Aligning a DNA sequence with a protein sequence

We develop several algorithms for the problem of aligning a DNA sequence with a protein sequence.Our methods account for frameshift errors, but not for introns in the DNA sequence.Thus, they are particularly appropriate for comparing a cDNA sequence that contains sequencing errors with an amino acid sequence or a protein sequence database.We describe techniques for efficient implementation, verify sufficient conditions for equivalenceof several definitions of alignment, and discuss experience with these ideas in a new release of the fasta suite of database-searching programs.