Bioinformatics, Vol 15, 122-130, Copyright © 1999 by Oxford University Press
K Bucka-Lassen, O Caprani and J Hein
MOTIVATION: The fact that the multiple sequence alignment problem is of
high complexity has led to many different heuristic algorithms attempting
to find a solution in what would be considered a reasonable amount of
computation time and space. Very few of these heuristics produce results
that are guaranteed always to lie within a certain distance of an optimal
solution (given a measure of quality, e.g. parsimony). Most practical
heuristics cannot guarantee this, but nevertheless perform well for certain
cases. An alignment, obtained with one of these heuristics and with a bad
overall score, is not unusable though, it might contain important
information on how substrings should be aligned. This paper presents a
method that extracts qualitatively good sub-alignments from a set of
multiple alignments and combines these into a new, often improved
alignment. The algorithm is implemented as a variant of the traditional
dynamic programming technique. RESULTS: An implementation of ComAlign (the
algorithm that combines multiple alignments) has been run on several sets
of artificially generated sequences and a set of 5S RNA sequences. To
assess the quality of the alignments obtained, the results have been
compared with the output of MSA 2.1 (Gupta et al., Proceedings of the Sixth
Annual Symposium on Combinatorial Pattern Matching, 1995; Kececioglu et
al., http://www.techfak.uni-bielefeld. de/bcd/Lectures/kececioglu.html,
1995). In all cases, ComAlign was able to produce a solution with a score
comparable to the solution obtained by MSA. The results also show that
ComAlign actually does combine parts from different alignments and not just
select the best of them. AVAILABILITY: The C source code (a Smalltalk
version is being worked on) of ComAlign and the other programs that have
been implemented in this context are free and available on WWW
http://www.daimi.au.dk/ ocaprani. CONTACT: klaus@bucka-lassen.dk;
jotun@pop.bio.au.dk;ocaprani@daimi.au.dk
ARTICLES
Combining many multiple alignments in one improved alignment
Object Oriented Ltd, 6004 Luzern, Switzerland, Department of Computer Science and Department of Ecology and Genetics, University of Aarhus, 8000 Aarhus C, Denmark.
CiteULike 
Connotea 
Del.icio.us What's this?
This article has been cited by other articles:
|
|
 |
|
  S. Moretti, F. Armougom, I. M. Wallace, D. G. Higgins, C. V. Jongeneel, and C. Notredame The M-Coffee web server: a meta-method for computing multiple sequence alignments by combining alternative alignment methods Nucleic Acids Res., July 13, 2007; 35(suppl_2): W645 - W648. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
I. M. Wallace, O. O'Sullivan, D. G. Higgins, and C. Notredame M-Coffee: combining multiple sequence alignment methods with T-Coffee Nucleic Acids Res., March 23, 2006; 34(6): 1692 - 1699. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
T. Lassmann and E. L. L. Sonnhammer Automatic assessment of alignment quality Nucleic Acids Res., December 16, 2005; 33(22): 7120 - 7128. [Abstract] [Full Text] [PDF]
|
|
|
|
 |
|
 H. Zhou and Y. Zhou SPEM: improving multiple sequence alignment with sequence profiles and predicted secondary structures Bioinformatics, September 15, 2005; 21(18): 3615 - 3621. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. H. Havgaard, R. B. Lyngso, G. D. Stormo, and J. Gorodkin Pairwise local structural alignment of RNA sequences with sequence similarity less than 40% Bioinformatics, May 1, 2005; 21(9): 1815 - 1824. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. Gorodkin, S. L. Stricklin, and G. D. Stormo Discovering common stem-loop motifs in unaligned RNA sequences Nucleic Acids Res., May 15, 2001; 29(10): 2135 - 2144. [Abstract] [Full Text] [PDF]
|
|
|
|
|
|
J. D. Thompson, F. Plewniak, J.-C. Thierry, and O. Poch DbClustal: rapid and reliable global multiple alignments of protein sequences detected by database searches Nucleic Acids Res., August 1, 2000; 28(15): 2919 - 2926. [Abstract] [Full Text] [PDF]
|
|