CSE182-L18Perfect PhylogenyThe 4-gamete condition4 Gamete Condition4-gamete condition: proofAn algorithm for constructing a perfect phylogenyInclusion PropertyExampleSort columnsAdd first columnAdding other columnsUnrooted caseSummary :No recombination leads to correlation between sitesRecombinationStudying recombinationLinkage (Dis)-equilibrium (LD)Measuring LDLD can be used to map disease genesPopulation sub-structure can cause problems in disease gene mappingPopulation sub-structure can increase LDRecent ad-mixing of populationDetermining population sub-structureDetermining Population sub-structureIterative Algorithm for Population SubstructureIterative algorithm for population sub-structureSlide 26GoalAlgorithm:StructureSlide 29Slide 30Sampling ZSamplingPopulation StructureOther topicsncRNA gene findingtRNA structureRNA structure: BasicsRNA structure: pseudoknotsA Static picture of the cell is insufficientGene expressionTranscriptional machineryTF bindingTF binding sitesPowerPoint PresentationDiscovering TF binding sitesIdea1: Use orthologous genes from different speciesIdea2: MicroarrayPathwaysSummaryCSE182-L18Population GeneticsPerfect Phylogeny•Assume an evolutionary model in which no recombination takes place, only mutation.•The evolutionary history is explained by a tree in which every mutation is on an edge of the tree. All the species in one sub-tree contain a 0, and all species in the other contain a 1. Such a tree is called a perfect phylogeny.•How can one reconstruct such a tree?The 4-gamete condition•A column i partitions the set of species into two sets i0, and i1 •A column is homogeneous w.r.t a set of species, if it has the same value for all species. Otherwise, it is heterogenous.•EX: i is heterogenous w.r.t {A,D,E} iA 0B 0C 0D 1E 1F 1i0i14 Gamete Condition•4 Gamete Condition–There exists a perfect phylogeny if and only if for all pair of columns (i,j), either j is not heterogenous w.r.t i0, or i1.–Equivalent to–There exists a perfect phylogeny if and only if for all pairs of columns (i,j), the following 4 rows do not exist(0,0), (0,1), (1,0), (1,1)4-gamete condition: proof•Depending on which edge the mutation j occurs, either i0, or i1 should be homogenous.•(only if) Every perfect phylogeny satisfies the 4-gamete condition•(if) If the 4-gamete condition is satisfied, does a prefect phylogeny exist?i0i1iAn algorithm for constructing a perfect phylogeny•We will consider the case where 0 is the ancestral state, and 1 is the mutated state. This will be fixed later.•In any tree, each node (except the root) has a single parent.–It is sufficient to construct a parent for every node.•In each step, we add a column and refine some of the nodes containing multiple children.•Stop if all columns have been considered.Inclusion Property•For any pair of columns i,j–i < j if and only if i1  j1 •Note that if i<j then the edge containing i is an ancestor of the edge containing iijExample 1 2 3 4 5A 1 1 0 0 0B 0 0 1 0 0C 1 1 0 1 0D 0 0 1 0 1E 1 0 0 0 0rAB C D EInitially, there is a single clade r, and each node has r as its parentSort columns•Sort columns according to the inclusion property (note that the columns are already sorted here).•This can be achieved by considering the columns as binary representations of numbers (most significant bit in row 1) and sorting in decreasing order 1 2 3 4 5A 1 1 0 0 0B 0 0 1 0 0C 1 1 0 1 0D 0 0 1 0 1E 1 0 0 0 0Add first column•In adding column i–Check each edge and decide which side you belong.–Finally add a node if you can resolve a claderABCDE 1 2 3 4 5A 1 1 0 0 0B 0 0 1 0 0C 1 1 0 1 0D 0 0 1 0 1E 1 0 0 0 0uAdding other columns•Add other columns on edges using the ordering propertyrEBCDA 1 2 3 4 5A 1 1 0 0 0B 0 0 1 0 0C 1 1 0 1 0D 0 0 1 0 1E 1 0 0 0 012435Unrooted case•Switch the values in each column, so that 0 is the majority element. •Apply the algorithm for the rooted caseSummary :No recombination leads to correlation between sites0 0 0 0 0 0 0 00 0 1 0 0 0 0 00 0 1 0 0 0 0 10 0 1 0 1 0 0 0385•The different sites are linked. A 1 in position 8 implies 0 in position 5, and vice versa.•The history of a population can be expressed as a tree.•The tree can be constructed efficientlyA BRecombination•A tree is not sufficient as a sequence may have 2 parents•Recombination leads to violation of 4 gamete property.•Recombination leads to loss of correlation between columns000000001111111100011111Studying recombination•A tree is not sufficient as a sequence may have 2 parents•Recombination leads to loss of correlation between columns•How can we measure recombination?Linkage (Dis)-equilibrium (LD)Extensive Recombination–Pr[A,B=(0,1)=0.125•Linkage equilibriumA B0 10 10 00 01 01 01 01 0No recombination–Pr[A,B=0,1] = 0.25•Linkage disequilibriumA B0 00 10 00 01 11 01 01 0Measuring LD•Consider two bi-allelic sites A and B, with values 0 and 1.•Let p1 = probability[individual has allele 1 in site A]•q1 = probability[individual has allele 1 in site B]•P11 = Prob [individual has allele 1 in site A, and B]•Linkage Disequilibrium, D = |P11-p1q1| = |P01-p0q1| =….•If D=0, sites are uncorrelated, (are in linkage equilibrium)•If |D| >>0, sites are highly correlated (have high LD)•Other measures exist, but they all measure similar quantities.LD can be used to map disease genes•LD decays with distance from the disease allele.•By plotting LD, one can short list the region containing the disease gene.011001DNNDDNLDPopulation sub-structure can cause problems in disease gene mappingPopulation sub-structure can increase LD•Consider two populations that were isolated and evolving independently. •They might have different allele frequencies in some regions.•Pick two regions that are far apart (LD is very low, close to 0)0 .. 10 .. 10 .. 01 .. 10 .. 10 .. 10 .. 10 .. 10 .. 11 .. 01 .. 00 .. 01 .. 11 .. 01 .. 01 .. 01 .. 01 .. 0Pop. APop. Bp1=0.1q1=0.9P11=0.1D=0.01p1=0.9q1=0.1P11=0.1D=0.01Recent ad-mixing of population•If the populations came together recently (Ex: African and European population), artificial LD might be created.•D = 0.15 (instead of 0.01), increases 10-fold•This spurious LD might lead one false associations•Other genetic events can cause LD to arise, and one needs to be careful0 .. 10 .. 10 .. 01 .. 10 .. 10 .. 10 .. 10 .. 10 .. 11 .. 01 .. 00 .. 01 .. 11 .. 01 .. 01 .. 01 .. 01 .. 0Pop.