The Small Parsimony Algorithm

Loading...

Do curso por University of California San Diego

Molecular Evolution (Bioinformatics IV)

47 classificações

University of California San Diego

Molecular Evolution (Bioinformatics IV)

47 classificações

Curso 4 de 7 em Specialization Bioinformatics

In the previous course in the Specialization, we learned how to compare genes, proteins, and genomes. One way we can use these methods is in order to construct a "Tree of Life" showing how a large collection of related organisms have evolved over time. In the first half of the course, we will discuss approaches for evolutionary tree construction that have been the subject of some of the most cited scientific papers of all time, and show how they can resolve quandaries from finding the origin of a deadly virus to locating the birthplace of modern humans. In the second half of the course, we will shift gears and examine the old claim that birds evolved from dinosaurs. How can we prove this? In particular, we will examine a result that claimed that peptides harvested from a T. rex fossil closely matched peptides found in chickens. In particular, we will use methods from computational proteomics to ask how we could assess whether this result is valid or due to some form of contamination. Finally, you will learn how to apply popular bioinformatics software tools to reconstruct an evolutionary tree of ebolaviruses and identify the source of the recent Ebola epidemic that caused global headlines.

Na lição

Week 3: Constructing Evolutionary Trees from Characters

<p>Welcome to week 3 of class!</p> <p>Over the last two weeks, we have seen several different algorithms for constructing evolutionary trees from distance matrices.</p> <p>This week, we will conclude the current chapter by considering what happens if we use properties called "characters" instead of distances. We will also see how to infer the ancestral states of organisms in an evolutionary tree, and consider whether it is possible to define an efficient algorithm for this task.</p>

Character-Based Tree Reconstruction 3:01

The Small Parsimony Algorithm 8:31

The Large Parsimony Algorithm 3:14

Evolutionary Tree Reconstruction in the Modern Era 5:30

Conheça os instrutores

Pavel Pevzner
Professor
Department of Computer Science and Engineering
Phillip Compeau
Visiting Researcher
Department of Computer Science & Engineering

So in the previous section, we introduced character tables,

and we saw that we can think about a multiple alignment

as a character table of its own, for which each of the m columns of this

multiple alignment can be viewed as a character.

Our goal is to use this multiple alignment

to reconstruct the most likely ancestral sequences.

To do so, we're going to need some way of determining how good

an assignment of ancestral sequences is for a given tree.

For example, say that we're given the following tree structure for

the four species that we've been considering, and that we then assign

the following ancestral sequences to internal nodes of the tree.

We're going to define the parsimony score, then,

of this tree, as the sum of the Hamming distances along each edge of the tree.

This tree has parsimony score equal to eight.

And this discussion brings us to the small parsimony problem, in which

we're given a rooted binary tree whose leaves are labeled by strings of length m,

and our goal is to assign ancestral sequences to this tree

in order to minimize the parsimony score.

Now, this seems like a difficult problem.

Is there going to be any way of simplifying it?

If we treat the columns of the multiple alignment that we're given as independent

of each other, then it means that we'll be able to solve the small

parsimony problem on each column of the multiple alignment separately.

In other words, we can work with one symbol of each string at a time.

So we'll now design a dynamic programming algorithm that will solve

the small parsimony problem, assuming that each string is just a single symbol.

So first, define T_v as the subtree of

the given tree T whose root is node v.

Then define s_k(v) as the minimum parsimony score

of the subtree T_v over all possible labelings of T_v,

such that the node v is labeled by symbol k.

Note that according to this definition,

the minimum parsimony score of the entire tree T is equal to

the minimum value of s_k at the root, taken over all symbols k.

The idea of our dynamic programming algorithm, then, is going to start at

the leaves of the tree, then compute the values s_k upward from

the leaves to the root, and then use this fact to find the minimum parsimony score.

In order to implement this algorithm,

we're going to need a recurrence relation for the score of a node v in

terms of its two children, which I'll call its "son" and its "daughter".

So we can define sigma_i,j to be 0 if the symbols i and

j are equal to each other.

And if i and j are not equal to each other,

we define sigma_i,j to be equal to 1.

Because you're a dynamic programming expert by now,

I'm going to leave proving this recurrence relation to you.

So once you've demonstrated this recurrence relation,

let's see how it works for an example.

So at each node v, an array is going to hold the set of scores s_k(v) for

each possible symbol k.

Here we're going to be working with DNA, so there will be four symbols k.

Because the leaves are preassigned in our tree,

we're going to set their scores equal to 0 for the symbols of those leaves, and

infinity for all other symbols.

For example, here the leaf is assigned C, so

we set the score of C equal to 0 and the score of T equal to infinity.

Why would we do this? Well, it prevents us from then going back and

changing the leaf node to t later.

It is something that we want to prevent, right?

So when we move up a level, we're going to apply the recurrence relation.

In the left most node, the two children are fixed as equal to C.

So the score of this node is going to be 0 if we assign it a C,

since there will be no conflicts between these two edges.

If we assign this node any other symbol,

then there will be two conflicts between the edges, and its score is going to be 2.

One node over from this, we will obtain a score of 1 if we assign this node an A or

a C, and a score of 2 otherwise because we'll have two conflicts.

The remaining two nodes proceed similarly.

So, note that I'm using red to indicate the minimum score at each step and

there may be a tie as we've seen in two nodes here.

When we move up one more level in the tree,

let's walk through the computation of, say, the array of the left node.

The score of A corresponds to the minimum parsimony score

over all possible assignments to this subtree,

assuming that A is assigned to that subtree.

In this case, the best that we can do is not to take an A here, but

to take a C here, since the parsimony score of that subtree will be equal to 0.

And then that will provide us with a conflict of 1 on that edge.

In this case, we do want to take A because the parsimony score of this subtree will

be 1, and then A will agree here.

In a sense, we're breaking the tie between A and C if we assign that equal to A.

So we would have gotten a score of 1 from this subtree, and

a score of 1 from this subtree, so we assign A a score of 2.

C should be pretty straightforward because C is a minimum at each of these two nodes.

So if we assign a C here and a C here, we get parsimoniy scores of 0 and 1,

and we have no conflicts here.

So this is really what the recurrence relation is saying.

So, two more examples.

For G, if we assume that we assign a G there, then we don't want to assign

Gs here because that would give us parsimony score of 4 here and 4 here,

and although we wouldn't have any conflicts along these edges,

we would have a score of 4.

We can do better than that if we simply assign Cs to both of these nodes,

in which case we get two conflicting edges, so a contribution of 2,

but then a contribution of 0 and 1, which gives us 3.

The case of T follows analogously because it's essentially the same as G.

So hopefully, you can see from that how we can get the right node on this level,

as well as when we move to the root.

So when we move to the root,

the minimum parsimony score is going to be corresponding to symbol C,

which means that we should assign C to the root because we said that the minimum

parsimony score of the tree was the minimum at the root over all symbols.

So, to reconstruct the other ancestral states, you're going to need to flex your

dynamic programming muscles once again and implement a backtracking approach

that goes from the root down to the leaves and assign symbols.

I want you to note, when you do this, that the red elements correspond to minima, but

they don't necessarily correspond to an optimal assignment of ancestral symbols.

So, for example, we're going to get into trouble

if we assign a T to this right-most node in the tree.

So, I want you to make sure that your backtracking approach is able to

reconstruct the tree shown on this slide before you try to implement a solution for

the small parsimony problem.

Once you have done so,

you might find it interesting to apply the SmallParsimony dynamic

programming algorithm to the tree we previously constructed for coronaviruses.

What are the ancestral coronavirus sequences that you obtain?

Also, it turns out that you can find the most parsimonious labeling of the internal

nodes in an unrooted tree by placing a root on an arbitrary edge,

solving the small parsimony problem for the resulting rooted tree, and

then simply removing the root.

Explore nosso catálogo

Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.

O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.

© 2019 Coursera Inc. Todos os direitos reservados.

Baixar na App Store

Baixar no Google Play