1、.,Intro to Phylogenetic Trees Computational Genomics Lecture 4b,Sections 7.1, 7.2, in Durbin et al. Chapter 17 in GusfieldSlides by Shlomo Moran and Ido Wexler. Slight modifications by Benny Chor,2,Evolution,Evolution of new organisms is driven by Diversity Different individuals carry different vari
2、ants of the same basic blue print Mutations The DNA sequence can be changed due to single base changes, deletion/insertion of DNA segments, etc. Selection bias,3,The Tree of Life,Source: Alberts et al,4,Daprs Ernst Haeckel, 1891,Tree of life- a better picture,5,Primate evolution,A phylogeny is a tre
3、e that describes the sequence of speciation events that lead to the forming of a set of current day species; also called a phylogenetic tree.,6,Historical Note,Until mid 1950s phylogenies were constructed by experts based on their opinion (subjective criteria)Since then, focus on objective criteria
4、for constructing phylogenetic trees Thousands of articles in the last decadesImportant for many aspects of biology Classification Understanding biological mechanisms,7,Morphological vs. Molecular,Classical phylogenetic analysis: morphological features: number of legs, lengths of legs, etc.Modern bio
5、logical methods allow to use molecular features Gene sequences Protein sequencesAnalysis based on homologous sequences (e.g., globins) in different species,8,Topology based on Morphology,Archonta,Ungulata,(Based on Mc Kenna and Bell, 1997),9,Rat QEPGGLVVPPTDA Rabbit QEPGGMVVPPTDA Gorilla QEPGGLVVPPT
6、DA Cat REPGGLVVPPTEG,From Sequences to a Phylogenetic Tree,Different genes/proteins may lead to different phylogenetic trees,10,Rat QEPGGLVVPPTDA Rabbit QEPGGMVVPPTDA Gorilla QEPGGLVVPPTDA Cat REPGGLVVPPTEG,From sequences to a phylogenetic tree,There are many possible types of sequences to use (e.g.
7、 mitochondrial vs. nuclear proteins).,11,Topology1 , based on Mitochondrial DNA,(Based on Pupko et al.,),12,(tree by Madsenl),(Based on Pupko et al. slide),Topology2 ,based on Nuclear DNA,13,Theory of Evolution,Basic idea speciation events lead to creation of different species. Speciation caused by
8、physical separation into groups where different genetic variants become dominant Any two species share a (possibly distant) common ancestor,14,Phylogenenetic trees,Leafs - current day species Nodes - hypothetical most recent common ancestors Edges length - “time” from one speciation to the next,15,T
9、ypes of Trees,A natural model to consider is that of rooted trees,Common Ancestor,16,Types of trees,Unrooted tree represents the same phylogeny without the root node,Depending on the model, data from current day species often does not distinguish between different placements of the root.,17,Rooted v
10、ersus unrooted trees,a,b,c,Tree c,Represents all three rooted trees,18,Positioning Roots in Unrooted Trees,We can estimate the position of the root by introducing an outgroup: a set of species that are definitely distant from all the species of interest,Aardvark,Bison,Chimp,Dog,Elephant,Falcon,Propo
11、sed root,19,Dangers of Gene Duplication,Speciation events,Gene Duplication,1A,2A,3A,3B,2B,1B,If we happen to consider genes 1A, 2B, and 3A of species 1,2,3, we get a wrong tree that does not represent the phylogeny of the host species of the given sequences because duplication does not create new sp
12、ecies.,In the sequel we assume all given sequences are orthologs.,S,S,S,20,Types of Data,Distance-based Input is a matrix of distances between species. Can be fraction of residue they disagree on, or alignment score between them, etc. Character-based Input is a multiple sequence alignment. Sequences
13、 consist of characters (e.g., residues) that are examined separately.Genome/Proteome based Input is whole genome or proteome sequences. No MSA or obvious distance definition.,21,Tree Construction: Two Popular Methods,Distance Based- A weighted tree that realizes the distances between the objects (or
14、 gets close to it). Character Based A tree that optimizes an objective function based on all characters in input sequences (major methods are parsimony and likelihood).,We start with distance based methods, considering the following question: Given a set of species (leaves in a supposed tree), and d
15、istances between them construct a phylogeny which best “fits” the distances.,22,Exact solution: Additive sets,Given a set M of L objects with an LL distance matrix: d(i,i)=0, and for ij, d(i,j)0 d(i,j)=d(j,i).For all i,j,k it holds that d(i,k) d(i,j)+d(j,k).Can we construct a weighted tree which rea
16、lizes these distances?,23,Additive sets (cont),We say that the set M with L objects is additive if there is a tree T, L of its nodes correspond to the L objects, with positive weights on the edges, such that for all i,j, d(i,j) = dT(i,j), the length of the path from i to j in T. Note: Sometimes the
17、tree is required to be binary, and then the edge weights are required to be non-negative.,24,Three objects sets always additive:,For L=3: There is always a (unique) tree with one internal node.,Thus,25,How about four objects?,L=4: Not all sets with 4 objects are additive: e.g., there is no tree whic
18、h realizes the distances below.,26,The Four Points Condition,Theorem: A set M of L objects is additive iff any subset of four objects can be labeled i,j,k,l so that: d(i,k) + d(j,l) = d(i,l) +d(k,j) d(i,j) + d(k,l) We call i,j,k,l the “split” of i,j,k,l.,Proof: Additivity 4 Points Condition: By the
19、figure.,27,4P Condition Additivity:,Induction on the number of objects, L. For L 3 the condition is empty and tree exists. Consider L=4. B = d(i,k) +d(j,l) = d(i,l) +d(j,k) d(i,j) + d(k,l) = A,Let y = (B A)/2 0. Then the tree should look as follows: We have to find the distancesa,b, c and f.,a,b,i,j
20、,k,m,c,y,l,n,f,28,Tree construction for L=4,a,b,i,j,k,m,c,y,l,n,f,Construct the tree by the given distances as follows:Construct a tree for i, j,k, with internal vertex mAdd vertex n ,d(m,n) = yAdd edge (n,l), c+f=d(k,l),n,f,n,f,n,f,Remains to prove: d(i,l) = dT(i,l) d(j,l) = dT(j,l),29,Proof for L=
21、4,By the 4 points condition and the definition of y: d(i,l) = d(i,j) + d(k,l) +2y - d(k,j) = a + y + f = dT(i,l) (the middle equality holds since d(i,j), d(k,l) and d(k,j) are realized by the tree) d(j,l) = dT(j,l) is proved similarly.,30,Induction step for L4:,Remove Object L from the set By induct
22、ion, there is a tree, T, for 1,2,L-1. For each pair of labeled nodes (i,j) in T, let aij, bij, cij be defined by the following figure:,31,Induction step:,Pick i and j that minimize cij. T is constructed by adding L (and possibly mij) to T, as in the figure. Then d(i,L) = dT(i,L) and d(j,L) = dT(j,L)
23、Remains to prove: For each k i,j: d(k,L) = dT(k,L).,32,Induction step (cont.),Let k i,j be an arbitrary node in T, and let n be the branching point of k in the path from i to j. By the minimality of cij , i,j,k,L is not a “split” of i,j,k,L. So assume WLOG that i,L,j,k is a “split” of i,j, k,L.,33,I
24、nduction step (end),Since i,L,j,k is a split, by the 4 points condition d(L,k) = d(i,k) + d(L,j) - d(i,j) d(i,k) = dT(i,k) and d(i,j) = dT(i,j) by induction, and d(L,j) = dT(L,j) by the construction.Hence d(L,k) = dT(L,k). QED,34,From Additive Distance to a Tree,By following the proof, the four poin
25、t condition can be used to construct a tree from a distance matrix, or to decide that there is no such tree (namely that the distance is not additive).But this algorithm will go over all quartets, resulting in O(L4) many steps for L species (too sllllllllllllow).The most popular method for construct
26、ing trees for additive sets uses the neighbor joining approach.,35,Constructing additive trees: The neighbor joining problem,Let i, j be sisters (neighboring leaves) in a tree, let k be their father, and let m be any other vertex. Using eq. we can compute the distances from k to all other leaves. Th
27、is suggest the following method to construct tree from an additive distance matrix: Find sisters i,j in the tree, Replace i,j by their father, k, and recursively construct a tree T for the smaller set. Add i,j as children of k in T.,36,Neighbor Finding,How can we find from distances alone a pair of
28、sisters (neighboring leaves)? Closest nodes are not necessarily neighboring leaves.,Next, we show a way to find neighbors from distances.,37,Neighbor Finding: Seitou & Nei method,Theorem (Saitou&Nei) Assume d is additive, with all tree edge weights positive. If D(i,j) is minimal (among all pairs of
29、leaves), then i and j are sister taxa in the tree.,The proof is rather involved, and will be skipped (no tears pls).,38,Saitou & Nei proof (to be skipped),Notations used in the proof p(i,j) = the path from vertex i to vertex j; P(D,C) = (e1,e2,e3) = (D,E,F,C),For a vertex i, and an edge e=(i,j): Ni(
30、e) = |k : e is on p(i,k)|. ND(e1) = 3, ND(e2) = 2, ND(e3) = 1 NC(e1) = 1,E,F,39,A simpler neighbor finding method:,Select an arbitrary (fixed) node r. For each pair of labeled nodes (i,j) let C(i,j) be defined by the following expression (also see figure):,C(i,j),i,j,r,Claim: Let i, j be such that C
31、(i,j) is maximized. Then i and j are neighboring leaves.,40,Sisters Identification: Example,5,4,6,20,25,Select arbitrarily r=A. C(B,C)=(15+25-30)/2=5 C(B,D)=(15+34-31)/2=8 C(C,D)=(25+34-49)/2=5,Claim: Let i, j be such that C(i,j) is maximized. Then i and j are neighboring leaves.,41,Neighbor Joining
32、 Algorithm,Set M to contain all leaves, and select a root r. |M|=L If L =2, return a tree of two vertices Iteration: Choose i,j such that C(i,j) is maximal Create a new vertex k, and update distances remove i,j, and add k to M Recursively construct a tree on the smaller set. When done, add i,j as ch
33、ildren on k, at distances d(i,k) and d(j,k).,42,Complexity of Neighbor Joining Algorithm,Naive Implementation: Initialization: (L2) to compute the C(i,j)s. Each Iteration: O(L) to update C(i,k):i L for the new node k. O(L2) to find the maximal C(i,j). Total of O(L3).,43,Complexity of Neighbor Joinin
34、g Algorithm,Using a Heap to store the C(i,j)s: Initialization: (L2) to compute and heapify the C(i,j)s. Each Iteration: O(1) to find the maximal C(i,j). O(L log L) to delete C(m,i), C(m,j) and add C(m,k) for all vertices m. Total of O(L2 log L). (implementation details are omitted),44,Reconstructing
35、 Trees from Additive Matrices,A,C,1,B,1,1,2,2,D,E,3,3,Given a distance matrix constituting an additive metric, the topology of the corresponding additive tree is unique.,Q: Do we have to test additivity before running NJ? A: This would be bad news, as this takes O(L4) time!,45,Reconstructing Trees f
36、rom Additive Matrices,A,C,1,B,1,1,2,2,D,E,3,3,Q: Do we have to test additivity before running NJ? A: By Seito-Nei, if matrix is additive, NJ will construct the correct tree. Algorithm does not care about awareness and need not know anything about the matrix!,46,NJ Algorithm: Example,Identify i,j as
37、neighbours if their divergence is minimal.Combine i,j into a new node u.update the distance matrix.If only 3 nodes are left finish.,Let ri be the sum of distances from i to every other node,47,Distance Matrix,A,48,Distance Matrix,A,Y,C,49,Distance Matrix,A,Y,C,D,Z,50,Reconstructing Trees from non Ad
38、ditive Matrices,Q: What if the distance matrix is not additive? A: We could still run NJ!Q: But can anything be said about the resulting tree?A: Not really. Resulting tree topology could even vary according to way ties are resolved on the way.,51,Almost Additive Matrix,A distance matrix d is “almost
39、 additive” if there exists an additive matrix d such that,Atteson: If d is almost additive with respect to a tree T, then the output of NJ is a tree T with the same topology as T,52,Distance Matrix,53,Unrooted Tree - NJ,54,Output - NJ,Branch length is proportional to distance,55,N-J Method produces
40、an Unrooted, Additive tree,56,What is required for the Neighbour joining method?,Distance matrix,0. Distance Matrix,Neighbor-Joining Method An Example,57,PAM distance 3.3 (Human - Monkey) is the minimum. So well join Human and Monkey to MonHum and well calculate the new distances.,Mon-Hum,Monkey,Hum
41、an,Spinach,Mosquito,Rice,1. First Step,58,After we have joined two species in a subtree we have to compute the distances from every other node to the new subtree. We do this with a simple average of distances: DistSpinach, MonHum = (DistSpinach, Monkey + DistSpinach, Human)/2 = (90.8 + 86.3)/2 = 88.
42、55,Mon-Hum,Monkey,Human,Spinach,2. Calculation of New Distances,59,Human,Mosquito,Mon-Hum,Monkey,Spinach,Rice,Mos-(Mon-Hum),3. Next Cycle,60,Human,Mosquito,Mon-Hum,Monkey,Spinach,Rice,Mos-(Mon-Hum),Spin-Rice,4. Penultimate Cycle,61,Human,Mosquito,Mon-Hum,Monkey,Spinach,Rice,Mos-(Mon-Hum),Spin-Rice,(Spin-Rice)-(Mos-(Mon-Hum),5. Last Joining,62,Human,Monkey,Mosquito,Rice,Spinach,The result: Unrooted Neighbor-Joining Tree,
