Answers are grounded in this paper and cite their sources.
Multiple sequence alignment is an important problem in computational molecular biology. Dynamic programming for optimal multiple alignment requires too much time to be practical. Although many algorithms for suboptimal alignment have been suggested, no “performance guarantees” algorithms have been known until recently. A computationally efficient approximation multiple alignment algorithm with guaranteed error bounds equal to the normalized communication cost of a corresponding graph is given in this paper. Recently, Altschul and Lipman [SIAM J. Appl. Math., 49 (1989), pp. 197–209] used suboptimal alignments for reducing the computational complexity of the optimal alignment algorithm. This paper develops the Altschul–Lipman approach and demonstrates that bounds for optimal multiple alignment of k sequences can be derived from a solution of the maximum weighted matching problem in a k-vertex graph. Fast maximum matching algorithms allow efficient implementation of dynamic bounds for the multiple alignment problem.
No takes yet. Share an insight, caveat, or question.
Pavel A. Pevzner (1992) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: