title: An iterative method for faster sum-of-pairs multiple sequence alignment.
abstract: BACKGROUND
  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 alpha(*) 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.
authors: Celera Genomics, Informatics Research, 45 West Gude Drive, Rockville, MD 20850, USA.
authors: K
authors: K
authors: Reinert
authors: J
authors: J
authors: Stoye
authors: T
authors: T
authors: Will
mesh_terms: D000465:Algorithms; D019295:Computational Biology / Q000295:instrumentation / Q000379:methods*; D017124:Conserved Sequence / Q000235:genetics; D003574:Cytochrome c Group / Q000235:genetics; D016208:Databases, Factual; D011237:Predictive Value of Tests; D015203:Reproducibility of Results; D016415:Sequence Alignment / Q000379:methods*; D017386:Sequence Homology, Amino Acid; D013997:Time Factors
chemical_list: D003574:Cytochrome c Group