Fast optimal alignment.
Algorithms often align sequences by minimizing a cost. Such algorithms usually operate by aligning successively longer subsequences until they finish the alignment. Efficient algorithms, such as those of Fickett and Ukkonen, speed the computation by ignoring bad subalignments. A general principle underlies the efficiency of these two algorithms: inequalities can direct computations to promising subalignments. Hence inequalities can be used to suggest alignment algorithms. Inequalities for unweighted end-gaps, affine and concave gap weights, etc., are discussed, and empirical results evaluating new algorithms for single indel costs and weighted end-gaps are presented. Empirical results show the new algorithms are, under certain circumstances, much faster than known algorithms.
Spouge
J L
JL
National Center for Biotechnology Information, National Library of Medicine, Bethesda, MD 20894.
D000465:Algorithms; D001709:Biotechnology / Q000379:methods*; D010363:Pattern Recognition, Automated