Abstract 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 sev-eral definitions of alignment, and discuss experience with these ideas in a new release of the fasta suite of database-searching programs. 1 Basic Definition and Algorithm We begin with a plausible definition of an alignment of a DNA sequence and an amino acid sequence, then give an algorithm for computing an optimal alignment. This section restates ideas originally developed ten years ago by Peltola et al. [9]. Alignment scores are based on (1) a penalty x> 0 for inserting or deleting a nucleotide (i.e., a frameshift er-ror), (2) an amino-acid substitution-score matrix, S, (such as a PAM or Blosum matrix) and (3) gap-open and gap-extension penalties, gop> 0 and gep> 0 (i.e., a gap of g amino acids is penalized gop+gep.g). Let S[Z, y] denote the substitution score for amino acids z and y. To score the re-placement of a short string of nucleotides by an amino acid, we proceed as follows. Let w be a nucleotide string of length 2, 3 or 4, and let y be an amino acid. Define an amino acid, denoted I, as follows. If 1~0) = 3 (1~1 denotes the length of w), then z is t,he translation of w according to the genetic code. If [WI = 2, pick 2 such that w is a subsequence of some codon for z and S[Z, y] is maximal over all such x. If 1201 = 4, pick z such that some codon for z is a subsequenc