**Chantal Korostensky, Ulrike Stege and Gaston Gonnet
e-mail: {korosten, stege, gonnet}@inf.ethz.ch**

*Date:*

Institute for Scientific Computing, ETH Zürich, Switzerland

The construction of both multiple sequence alignments (MSAs) and their corresponding evolutionary trees are fundamental problems in computational biology. Usually practical algorithms for constructing MSAs fail to produce an exact solution due to the complexity of the problems for the underlying model. The main problem in the biological point of view is the misplacement of gaps. We present two different algorithms for dealing with misplaced gaps in MSAs. The first algorithm takes as input an MSA that was built by any algorithm and produces an improved MSA. With the use of a well defined scoring function we can determine the maximum possible score of a given MSA. The second algorithm deals with the problem of evolutionary tree construction using an MSA. Misplaced gaps can cause conflicts in the MSA and therefore can prevent a unique solution. We present an algorithm that transforms a conflicting MSA into a graph problem and show how to solve the problem using vertex cover.- Introduction
- Classification of the problems
- Methods
- Tree construction using gaps
- Bibliography
- About this document ...