1Eric Xing 1Machine LearningMachine Learning1010--701/15701/15--781, Spring 2008781, Spring 2008Machine Learning in Machine Learning in Computational BiologyComputational BiologyEric XingEric XingLecture 20, April 7, 2008Reading: Eric Xing 2The Central Dogma2Eric Xing 3AACCGGTTGenome and ProteomeEric Xing 4Gene Structure in DNAz The inference problem: predicting locations of the genes on DNA3Eric Xing 5DNA proteingenetic code*Proteins are coded by DNAz There are between 30,000 to 40,000 genes in the human genomez The human gene inventory corresponds to ~1.5% of the genome (coding regions)Eric Xing 6Protein Structure Hierarchyz The inference problem: predicting the structures from sequences APAFSVSPASGACGPECA4Eric Xing 7Genetic PolymorphismsEric Xing 8Genetic Demographyz Are there genetic prototypes among them ?z What are they ?z How many ? (how many ancestors do we have ?)5Eric Xing 9ZXA AA AX2X3X1XTY2Y3Y1YT... ... AGAGACComputation Biology and MLz Mixture and infinite mixturez clustering of genetic polymorphisms z Hidden Markov Modelsz gene findingz Treesz sequence evolutionz Conditional Random Fieldsz protein structure predictionEric Xing 10ZXComputation Biology and MLz Mixture and infinite mixture z clustering of genetic polymorphismsz HMMsz gene findingz Treesz sequence evolutionz CRMsz protein structure prediction6Eric Xing 11Biological Terms– Each variant is called an “allele”– Almost always bi-allelic– Account for most of the genetic diversity among different (normal) individuals, e.g. drug response, disease susceptibilityz Genetic polymorphism: a difference in DNA sequence among individuals, groups, or populationsz Single Nucleotide Polymorphism (SNP): DNA sequence variation occurring when a single nucleotide - A, T, C, or G -differs between members of the speciesEric Xing 12From SNPs to Haplotypesz Alleles of adjacent SNPs on a chromosome form haplotypesz Useful in the study of disease association or genetic evolution7Eric Xing 13CTATGACGATTA??????Haplotype h≡(h1, h2)possible associations of alleles to chromosomeA heterozygousdiploid individualCTATGACpCm• This is a mixture modeling problem!The Genotype:pairs of alleles with association of alleles to chromosomes unknownATGCsequencingTC TG AAPhase ambiguity of SNPs "haplotypes"Eric Xing 14Haplotype InferenceWhy is it approachable?z Many of the haplotypes appear many timesz Data for many individuals allows inferenceT G T C GA C T A TA G T A TA C C C TA/T C/G T/T A/C G/TA G T C TT C T A G A G T C TA C C A TA/A C/G C/T A/C T/TSolution seems ‘better’ since it uses fewer haplotypes8Eric Xing 15z The probability of a genotype g:z Standard settings:z p(h1,h2)= p(h1)p(h2) Hardy-Weinberg equilibriumz |H| = K fixed-sized population haplotype poolz Problem: K ? H ?∑∈=H21,2121),|(),()(hhhhgphhpgpGenotypingmodelHaplotypemodelPopulation haplotypepoolGnHn1Hn2Finite mixture modelEric Xing 16Ancestral Inferencez Better recovery of the ancestors leads to better haplotyping results (because of more accurate grouping of common haplotypes)z True haplotypes are obtainable with high cost, but they can validate model more subjectively (as opposed to examining saliency of clustering)z Many other biological/scientific utilities GnHn1Hn2Akθk?NNEssentially a clustering problem, but Essentially a clustering problem, but ……9Eric Xing 17Being Bayesian about ...z Population haplotype identitiesz Population haplotype frequenciesz Number of population haplotypes z Associations between population haplotype and individual haplotype/genotypeEric Xing 18A Hierarchical Bayesian Infinite Allele model).},{|(~kahphθ• Assume an individual haplotype h is stochastically derived from a population haplotypeakwith nucleotide-substitution frequencyθk: • Not knowing the correspondences between individual and population haplotypes, each individual haplotype is a mixture of population haplotypes.• The number and identity of the population haplotypes are unknown− use a Dirichlet Process to construct a prior distribution G on H´×RJ.• Inference: Markov Chain Monte CarloGnHn1Hn2Akθk∞GτG0Bayesian Haplotype Inference via the Dirichlet Process (Xing et al. ICML2004)10Eric Xing 19Chinese Restaurant ProcessCRP defines an exchangeable distribution on partitions over an (infinite) sequence of integers =)|=(-iikcP c100α+110αα+1α+21α+21αα+2α+31α+32αα+31-+1αim1-+2αim1-+ααi....1θ2θEric Xing 20{A,θ} {A,θ} {A,θ} {A,θ} {A,θ} {A,θ}……31245678 9The DP Mixture of Ancestral Haplotypesz The customers around a table form a clusterz associate a mixture component (i.e., a population haplotype) with a table z sample {a,θ} at each table from a base measure G0to obtain the population haplotype and nucleotide substitution frequency for that componentz With p(h|{Α, θ}) and p(g|h1,h2), the CRP yields a posterior distribution on the number of population haplotypes (and on the haplotype configurations and the nucleotide substitution frequencies)11Eric Xing 21Convergence of Ancestral InferenceEric Xing 22Results on simulated dataz DP vs. Finite Mixture via EM00.050.10.150.20.250.30.350.40.4512345data setsindividual error Series1Series2DPEM12Eric Xing 23ResultsThe Gabriel dataThe Gabriel dataEric Xing 24Population structurez DATA: 256 European individuals with 103 lociPopulation Structure13Eric Xing 25Computation Biology and MLz Mixture and infinite mixture z clustering of genetic polymorphismsz HMMsz gene findingz Treesz sequence evolutionz CRMsz protein structure predictionA AA AX2X3X1XTY2Y3Y1YT... ... Eric Xing 26cacatcgctgcgtttcggcagctaattgccttttagaaattattttcccatttcgagaaactcgtgtgggatgccggatgcggctttcaatcacttctggcccgggatcg gattgggtcacattgtctgcgggctctattgtctcgatccgcggcgcagttcgcgtgcttagcggtcagaaaggcagagattcggttcggattgatgcgctggcagcagggcacaaagatctaatgactggcaaatcgctacaaataaatta aagtccggcggctaattaatgagcggactgaagccactttggattaaccaaaaaacagcagataaacaaaaacggcaaagaaaattgccacagagttgtcacgctttgttgcacaaacatttgtgcagaaaagtgaaaagcttttagccatt attaagtttttcctcagctcgctggcagcacttgcgaatgtactgatgttcctcataaatgaaaattaatgtttgctctacgctccaccgaactcgcttgtttgggggattggctggctaatcgcggctagatcccaggcggtataaccttt tcgcttcatcagttgtgaaaccagatggctggtgttttggcacagcggactcccctcgaacgctctcgaaatcaagtggctttccagccggcccgctgggccgctcgcccactggaccggtattcccaggccaggccacactgtaccgcacc gcataatcctcgccagactcggcgctgataaggcccaatgtcactccgcaggcgtctatttatgccaaggaccgttcttcttcagctttcggctcgagtatttgttgtgccatgttggttacgatgccaatcgcggtacagttatgcaaatg
View Full Document
Unlocking...