Algorithm for aligning nucleotide against peptide sequences

Gaston Gonnet gonnet at
Fri Oct 2 19:29:28 EST 1992

The following report is now available, please submit requests
to:  wertli at

184     Lukas Knecht, Gaston H. Gonnet: Alignment of Nucleotide with Peptide

The alignment of a nucleotide (DNA/RNA) with a peptide sequence (protein)
is usually computed by translating the open reading frames of the
nucleotide sequence into hypothetical proteins, then aligning each protein
with the peptide sequence. Such an approach however cannot properly handle
base indels or introns that change the nucleotide's reading frame.
The dynamic programming algorithm presented here simultaneously translates
the nucleotide sequence and aligns it to the peptide sequence, thereby
considering all reading frames in every step, and in effect finds the
optimal reading frames. The algorithm can be efficiently implemented. With
a nucleotide sequence of m bases and a peptide sequence of n amino acids,
its time complexity is O(mn). It has been successfully applied to searching
for similarities between yeast chromosome III and known proteins.

This algorithm is implemented and available in the Darwin system.

More information about the Comp-bio mailing list