Fast optimal alignment. 1991

J L Spouge
National Center for Biotechnology Information, National Library of Medicine, Bethesda, MD 20894.

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.

UI MeSH Term Description Entries
D010363 Pattern Recognition, Automated In INFORMATION RETRIEVAL, machine-sensing or identification of visible patterns (shapes, forms, and configurations). (Harrod's Librarians' Glossary, 7th ed) Automated Pattern Recognition,Pattern Recognition System,Pattern Recognition Systems
D000465 Algorithms A procedure consisting of a sequence of algebraic formulas and/or logical steps to calculate or determine a given task. Algorithm
D001709 Biotechnology Body of knowledge related to the use of organisms, cells or cell-derived constituents for the purpose of developing products which are technically, scientifically and clinically useful. Alteration of biologic function at the molecular level (i.e., GENETIC ENGINEERING) is a central focus; laboratory methods used include TRANSFECTION and CLONING technologies, sequence and structure analysis algorithms, computer databases, and gene and protein structure function analysis and prediction. Biotechnologies

Related Publications

J L Spouge
January 1984, Nucleic acids research,
J L Spouge
January 2013, Scientific reports,
J L Spouge
December 2000, Journal of theoretical biology,
J L Spouge
September 1993, Journal of theoretical biology,
J L Spouge
October 2012, Bioinformatics (Oxford, England),
J L Spouge
May 2009, PLoS computational biology,
J L Spouge
June 1996, Current opinion in structural biology,
J L Spouge
March 1974, Applied optics,
J L Spouge
January 2013, IEEE/ACM transactions on computational biology and bioinformatics,
Copied contents to your clipboard!