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 un­rooted tree into a rooted ultra­metric 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 un­rooted tree becomes:     

                                
B ­­­­­2­­­­­­                                                         |­­­­ 3­­­­ A        
                    |                                       ­­­­2­­­AD | 
                    | 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 ultra­metric 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