Online Lectures on Bioinformatics

navigation

Phylogenetic Trees and Multiple Alignments

Ultrametric Trees

Definition:

A metric on a set of objects O is given by the assignment of a real number d(x,y) to every pair $x,y \in O$ , whereat d(x,y)has to fulfill the following requirements:

$\begin{eqnarray*}d(x,y) & > & 0 \qquad \ for \ x \neq y \\ d(x,y) & = & 0 \qqua... ...z) \qquad \forall \ x, y, z \quad \textrm{(triangle inequality)} \end{eqnarray*}$

An ultrametric has to fulfill an additional requirement:

$\begin{displaymath}d(x,y) \ \leq \ max \ (d(x,z), \ d(y,z)) \end{displaymath}$

An ultrametric tree also is characterized by the three point condition (P. Bunemann):

Any three points x, y, z can be renamed such that

$\begin{displaymath}d(x,y) \ \leq \ d(x,z) \ = \ d(y,z) \end{displaymath}$

Given a set of sequences and assuming that the pairwise sequence alignments provide a measure for the evolutionary distance between the sequences and that the the resulting distance matrix constitutes an ultrameric (the ideal case), the reconstruction of the phylogenetic, ultrametric tree is managed by the following general clustering procedure:

Always pick the closest pair from the distance matrix and merge these two objects into one. Various schemes differ in how the distance between a newly formed object and the other objects is defined. Say, object x has been formed by merging y and z.

$\begin{eqnarray*}\textrm{\textit{single linkage clustering}:} \quad d(x,u) & := ... ...e clustering}:} \quad d(x,u) & := & 1/2 * (d(y,u) \ + \ d(z,u)) \end{eqnarray*}$

For non-ultrametric distances clustering will produce an ultrametic tree, whose distances will somehow resemble the original matrix.

The following figure gives an example for the construction of an ultrametric tree by average linkage clustering. Given is a $n \ x \ n$ distance matrix constituting an ultrametric:

$\includegraphics{ultrametric.eps}$

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