Homework Due April 3
rd
Question 1
Phylogenetic Trees
Consider the following triangular distance matrix:
B C D E
A 14 14 6 10
B 4 14 14
C 14 14
D 10
•
You should provide the sequence of (increasingly smaller) triangular matrices that
define the distances between the nodes and combinations of nodes.
•
Transform your unrooted tree into a rooted ultrametric tree by suitably adding
the root.
•
Represent your tree using parenthesis
You may use the steps suggested in the following URL where an example is also fully
worked out:
http://linneus20.ethz.ch:8080/5_4_9.html
Solution
Sequence of Triangular Matrices
B C D E
A 14 14 6 10
B 4* 14 14
C 14 14
D 10
The asterisk indicates the minimal distance
Combine nodes B and C
The resulting matrix becomes
D E BC
A 6* 10 14
D 10 14
E 14
The minimal distance is now 6 indicating that one has to combine nodes A and D
The next triangular matrix becomes:
AD BC
E 10* 14
AD 14
Finally one combines E with AD obtaining
BC
EAD 14
The unrooted tree becomes:
B 2 | 3 A
| 2AD |
| BC | | 3 D
|7 EAD |
| | 5 E
|
C 2
By choosing a root in the segment (BC EAD) at a distance 5 from node BC and a
distance 2 from EAD one obtains an ultrametric tree because the distance from any node
A,B,C,D, E to that root is always 7.
The parenthesis representation of the rooted tree is ((B C) (E (A D))
Question 2
Character Based
Perfect Phylogeny
Consider the following character matrix with 5 objects A, B, C, D, E and 7 characters
C1, C2, …, C7
C1
C2
C3
C4
C5
C6
C7
A
1
1
0
0
0
0
0
B
0
0
1
1
0
0
0
C
1
0
0
0
1
1
0
D
1
0
0
0
1
0
1
E
0
0
0
1
0
0
0
Determine if the above corresponds to perfect phylogeny and draw the corresponding
character tree
Solution
C1
C4
C2
A
C6
C7
E
B
C
D
C3
C5