Exercises marked with (*) require further reading/search beyond the suggested texts.
1. For each of the input matrices below, determine whether it admits a perfect phylogeny and construct such a phylogeny if one exists.
C1 C2 C3 A 0 1 0 B 0 0 1 C 0 1 1 D 1 1 0 E 1 0 0
C1 C2 C3 C4 A 0 1 0 1 B 0 1 1 1 C 0 1 1 1 D 1 1 0 0 E 1 0 0 0
Answer:
According to the following lemma, there is no perfect phylogeny tree for the first matrix presented:
Lemma: A binary matrix M admits a perfect phylogeny with all characters absent in the root if and only if for each pair of characters i and j the sets Oi and Oj are disjoint or one of them contains the other.
For the second matrix, if we complement the second character, it becomes possible to build a perfect phylogeny for this matrix. The figure below shows such a perfect phylogeny, where it is assumed that the root has character C2 and no other characters, and that the edge linked to species E contains a loss of characteristc C2.
© 2015 Joao Meidanis