Journal Article

A <i>min-cut</i> algorithm for the consistency problem in multiple sequence alignment

Eduardo Corel, Florian Pitschi and Burkhard Morgenstern

in Bioinformatics

Volume 26, issue 8, pages 1015-1021
Published in print April 2010 | ISSN: 1367-4803
Published online February 2010 | e-ISSN: 1460-2059 | DOI:
A min-cut algorithm for the consistency problem in multiple sequence alignment

More Like This

Show all results sharing this subject:

  • Bioinformatics and Computational Biology


Show Summary Details


Motivation: 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.

Availability: The prototype is freely available under GNU Public Licence from E.C.


Journal Article.  6438 words.  Illustrated.

Subjects: Bioinformatics and Computational Biology

Full text: subscription required

How to subscribe Recommend to my Librarian

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.