previous section previous page next page next section
CMB

Online Lectures on Bioinformatics

navigation


Phylogenetic Trees and Multiple Alignments



Additive trees

A generalization of ultrametric trees are additive trees. Remind that in an ultrametric tree, the number of mutations was assumed to be proportional to the temporal distance of a node to the ancestor and it was also assumed that the mutations took place with the same rate in all paths. Thus an ultramaetric tree is assigned a root and the distance from the root to a leave is constant. But it's a fact, that the evolutionary clock is running differently for different species and even for different regions i.e. in a protein sequence. An unrooted phylogenetic tree is a reflection of our ignorance as to where the common ancestor lies. All nodes of an additive tree except for the leaves have degree three, an additive tree is therefore an unrooted binary tree.

\includegraphics{additive.eps}

Definition: The additional requirement for an additive metric is:


\begin{displaymath}d(x,y) \ + \ d(u,v) \ \leq \ max(d(x,u) \ + \ d(y,v), \ d(x,v) \ + \ d(y,u)) \qquad \forall \ x, \ y, \ u, \ v \end{displaymath}

An additive tree also is characterized by the four point condition:

Any 4 points can be renamed such that


\begin{displaymath}d(x,y) \ + \ d(u,v) \ \leq \ d(x,u) \ + \ d(y,v) \ = \ d(x,v) \ + \ d(y,z) \end{displaymath}

\includegraphics{four_points.eps}

The tree construction from an additive metric works by successive insertion. There is exactly one tree topology that allows for realization of an additive metric.


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