next up previous
Next: Introduction

Using Insertion and Deletion Events for Improving Multiple Sequence Alignments and Building the Corresponding Evolutionary Tree

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.

 
next up previous
Next: Introduction
Chantal Korostensky
1999-07-14