Phylogenetic Trees and Multiple Alignments

Reconstruction of additive trees

The following algorithm for the reconstruction of an additive tree from a given distance matrix was introduced by Beyer, Singh, Smith and Waterman:

• Verify that the distance matrix constitutes an additive metric
• Choose a pair of objects, which results in the first path in the tree.
• Choose a third object and establish the linear equations to let the object branch off the path.
• Choose a pair of leaves in the tree constructed so far and compute the point a newly chosen object is inserted at.

  1.

  The new path branches off an existing branch in the tree: Do the insertion step once more in the branching path.

  2.

  The new path branches off an edge in the tree: This insertion is finished.

An alternative algorithm inserts a new object into the tree by trying to solve the linear equations which result from trying to let the new edge branch off each edge in the tree, whereat there exists a solution for one edge only:

Given a distance matrix constituting an additive metric, the topology of the corresponding additive tree is unique.