Exercise 2 Consider a set s.. , sn of current species. A phylogeny is a tree representation of the evolution that led, from a common unique ancestor, to s1,., sn The exact phylogeny is usually unknown, and it is an important problem in computational biology to find the one that is most likely. One of the prominent methods to reconstruct the phylogeny is the following: The input is given by a matrix M E10,1)nxm, where each row represents a species, and each column a character (e.g. the presence of a certain gene in the DNA, or a physical characteristic), and entry M[i.j is 1 if species i has character j, and 0 otherwise (see Figure 1, left). Figure 1, right gives a possible phylogeny of four species (lamprey, shark, salmon, lizard). It assumes that (*) all the species evolved from a common ancestor species a1, where none of the characters are present, through a sequence of successive ancestors. (**) Each species evolved from a previous ancestor species by developing one or more characters, or after one or more characters have disappeared no two species with the exactly the same cha racters appear at any time during the evolution In the tree T in Figure 1, a2 evolved from a1 by developing characters a, b, and shark, salmon, lizard evolved from the common ancestor a2. Salmon and lizard evolved from the common ancestor a3, that has characters a, b, c. Points at which characters emerge are indicated by labeled bars. A State change in T is the emergence of a certain character. For instance, between ancestors a and a2, there are two state changes. T has in total 7 state changes. a) Find a phylogeny tree for the instance in Figure 1 that respects hypothesis (*), (**), (***) and has at least 8 state changes b) A most parsimonious tree is a phylogeny tree that respects conditions (*), (*), **) and has a minimum number of state changes. Those trees are often considered very good candidates for representing the real evolution of the species. Give a graph G and a distance function c such that the problem of finding the most parsimonious tree for the input in Figure 1, left can be formulated as a Steiner Minimum Tree problem with respect to a distance c. c) Show that the problem of finding a most parsimonious tree for a generic input M E0,1n can be formulated as a Steiner Minimum Tree problem. a, b lamprey 0 0 0 0 0 1 shark 01 0 0 salmon 1 00 izard11 1 0 0 lamprey shark salmon lizard Figure 1: The data from Exercise 2 Exercise 2 Consider a set s.. , sn of current species. A phylogeny is a tree representation of the evolution that led, from a common unique ancestor, to s1,., sn The exact phylogeny is usually unknown, and it is an important problem in computational biology to find the one that is most likely. One of the prominent methods to reconstruct the phylogeny is the following: The input is given by a matrix M E10,1)nxm, where each row represents a species, and each column a character (e.g. the presence of a certain gene in the DNA, or a physical characteristic), and entry M[i.j is 1 if species i has character j, and 0 otherwise (see Figure 1, left). Figure 1, right gives a possible phylogeny of four species (lamprey, shark, salmon, lizard). It assumes that (*) all the species evolved from a common ancestor species a1, where none of the characters are present, through a sequence of successive ancestors. (**) Each species evolved from a previous ancestor species by developing one or more characters, or after one or more characters have disappeared no two species with the exactly the same cha racters appear at any time during the evolution In the tree T in Figure 1, a2 evolved from a1 by developing characters a, b, and shark, salmon, lizard evolved from the common ancestor a2. Salmon and lizard evolved from the common ancestor a3, that has characters a, b, c. Points at which characters emerge are indicated by labeled bars. A State change in T is the emergence of a certain character. For instance, between ancestors a and a2, there are two state changes. T has in total 7 state changes. a) Find a phylogeny tree for the instance in Figure 1 that respects hypothesis (*), (**), (***) and has at least 8 state changes b) A most parsimonious tree is a phylogeny tree that respects conditions (*), (*), **) and has a minimum number of state changes. Those trees are often considered very good candidates for representing the real evolution of the species. Give a graph G and a distance function c such that the problem of finding the most parsimonious tree for the input in Figure 1, left can be formulated as a Steiner Minimum Tree problem with respect to a distance c. c) Show that the problem of finding a most parsimonious tree for a generic input M E0,1n can be formulated as a Steiner Minimum Tree problem. a, b lamprey 0 0 0 0 0 1 shark 01 0 0 salmon 1 00 izard11 1 0 0 lamprey shark salmon lizard Figure 1: The data from Exercise 2