Bioinformatics Vol. 16 no. 9 2000
Pages 808-814
© 2000 Oxford University Press
An iterative method for faster sum-of-pairs multiple sequence alignment
1 Celera Genomics, Informatics Research, 45
West Gude Drive, Rockville, MD 20850, USA
2 German Cancer Research Center (DKFZ),
Theoretical Bioinformatics (H0300), Im Neuenheimer Feld 280, 69120,
Heidelberg, Germany
3 Research Center for Interdisciplinary
Studies on Structure Formation (FSPM), University of Bielefeld,
Postfach 100131, 33501, Bielefeld, Germany
Received on December 10, 1999
; revised on March 13, 2000
; accepted on May 5, 2000
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 
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: j.stoye{at}dkfz.de
To whom correspondence should be addressed.
**** Present address: mediaWays GmbH, Hülshorstweg 30, 33415 Verl, Germany.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  T. Rausch, A.-K. Emde, D. Weese, A. Doring, C. Notredame, and K. Reinert Segment-based multiple sequence alignment Bioinformatics, August 15, 2008; 24(16): i187 - i192. [Abstract] [PDF]
|
|
|
|
 |
|
 C. N.I. Pang, K. Lin, M. A. Wouters, J. Heringa, and R. A. George Identifying foldable regions in protein sequence from the hydrophobic signal Nucleic Acids Res., February 2, 2008; 36(2): 578 - 588. [Abstract] [Full Text] [PDF]
|
|