Spouge J L
National Center for Biotechnology Information, National Library of Medicine, Bethesda, MD 20894.
Comput Appl Biosci. 1991 Jan;7(1):1-7. doi: 10.1093/bioinformatics/7.1.1.
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.
