title: A min-cut algorithm for the consistency problem in multiple sequence alignment.
abstract: 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.
authors.affiliation: Georg-August-Universität, Institut für Mikrobiologie und Genetik, Goldschmidtstrasse 1, 37077 Göttingen, Germany. ecorel@gwdg.de
authors.forename: Eduardo
authors.initials: E
authors.lastname: Corel
authors.forename: Florian
authors.initials: F
authors.lastname: Pitschi
authors.forename: Burkhard
authors.initials: B
authors.lastname: Morgenstern
mesh_terms: D000465:Algorithms; D030541:Databases, Genetic; D023281:Genomics / Q000379:methods*; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA