Algorithm for aligning nucleotide against peptide sequences
gonnet at inf.ethz.ch
Fri Oct 2 19:29:28 EST 1992
The following report is now available, please submit requests
to: wertli at inf.ethz.ch
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