previous section previous page next page next section
CMB

Online Lectures on Bioinformatics

navigation


Phylogenetic Trees and Multiple Alignments



Iterative alignment strategy

The aim is to reduce the problem of a multiple alignment to an iteration of pairwise alignments.

The procedure works as follows:

  • Compute all pairwise distances between given sequences
  • Compute a tree by single linkage clustering
  • Align the sequences in bottom up order, see figure:

\includegraphics{it_ali.eps}

The bottom up alignment requires comparing groups of pre-aligned sequences. This is achieved by using profile alignment. Profile alignment relies on a NW like algorithm, however with scores defined as average scores among columns of pre-aligned sequence groups.

Again the concept of the edit matrix is used to obtain a dynamic programming algorithm. A possibility to treat the gaps in profile alignments is to look into the profiles and to overtake gap-penalties to the edit matrix.

Advantages of iterative alignment procedure:

  • profile alignment reflects the conservation within a group (biologically relevant)
  • it's fast and scales to large numbers of sequences

Disadvantages:

  • unclear objective function
  • misalignments introduced during the procedure are kept



Comments are very welcome.
luz@molgen.mpg.de