1Computational GenomicsComputational GenomicsThe Coalescent ProcessThe Coalescent ProcessEric XingEric XingLecture 12, February 22, 2007DTW Chap 13Clusteringz How to label them ?z inferencez How many clusters ???z model selection ?z or inference ?2Genetic Demographyz Are there genetic prototypes among them ?z What are they ?z How many ? (how many ancestors do we have ?) z Inference done separately, or jointly?Multi-population Genetic Demography3Sir John Kingman, Head of the Isaac Newton Institute of Mathematical SciencesThe coalescentCoalescent Theoryz how we can build up a genealogical tree to relate a sample of n haploid individuals, collected in the present day?z The following series of slides shows how you can build up a genealogical tree to relate a sample of 22 individuals, collected in the present day, at a single haplotype locus (e.g. the non-recombining Y chromosome).z Because (for the Y chromosome) one son has only one father, but one father can have more than one son, coalescent events occur in the genealogy which inevitably result in a reduction of ancestors. Eventually, one ancestor remains – the Most Recent Common Ancestor (MRCA).4PresentTime22 individualsPresentTime22 individuals18 ancestors5PresentTime22 individuals18 ancestors16 ancestorsPresentTime22 individuals18 ancestors16 ancestors14 ancestors6PresentTime22 individuals18 ancestors16 ancestors14 ancestors12 ancestorsPresentTime22 individuals18 ancestors16 ancestors14 ancestors12 ancestors9 ancestors7PresentTime22 individuals18 ancestors16 ancestors14 ancestors12 ancestors9 ancestors8 ancestorsPresentTime22 individuals18 ancestors16 ancestors14 ancestors12 ancestors9 ancestors8 ancestors8 ancestors8PresentTime22 individuals18 ancestors16 ancestors14 ancestors12 ancestors9 ancestors8 ancestors8 ancestors7 ancestorsPresentTime22 individuals18 ancestors16 ancestors14 ancestors12 ancestors9 ancestors8 ancestors8 ancestors7 ancestors7 ancestors9PresentTime22 individuals18 ancestors16 ancestors14 ancestors12 ancestors9 ancestors8 ancestors8 ancestors7 ancestors7 ancestors5 ancestorsPresentTime22 individuals18 ancestors16 ancestors14 ancestors12 ancestors9 ancestors8 ancestors8 ancestors7 ancestors7 ancestors5 ancestors5 ancestors10PresentTime22 individuals18 ancestors16 ancestors14 ancestors12 ancestors9 ancestors8 ancestors8 ancestors7 ancestors7 ancestors5 ancestors5 ancestors3 ancestorsPresentTime22 individuals18 ancestors16 ancestors14 ancestors12 ancestors9 ancestors8 ancestors8 ancestors7 ancestors7 ancestors5 ancestors5 ancestors3 ancestors3 ancestors11PresentTime22 individuals18 ancestors16 ancestors14 ancestors12 ancestors9 ancestors8 ancestors8 ancestors7 ancestors7 ancestors5 ancestors5 ancestors3 ancestors3 ancestors3 ancestorsPresentTime22 individuals18 ancestors16 ancestors14 ancestors12 ancestors9 ancestors8 ancestors8 ancestors7 ancestors7 ancestors5 ancestors5 ancestors3 ancestors3 ancestors3 ancestors2 ancestors12PresentTime22 individuals18 ancestors16 ancestors14 ancestors12 ancestors9 ancestors8 ancestors8 ancestors7 ancestors7 ancestors5 ancestors5 ancestors3 ancestors3 ancestors3 ancestors2 ancestors2 ancestorsPresentTime22 individuals18 ancestors16 ancestors14 ancestors12 ancestors9 ancestors8 ancestors8 ancestors7 ancestors7 ancestors5 ancestors5 ancestors3 ancestors3 ancestors3 ancestors2 ancestors2 ancestors1 ancestor13PresentTimePresentTimeMost recent common ancestor(MRCA)14z Mutational events can now be added to the genealogical tree, resulting in polymorphic sites. If these sites are typed in the modern sample, they can be used to split the sample into sub-clades (represented by different colors)PresentTimemutationMost recent common ancestor(MRCA)TCGAGGTATTAACTCTAGGTATTAAC15PresentTimemutationMost recent common ancestor(MRCA)TCGAGGTATTAACTCTAGGTATTAACPresentTimeMost recent common ancestor(MRCA)TCGAGGTATTAACTCTAGGTATTAACTCGAGGCATTAAC16PresentTimeMost recent common ancestor(MRCA)TCGAGGTATTAACTCTAGGTATTAACTCGAGGCATTAACPresentTimeMost recent common ancestor(MRCA)TCGAGGTATTAACTCTAGGTATTAACTCGAGGCATTAACTCTAGGTGTTAAC17PresentTimeMost recent common ancestor(MRCA)TCGAGGTATTAACTCTAGGTATTAACTCGAGGCATTAACTCTAGGTGTTAACPresentTimeMost recent common ancestor(MRCA)TCGAGGTATTAACTCTAGGTATTAACTCGAGGCATTAACTCTAGGTGTTAACTCGAGGTATTAGC18PresentTimeMost recent common ancestor(MRCA)TCGAGGTATTAACTCTAGGTATTAACTCGAGGCATTAACTCTAGGTGTTAACTCGAGGTATTAGCPresentTimeMost recent common ancestor(MRCA)TCGAGGTATTAACTCTAGGTATTAACTCGAGGCATTAACTCTAGGTGTTAACTCGAGGTATTAGCTCTAGGTATCAAC19PresentTimeMost recent common ancestor(MRCA)TCGAGGTATTAACTCTAGGTATTAACTCGAGGCATTAACTCTAGGTGTTAACTCGAGGTATTAGCTCTAGGTATCAACPresentTimeMost recent common ancestor(MRCA)TCGAGGTATTAACTCTAGGTATTAACTCGAGGCATTAACTCTAGGTGTTAACTCGAGGTATTAGCTCTAGGTATCAAC* ** * *20The Statistical Modelsz To move beyond mere description, and to attempt such things as estimating the TMRCA (Time to Most Recent Common Ancestor) of the tree, it is necessary to adopt certain modelingassumptions.z For now lets forget about mutations, but just concern ourselves with the coalescenceKingman's coalescent processz Random collision of lineages as go back in timez Collision is faster the smaller the effective population sizez In a haplotype population of effective population size N,Average time for k copies to coalesce to k-1 copies:generations)( 12−=kkNAverage time for two copies to coalesce:= N generationsAverage time for n copies to coalesce:generations⎟⎠⎞⎜⎝⎛−=nN112Derivation? ---- Hw!21Hint of the derivationThe Wright-Fisher (WF) modelz The coalescent is descriptive, but not generative!z A classic generative model is the Wright-Fisher model. This is the canonical model of genetic drift in populations. It was invented in 1932 and 1930 by Sewall Wright and R. A. Fisher.z It starts with the following assumptions:z random mating and a random number of offspring (strictly, following a Poisson distribution)z no recombination (i.e. a single locus), z constant population size, z no selection,22The Wright-Fisher (WF) modelz It is a forwards-in-time model of a neutral locus in a constant-size, random-mating, haploid population evolving in discrete generations.z Each individual in generation t has a random number (possibly 0) of offspring in generation t+1. Each is:z identical to the parent with probability 1-µ;z otherwise a mutation occurs.z With WF, one can attempt such things as estimating the TMRCA (Time to Most Recent Common Ancestor) of the tree, etc.generation