Aligning a DNA sequence with a protein sequence

We develop several algorithms for the problem of aligning 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 suffers from sequencing errors with an amino acid sequence or a protein sequence database, We describe algorithms for computing optimal alignments for several definitions of DNA-protein alignment, verify sufficient conditions for equivalence of certain definitions, describe techniques for efficient implementation, and discuss experience with these ideas in a new release of the FASTA suite of database-searching programs.