|
1
|
- Leaves are events
- Labels are evolutionary distances
|
|
2
|
- Form a distance matrix such that each row and column corresponds to a
species and the entries are the distances between
- Find a tree such that the distance between each pair of leaves is equal
to the distance between these species given in the distance matrix
(additive tree ®polynomial
solution)
- The distance matrix must be additive
|
|
3
|
|
|
4
|
- These conditions usually do not hold- problem becomes hard.
As a consequence, we invoke a heuristic. We will use Unweighted Pair Group
Method with Arithmetic Mean (UPGMA)
- UPGMA
- Bad news- Like any heuristic, it does not always produce the right
answer
- Good news- It always produces an ultrametic tree
|
|
5
|
- Choose the pair X,Y with the smallest distance
- Combine X and Y into a singleton, XY
- The distance between any other point and the compound species XY is the
arithmetic mean of the pairwise distances dij where i is a
component species of X and j is a component species of Y.
- Restated, the distance from k to xy is (d(k,x)+d(k,y))/2
|
|
6
|
- The matrix is now one order smaller
- Repeat the procedure until only two compound species remain.
|
|
7
|
- Build an evolutionary tree such that from the point of branching between
two (compound) species X and Y, the distance to each of their component
species is dij/2.
|
|
8
|
|
|
9
|
|
|
10
|
|
|
11
|
|
|
12
|
|
Notes
