cs178 hw 3 27 solutions

background image

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

background image

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

background image

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))

background image

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


Wyszukiwarka

Podobne podstrony:
cs178 hw 3 27 solutions(1)
Prezentacje, Spostrzeganie ludzi 27 11
27 407 pol ed02 2005
2012 02 27, ćwiczenie 1 0001
IE RS lab 11 solutions
Materiały do wykładu 4 (27 10 2011)
BTI AWAX 26 27 45
00090100091 Bardzo łatwy, 00090100091 Solution
53 Prostownik 27 150
ei 03 2002 s 27
Prz 3 w 27 DROGA GOŚCINNOŚCI
09 1993 27 32
4 27 Life coaching
27 Pigalle
27 28 Polimery NOWE
Cz B 00390100013 bardzo trudny, 00390100013 solution
egzamin 2 termin 27 06 2005 id Nieznany

więcej podobnych podstron