A min-cut algorithm for the consistency problem in multiple sequence alignment.
BACKGROUND
Multiple sequence alignments can be constructed on the basis of pairwise local sequence similarities. This approach is rather flexible and can combine the advantages of global and local alignment methods. The restriction to pairwise alignments as building blocks, however, can lead to misalignments since weak homologies may be missed if only pairs of sequences are compared.


RESULTS
Herein, we propose a graph-theoretical approach to find local multiple sequence similarities. Starting with pairwise alignments produced by DIALIGN, we use a min-cut algorithm to find potential (partial) alignment columns that we use to construct a final multiple alignment. On real and simulated benchmark data, our approach consistently outperforms the standard version of DIALIGN where local pairwise alignments are greedily incorporated into a multiple alignment.


BACKGROUND
The prototype is freely available under GNU Public Licence from E.C.
Corel
Eduardo
E
Georg-August-Universität, Institut für Mikrobiologie und Genetik, Goldschmidtstrasse 1, 37077 Göttingen, Germany. ecorel@gwdg.de
Pitschi
Florian
F
Morgenstern
Burkhard
B
D000465:Algorithms; D030541:Databases, Genetic; D023281:Genomics / Q000379:methods*; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA