Physical networks active learning10-810 /02-710Computational GenomicsGRAMModules• Gene Module– Set of genes that are co-regulated and co-expressed.• Functional Module– Collection of gene modules with related function.Modules provide an abstraction which reduces genetic network complexity without significant loss of explanatory power, and allows us to determine the significance of the model.Genetic RegulAtory Modules (GRAM)GRAM Algorithm Overview• For each regulator combination, look at all genes bound (using a strict binding p-value).• Find a core gene expression profile.• Remove genes far away from core.• Add genes close to the core (with relaxed p-value threshold).Results:RichMediaModulesBar-Joseph et al Nature Biotechnology 2003Binding p-values form a continuum – where do you draw the cut-off line?99 genes bound by Hap4 with a p-value < .01 28 genes were selected by the GRAM algorithm; all are involved in respiration. Six of these genes (PET9, ATP16, KGD2, QCR6, SDH1, and NDI1) would not have been identified as Hap4 targets using the stringent .001 p-value threshold (p-values range from .0011 to .0036).The Importance of Information Fusion:Using Only BindingThe Importance of Information Fusion: Using Only ExpressionA cluster of amino acid synthesis genesEleven Significant Activators Found; Ten Previously Identified in LiteratureActivator of heat shock related genes+0.36Stress responseHsf1Activator of cell cycle genes+0.37Cell cycleFkh2Activator, involved in stress response+0.38Stress responseMsn4Activator of cell cycle genes+0.39Cell cycleSwi6Activator, regulation of amino acid synthesis+0.40Energy and metabolismAro80Activator, involved in multi-drug resistance+0.47DetoxificationCad1Activator of cell cycle genes+0.49Cell cycleFkh1Previously identified as a repressor+0.50 Carbohydrate transportNrg1Activator, possibly involved in oxidative stress response+0.53DetoxificationYap1Activator of CCAAT box containing genes+0.60RespirationHap4Activator, required for pheromone response+0.64Pheromone responseSte12CommentsCorrelationModule functionFactorValidation Ideas• Literature.• Curated databases (e.g., GO/MIPS/TRANSFAC).• Other high throughput data sources.• “Randomized” versions of data.• New experiments.GRAM Network Validation• Literature:– Many TF interactions predicted by modules corresponded well to literature (but what about ones that didn’t…)• Curated databases:– Computed enrichment for genes in modules for MIPS categories using the hypergeometric distribution. – Modules belong to diverse array of categories corresponding to cellular processes such as amino acid biosynthesis, carbohydrate and fatty acid metabolism, respiration, ribosome biogenesis, stress response, protein synthesis, fermentation, and the cell cycle.• “Randomized” data:– When compared to results generated using binding data alone, there was 3-fold increase in modules significantly enriched in MIPS categories.Predicting Mechanisms of Transcription Factors RegulationCluster 33 regs: HIR1 YPD | HIR2 YPD | Rsc8 avg corr: 0.81661 YBR009C HHF1 histone H YBR010WHHT1 histone H YDR224C HTB1 histone H2 YDR225WHTA1 histone H2 40.10.03 chromosome (44 ORFs) 2.52E-09 44 404.05.01.04 transcriptional control (334 ORFs) 9.44E-06 334 404.05.01 mRNA synthesis (406 ORFs) 2.07E-05 406 4Combinatorial regulationWT swi4∆100swi5∆swi6∆swi6∆mbp∆mbp∆hir1∆hir2∆Rsc8 at HTA1TFIIB at HTA1Rsc8 at SOD1500150200250Ng et al, Genes Dev. 2002Cluster 9 regs: STB1 YPD | SWI4 YPD p-valueavg corr: 0.62927 YCR065WHCM1 HCM1 G1 0.0012YDR501WYDR501WYDR501WG1 0.00002YGR109C CLB6 CLB6 G1 0.0013YGR221C YGR221C YGR221C G1 0.0009YIL140W SRO4 SRO4 G1 0.008YIL141W YIL141W YIL141W G1 0.008YMR179WSPT21 SPT21 G1 0.007YNL289W PCL1 PCL1 G1 0.000005YPL256C CLN2 CLN2 G1 0.00007Binding PredictionsConnection to Sequence DataWhat is the percentage of genes bound by factors with known motifs that contain the motif ?Results:RichMediaModulesSub-Network Discovery• Identify genes involved in the system.• Identify the factors controlling the system, and the modules involved.• Determine a dynamic model for the activation of the modules by the identified factors. We extend GRAM and combine it with our continuous representation and alignment algorithms to construct a dynamic model for a sub-networkp-value: 10-4p-value: 0.2 p-value: 0.7 p-value: 10-6Factors = {F1,F2,F6} Genes = {g1,g2,g4,g13,g14,g15,g22,g24}Sub-Networks Discovery Algorithmg4g3g2g1F1, F2g4g3g7g6F1, F4g12g11g10g9F3, F5g15g14g13g1F6, F21.g13g1F2g2F1F1, F2g4F6F1g15g14F2, F62.Blue boxes: gene modulesAssembly of the Cell Cycle TranscriptionalRegulatory NetworkBlue boxes: gene modulesAssembly of the Cell Cycle TranscriptionalRegulatory NetworkIndividual regulators:ovals, connected to their modulesDashed line: extends from module encoding a regulator to the regulator protein ovalLee et al Science 2002Results for the Fkh1/2 KnockoutWTKnockoutBar-Joseph et al PNAS 2003Blue boxes: gene modulesAssembly of the Cell Cycle TranscriptionalRegulatory NetworkIndividual regulators:ovals, connected to their modulesDashed line: extends from module encoding a regulator to the regulator protein oval0841 3217Physical networksData integrationGene expressionProtein interactionsProtein-DNA bindingYeast mating pathway• A graph depicting physical interactions and functional annotations.A mechanistic model of gene regulation• Physical data:- Yeast binding data - DIP database (PPI)• Functional data:- Rosetta compendium knockout dataInferring the mechanistic model from observed dataKey question: How do we construct the model from known mechanisms and constraints from observed data?• Decompose data into pairwise items.• Construct potential functions specifying constraints of each item.• Combine potential functions by multiplication.Requirements to explain knock-out data• There is at least one connecting path.Requirements to explain knock-out data• There is at least one connecting path.• Edge directions along the path are consistent with the knock-out effect.Requirements to explain knock-out data• There is at least one connecting path.• Edge directions along the path are consistent with the knock-out effect.• The last edge on each path is a protein-DNA edge.Requirements to explain knock-out data• There is at least one connecting path.• Edge directions along the path are consistent with the knock-out effect.• The last edge on