ReAligner: a program for refining DNA sequence multi-alignments.
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.
Anson
E L
EL
Department of Computer Science, University of Arizona, Tucson 85721, USA. anson@cs.arizona.edu
Myers
E W
EW
D000465:Algorithms; D001483:Base Sequence; D004247:DNA; D008957:Models, Genetic; D008969:Molecular Sequence Data; D016415:Sequence Alignment / Q000379:methods*; D012984:Software
D004247:DNA