title: A tool for aligning very similar DNA sequences.
abstract: We have produced a computer program, named sim3, that solves the following computational problem. Two DNA sequences are given, where the shorter sequence is very similar to some contiguous region of the longer sequence. Sim3 determines such a similar region of the longer sequence, and then computes an optimal set of single-nucleotide changes (i.e. insertions, deletions or substitutions) that will convert the shorter sequence to that region. Thus, the alignment scoring scheme is designed to model sequencing errors, rather than evolutionary processes. The program can align a 100 kb sequence to a 1 megabase sequence in a few seconds on a workstation, provided that there are very few differences between the shorter sequence and some region in the longer sequence. The program has been used to assemble sequence data for the Genomes Division at the National Center for Biotechnology Information.
authors.affiliation: Department of Computer Science and Information Management, Providence University, Shalu, Taichung, Taiwan.
authors.forename: K M
authors.initials: KM
authors.lastname: Chao
authors.forename: J
authors.initials: J
authors.lastname: Zhang
authors.forename: J
authors.initials: J
authors.lastname: Ostell
authors.forename: W
authors.initials: W
authors.lastname: Miller
mesh_terms: D000444:Aldehyde Dehydrogenase / Q000235:genetics; D000465:Algorithms; D000595:Amino Acid Sequence; D001483:Base Sequence; D003195:Computer Communication Networks; D004247:DNA / Q000235:genetics*; D005069:Evaluation Studies as Topic; D015894:Genome, Human; D006801:Humans; D008957:Models, Genetic; D008969:Molecular Sequence Data; D016415:Sequence Alignment / Q000379:methods* / Q000706:statistics & numerical data; D017386:Sequence Homology, Amino Acid; D012689:Sequence Homology, Nucleic Acid; D012984:Software
chemical_list: D004247:DNA; D000444:Aldehyde Dehydrogenase