title: Alignments of DNA and protein sequences containing frameshift errors.
abstract: Molecular sequences, like all experimental data, are subject to error. Many current DNA sequencing protocols have very significant error rates and often generate artefactual insertions and deletions of bases (indels) which corrupt the translation of sequences and compromise the detection of protein homologies. The impact of these errors on the utility of molecular sequence data is dependent on the analytic technique used to interpret the data. In the presence of frameshift errors, standard algorithms using six-frame translation can miss important homologies because only subfragments of the correct translation are available in any given frame. We present a new algorithm which can detect and correct frameshift errors in DNA sequences during comparison of translated sequences with protein sequences in the databases. This algorithm can recognize homologous proteins sharing 30% identity even in the presence of a 7% frameshift error rate. Our algorithm uses dynamic programming, producing a guaranteed optimal alignment in the presence of frameshifts, and has a sensitivity equivalent to Smith-Waterman. The computational efficiency of the algorithm is O(nm) where n and m are the sizes of two sequences being compared. The algorithm does not rely on prior knowledge or heuristic rules and performs significantly better than any previously reported method.
authors.affiliation: Computer Science and Mathematics Division, Oak Ridge National Laboratory, TN 37831-6364, USA. x3g@ornl.gov
authors.forename: X
authors.initials: X
authors.lastname: Guan
authors.forename: E C
authors.initials: EC
authors.lastname: Uberbacher
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D000818:Animals; D004247:DNA / Q000737:chemistry* / Q000235:genetics*; D016208:Databases, Factual; D005069:Evaluation Studies as Topic; D016368:Frameshift Mutation; D006801:Humans; D008969:Molecular Sequence Data; D011506:Proteins / Q000737:chemistry* / Q000235:genetics*; D051381:Rats; D012680:Sensitivity and Specificity; D016415:Sequence Alignment / Q000379:methods* / Q000706:statistics & numerical data; D017386:Sequence Homology, Amino Acid
chemical_list: D011506:Proteins; D004247:DNA