An iterative method for faster sum-of-pairs multiple sequence alignment
Knut Reinert, Jens Stoye, Torsten Will · Bioinformatics · 2000
Abstract Motivation: Multiple sequence alignment is an important tool in computational biology. In order to solve the task of computing multiple alignments in affordable time, the most commonly used multiple alignment methods have to use heuristics. Nevertheless, the computation of optimal multiple alignments is important in its own right, and it provides a means of evaluating heuristic approaches or serves as a subprocedure of heuristic alignment methods. Results: We present an algorithm that uses the divide-and-conquer alignment approach together with recent results on search space reduction to speed up the computation of multiple sequence alignments. The method is adaptive in that depending on the time one wants to spend on the alignment, a better, up to optimal alignment can be obtained. To speed up the computation in the optimal alignment step, we apply the \batchmode \documentclass[fleqn,10pt,legalpaper]{article} \usepackage{amssymb} \usepackage{amsfonts} \usepackage{amsmath} \pagestyle{empty} \begin{document} \(\mathcal{A}^{*}\) \end{document}algorithm which leads to a procedure provably more efficient than previous exact algorithms. We also describe our implementation of the algorithm and present results showing the effectiveness and limitations of the procedure. Availability: http://bibiserv.techfak.uni-bielefeld.de/oma/ Contact: [email protected] To whom correspondence should be addressed. **** Present address: mediaWays GmbH, Hülshorstweg 30, 33415 Verl, Germany.