Question

Reconstructing evolutionary trees by maximum parsimony. Suppose we manage to sequence a particular gene across a whole bunch of different species. For concreteness, say there are n species, and the sequences are strings of length k over alphabet$\underset{\mathbf{}}{\mathbf{\sum }\mathbf{=}\left\{A,C,G,T\right\}}$. How can we use this information to reconstruct the evolutionary history of these species?

Evolutionary history is commonly represented by a tree whose leaves are the different species, whose root is their common ancestor, and whose internal branches represent speciation events (that is, moments when a new species broke off from an existing one). Thus we need to find the following:

• An evolutionary tree with the given species at the leaves.

• For each internal node, a string of length K: the gene sequence for that particular ancestor.

For each possible tree T annotated with sequences$\mathit{s}\left(u\right)\mathbf{\in }\mathbf{\sum }_{\mathbf{}}\mathit{k}$at each of its nodes , we can assign a score based on the principle of parsimony: fewer mutations are more likely.

localid="1659249441524" $\mathrm{score}\mathbf{\left(}\mathbf{T}\mathbf{\right)}\mathbf{=}\mathbf{\sum }_{\mathbf{(}\mathbf{u}\mathbf{.}\mathbf{v}\mathbf{)}\mathbf{\in }\mathbf{E}\mathbf{\left(}\mathbf{T}\mathbf{\right)}}\mathbf{}\mathbf{(}\mathbf{number}\mathbf{}\mathbf{of}\mathbf{}\mathbf{positions}\mathbf{}\mathbf{on}\mathbf{}\mathbf{which}\mathbf{}\mathbf{s}\left(u\right)\mathbf{ands}\left(v\right)\mathbf{disagree}\mathbf{}\mathbf{)}$

Finding the highest-score tree is a difficult problem. Here we will consider just a small part of it: suppose we know the structure of the tree, and we want to fill in the sequences s(u) of the internal nodes u. Here’s an example with k=4 and n=5:

(a) In this particular example, there are several maximum parsimony reconstructions of the internal node sequences. Find one of them.

(b) Give an efficient (in terms of n and k ) algorithm for this task. (Hint: Even though the sequences might be long, you can do just one position at a time.)

Short answer

(a) One of the reconstructions of the internal nodes sequences:

(b)Algorithm for the given task.

$$\begin{gathered} \delta \left(i,j\right)=\left\{\begin{array}{l}1ifi=j\\ 0otherwise\end{array}\right. \\ L=left-subtree\left(T\right) \\ R=right-subtree\left(T\right) \\ S\left(T,C\right)=\underset{a\in \sum _{},b\in \sum _{}}{min}\left(S\left(L,a\right)+S\left(R,b\right)+\delta \left(c,a\right)+\delta \left(c,b\right)\right) \end{gathered}$$

Step-by-step solution

Step 1:Find one of the reconstruction

(a)

Consider the given tree,start mutation(change in sequence) from one position at a time, this also removes ambiguity of making sequence. Now according to mutation, there can be many evolution trees. One of the possible evolutionary tree is as follows,

Therefore, one of the reconstruction is obtained.

Step 2:Give an efficient algorithm

(b)

Consider one bit at time to define the algorithm. Define the state S(T,c), Where $c\in \left\{A,C,G,T\right\}$. To represent the problem domain,T is the subtree and the minimum score when the root node of T is c. So the following algorithm is,

$$\begin{gathered} \delta \left(I,J\right)=\left\{\begin{array}{l}1ifi=j\\ 0otherwise\end{array}\right. \\ L=left-subtree\left(T\right) \\ R=right-subtree\left(T\right) \\ S\left(T,C\right)=\underset{a\in \underset{}{\sum ,b\in \sum _{}}}{min}\left(S\left(L,a\right)+S\left(R,b\right)+\delta \left(c,a\right)+\delta \left(c,b\right)\right) \end{gathered}$$

Since inner nodes has two sons, the number of inner nodes that can be obtained is the number of leaf nodes minus 1. The state number can be calculated in s=O(n) time.

And the transition cost of the state is O (1). Thus, the whole algorithm complexity is O (nk)

Therefore, the efficient algorithm has been obtained with O (nk) complexity.