title: ReAligner: a program for refining DNA sequence multi-alignments.
abstract: We present a round-robin realignment algorithm that improves a potentially crude initial alignment of an assembled collection of DNA sequence fragments, as might, for example, be output by a typical fragment assembly program. The algorithm uses a weighted combination of two scoring schemes to achieve superior multi-alignments, and employs a banded dynamic programming variation to achieve a running time that is linear in the amount of sequence in the data set. We demonstrate that the algorithm improves upon the alignments produced by other assembly programs in a series of empirical experiments on simulated data. Finally, we present a pair of programs embodying the algorithms that are available from the Web site ftp://ftp.cs.arizona.edu/realigner.
authors.affiliation: Department of Computer Science, University of Arizona, Tucson 85721, USA. anson@cs.arizona.edu
authors.forename: E L
authors.initials: EL
authors.lastname: Anson
authors.forename: E W
authors.initials: EW
authors.lastname: Myers
mesh_terms: D000465:Algorithms; D001483:Base Sequence; D004247:DNA; D008957:Models, Genetic; D008969:Molecular Sequence Data; D016415:Sequence Alignment / Q000379:methods*; D012984:Software
chemical_list: D004247:DNA