Phylogentic Tree ConstructionWhat is evolution?Some Conventional Tools For Evolutionary StudiesEvolutionary StudiesSuccess Story 1: the Giant Panda RiddleEvolutionary Tree of Bears and RaccoonsSuccess Story 2: Out of Africa HypothesisHuman Evolutionary Tree (cont’d)How to construct such a tree?Basic Idea: Sequence Similarity -> Evolution TimeSim(Human, Mouse) > Sim(Human, Chicken)Beta Globin Phylogenetic TreePhylogenetic Tree Construction MethodsEvolutionary TreesRooted and Unrooted TreesDistances in TreesDistance in Trees: an ExampeDistance MatrixFitting Distance MatrixReconstructing a 3 Leaved TreeReconstructing a 3 Leaved Tree (cont’d)Trees with > 3 LeavesAdditive Distance MatricesHow do we know if a distance matrix is additive?The Four Point Condition (cont’d)The Four Point Condition: TheoremDistance Based Phylogeny ProblemNeighboring LeavesFinding Neighboring LeavesSlide 30Slide 31Neighbor Joining AlgorithmNeighbor-JoiningNeighbor-Joining: ExampleNeighbor-Joining: Example (cont.)UPGMA: Unweighted Pair Group Method with Arithmetic MeanUPGMA’s Weakness: ExampleLeast Squares Distance Phylogeny ProblemAlignment Matrix vs. Distance MatrixCharacter-Based Tree ReconstructionCharacter-Based Tree Reconstruction (cont’d)Maximum ParsimonySlide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Small Parsimony ProblemWeighted Small Parsimony ProblemSankoff’s AlgorithmSlide 54Fitch’s AlgorithmFitch’s Algorithm (cont’d)Probabilistic ApproachesDetailed View of Probabilistic ModelsThe Jukes-Cantor modelComputing the LikelihoodHandling the Hidden NodesMaximizing the LikelihoodMore realistic evolutionary modelsWhat You Should KnowPhylogentic Tree Construction (Lecture for CS498-CXZ Algorithms in Bioinformatics) Nov. 29, 2005ChengXiang ZhaiDepartment of Computer ScienceUniversity of Illinois, Urbana-ChampaignWhat is evolution?•A process of change in a certain direction (Merriam – Webster Online).•In Biology: The process of biological and organic change in organisms by which descendants come to differ from their ancestor (Mc GRAW –HILL Dictionary of Biological Science).•Charles Darwin first developed the Evolution idea in detail in his well-known book On the Origin of Spieces published in 1859.Some Conventional Tools For Evolutionary Studies•Fossil Record: some of the biota found in a given stratum are the descendants of those in the previous stratum.•Morphological Similarity: similar species are found to have some similar anatomical structure; For example: horses, donkeys and zebras.•Embryology: embryos of related kinds of animals are astoundingly similar.Evolutionary Studies•Early approaches–Based on anatomical features –Subjective derivation of evolutionary relationships •Some of them were later proved incorrect•Modern approaches–Based on DNA–Objective derivation of evolutionary relationshipsSuccess Story 1:the Giant Panda Riddle•For roughly 100 years scientists were unable to figure out which family the giant panda belongs to•Giant pandas look like bears but have features that are unusual for bears and typical for raccoons, e.g., they do not hibernate•In 1985, Steven O’Brien and colleagues solved the giant panda classification problem using DNA sequences and algorithmsEvolutionary Tree of Bears and RaccoonsSuccess Story 2: Out of Africa Hypothesis•Around the time the giant panda riddle was solved, a DNA-based reconstruction of the human evolutionary tree lead to the Out of Africa Hypothesis:–Claims our most ancient ancestor lived in Africa roughly 200,000 years agoHuman Evolutionary Tree (cont’d)http://www.mun.ca/biology/scarr/Out_of_Africa2.htmHow to construct such a tree?Basic Idea: Sequence Similarity -> Evolution Time•Beta globin chains of closely related species are highly similar:•Observe simple alignments below:Human β chain: MVHLTPEEKSAVTALWGKV NVDEVGGEALGRLLMouse β chain: MVHLTDAEKAAVNGLWGKVNPDDVGGEALGRLLHuman β chain: VVYPWTQRFFESFGDLSTPDAVMGNPKVKAHGKKVLGMouse β chain: VVYPWTQRYFDSFGDLSSASAIMGNPKVKAHGKK VINHuman β chain: AFSDGLAHLDNLKGTFATLSELHCDKLHVDPENFRLLGN Mouse β chain: AFNDGLKHLDNLKGTFAHLSELHCDKLHVDPENFRLLGNHuman β chain: VLVCVLAHHFGKEFTPPVQAAYQKVVAGVANALAHKYHMouse β chain: MI VI VLGHHLGKEFTPCAQAAFQKVVAGVASALAHKYH There are a total of 27 mismatches, or (147 – 27) / 147 = 81.7 % identicalSim(Human, Mouse) > Sim(Human, Chicken)Human β chain: MVH L TPEEKSAVTALWGKVNVDEVGGEALGRLLChicken β chain: MVHWTAEEKQL I TGLWGKVNVAECGAEALARLLHuman β chain: VVYPWTQRFFESFGDLSTPDAVMGNPKVKAHGKKVLGChicken β chain: IVYPWTQRFF ASFGNLSSPTA I LGNPMVRAHGKKVLTHuman β chain: AFSDGLAHLDNLKGTFATLSELHCDKLHVDPENFRLLGN Chicken β chain: SFGDAVKNLDNIK NTFSQLSELHCDKLHVDPENFRLLGDHuman β chain: VLVCVLAHHFGKEFTPPVQAAY QKVVAGVANALAHKYHChicken β chain: I L I I VLAAHFSKDFTPECQAAWQKLVRVVAHALARKYH-There are a total of 44 mismatches, or (147 – 44) / 147 = 70.1 % identicalBeta Globin Phylogenetic TreePhylogenetic Tree Construction Methods •All related to clustering•Similarity/distance based –Start with known distances between species–Bottom up construction–Criteria: Molecular clock vs. Additivity•Maximum parsimony –Start with some alignment of sequences–Character-based –Search for the right tree–Criteria: Minimize mutations •Probabilistic models–Start with a model for evolution–Reduct the tree construction problem to a model estimation problemToday’s lectureEvolutionary Trees•Leaves represent existing species•Internal vertices represent ancestors•Rooted trees:–Root represents the oldest evolutionary ancestor–Can be viewed as directed trees from the root to the leaves•Unrooted trees:–The position of the root (“oldest ancestor”) is unknown. –Otherwise, they are like rooted treesRooted and Unrooted TreesDistances in Trees•Edges may have weights reflecting:–Number of mutations on evolutionary path from one species to another –Time estimate for evolution of one species into another (molecular clock)•In a tree T with n leaves, we often compute the length of a path between leaves i and j, dij(T)–dij(T) refers to the the distance between i and j (sum of the weight of the edges on the path from i to j in the tree T)Distance in Trees: an ExampeFor i = 1, j = 4, dij is:di,j = 12 + 13 + 14 + 17 + 12 = 68ijDistance Matrix•Given n species, we can compute the n x n distance matrix Dij•Dij may be defined as the edit distance between a gene in
View Full Document
Unlocking...