title: Aligning a DNA sequence with a protein sequence.
abstract: 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.
authors.affiliation: Department of Computer Science and Engineering, The Pennsylvania State University, University Park 16802, USA. zzhang@galapagos.cse.psu.edu
authors.forename: Z
authors.initials: Z
authors.lastname: Zhang
authors.forename: W R
authors.initials: WR
authors.lastname: Pearson
authors.forename: W
authors.initials: W
authors.lastname: Miller
mesh_terms: D000465:Algorithms; D004247:DNA / Q000737:chemistry*; D016208:Databases, Factual; D011506:Proteins / Q000737:chemistry*; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA; D012984:Software
chemical_list: D011506:Proteins; D004247:DNA