Phylogenetic Trees and Multiple Alignments

Heuristics

1.

Heuristics for tree construction

The methods for exact tree reconstruction provide an inventory for heuristics for tree construction based on approximating additive metrics. Heuristics give exact results when operating on additive metrics, but the performance of solutions gets unclear when biased additive metrics are handled.

• Insertion heuristics

  Step by step new objects are inserted into the tree. Each edge is tested for insertion, and for each edge an objective function is minimized. Finally the object is inserted at the edge, which minimizes the objective function best.

• Rearrangement

  In addition to inserting objects, objects are taken out, the tree is rearranged and new insertions of objects are tested.

• Nearest Neighbor Interchange

  The tree topology is changed by exchanging two nearest leaves, and for each topology, an objective function is minimized.

2.

The Three-Way-Alignment

The principle of the Three-Way-Alignment is to build up a multiple alignment by constructing a tree and aligning sequences and pre-aligned groups of sequences simultaneously:

Given N sequences and assume, that there is a tree topology for sequences and a multiple alignment for n sequences coupled to the tree, i.e n=5:

Each edge of the tree is tested for an insertion of a new sequence, i.e. test edge e:

For an insertion of a sequence in edge e, a three-way-alignment between the following groups of sequences is computed

• The aligned sequences on the left of e
• The aligned sequences on the right of e
• the new sequence

The three-way alignment implies new edge weights and therefore a new path length for the complete tree:

In order to keep the amount of evolution as small as possible, one chooses the topology resulting in the smallest path length.

In the example an alignment of n+1 sequences now is coupled with a tree topology for six sequences:

and a new sequence may be inserted...

When constructing a multiple alignment iteratively in this way, a correction of positions in the profile alignments is possible.

exercises

For a more detailed view on the subject, have a look at the paper of Vingron and v. Haeseler.

The methods for phylogeny construction we used so far were distance based: The input data were distances between present-day objects. Input data may also be given by discrete characters having a finite number of states.