1Gene Regulation and Gene Regulation and MicroarraysMicroarrays…after which we come back to multiple alignments for finding regulatory motifsOverview• A. Gene Expression and Regulation• B. Measuring Gene Expression: Microarrays• C. Finding Regulatory MotifsA. Regulation of Gene ExpressionCells respond to environmentHeatFoodSupplyResponds toenvironmentalconditionsVarious external messagesGenome is fixed – Cells are dynamic• A genome is static– Every cell in our body has a copy of same genome• A cell is dynamic– Responds to external conditions– Most cells follow a cell cycle of division• Cells differentiate during developmentGene regulation• … is responsible for the dynamic cell• Gene expression varies according to:– Cell type– Cell cycle– External conditions– Location2Where gene regulation takes place• Opening of chromatin• Transcription• Translation• Protein stability• Protein modificationsTranscriptional Regulation• Strongest regulation happens during transcription• Bestplace to regulate: No energy wasted making intermediate products• However, slowest response timeAfter a receptor notices a change:1. Cascade message to nucleus2. Open chromatin & bind transcription factors3. Recruit RNA polymerase and transcribe4. Splice mRNA and send to cytoplasm5. Translate into proteinTranscription Factors Binding to DNATranscription regulation:Certain transcription factors bind DNABinding recognizes DNA substrings:Regulatory motifsPromoter and Enhancers• Promoter necessary to start transcription• Enhancers can affect transcription from afarRegulation of GenesGeneRegulatory ElementRNA polymerase(Protein)Transcription Factor(Protein)DNARegulation of GenesGeneRNA polymeraseTranscription Factor(Protein)Regulatory ElementDNA3Regulation of GenesGeneRNA polymeraseTranscription FactorRegulatory ElementDNANew proteinExample: A Human heat shock protein• TATA box: positioning transcription start• TATA, CCAAT: constitutive transcription• GRE: glucocorticoid response• MRE: metal response• HSE: heat shock elementTATASP1CCAAT AP2HSEAP2CCAATSP1promoter of heat shock hsp700--158GENEThe Cell as a Regulatory Network• Genes = wires• Motifs = gatesA B Make DCIf C then DIf B then NOT DIf A and B then DDMake BDIf D then BCgene Dgene BThe Cell as a Regulatory Network (2)B. DNA MicroarraysMeasuring gene transcription in a high-throughput fashionWhat is a microarray4What is a microarray (2)• A 2D array of DNA sequences from thousands of genes• Each spot has many copies of same gene• Allow mRNAs from a sample to hybridize• Measure number of hybridizations per spotHow to make a microarray• Method 1: Printed Slides (Stanford)– Use PCR to amplify a 1Kb portion of each gene– Apply each sample on glass slide• Method 2: DNA Chips (Affymetrix)– Grow oligonucleotides(20bp) on glass– Several words per gene (choose unique words)If we know the gene sequences,Can sample all genes in one experiment!Goal of Microarray Experiments• Measure level of gene expression across many different conditions:– Expression Matrix M: {genes}×{conditions}:Mij= |genei| in conditionj• Deduce gene function• Deduce gene regulatory networks – parts and connections-level description of biologySteps Towards Achieving this Goal1. Removing noise from gene expression levels2. Feature Extraction3. Clustering of genes/conditions4. Analysisa. Statistical significance of clustersb. Finding regulatory sequence motifsc. Building regulatory networksd. Experimental verification1. Removing Noise from Gene Expression Levels• Expression levels vary with time, labs, concentrations, chemicals used• Noise model: Mij= ci(aijgiTi+ εij)– Mij, Tij: observed and true level genej,chipi– gi, cj: mult. error constant for genei, chipj– aij, εij: error terms• Parameter Estimation– cj: spike in control probes– gi: control experiment of known concentration– εij, aij: minimize according to normal distribution2. Feature Extraction• Sample Correlation– Expression level can be different, but genes related; or similar, but genes unrelated• Select most relevant features– In clustering genes, most meaningful chips– In clustering conditions, most meaningful genes∑ ∑∑= ==−−−−=chipsichipsiiichipsiiiyyxxyyxxyxs#1#122#1)ˆ()ˆ()ˆ)(ˆ(),(53. Clustering of Genes and Conditions• Unsupervised:– Hierarchical clustering– K-means clustering– Self Organizing Maps (SOMs)– Singular Value Decomposition (SVD)• Supervised: – Support Vector MachinesCould be useful to separate patient from non-patient genes and samplesResults of Clustering Gene Expression• Human tumor patient and normal cells; various conditions• Cluster or Classifygenes according to tumors• Cluster tumors according to genes4. Analysis of Clustered Data• Statistical Significance of Clusters• Regulatory motifs responsible for common expression• Regulatory Networks• Experimental VerificationC. Finding Regulatory MotifsC. Finding Regulatory MotifsTiny Multiple Local Alignments of Many SequencesFinding Regulatory MotifsGivena collection of genes with common expression,Findthe TF-binding motif in common...Characteristics of Regulatory Motifs• Tiny• Highly Variable• ~Constant Size– Because a constant-size transcription factor binds• Often repeated• Low-complexity-ish6Problem DefinitionProbabilisticMotif: Mij; 1 ≤ i ≤ W1 ≤ j ≤ 4Mij= Prob[ letter i, pos j ]Find best M, and positions p1,…, pNin sequencesCombinatorialMotif M: m1…mWSome of the mi’s blankFind M that occurs in all siwith ≤ k differencesGiven a collection of promoter sequences s1,…, sNof genes with common expressionEssentially a Multiple Local Alignment• Find“best” multiple local alignmentAlignment score defined differently in probabilistic/combinatorial cases...Algorithms• Probabilistic1. Expectation Maximization:MEME2. Gibbs Sampling: AlignACE, BioProspector• CombinatorialCONSENSUS, TEIRESIAS, SP-STAR, othersDiscrete Approaches to Motif FindingDiscrete FormulationsGiven sequences S = {x1, …, xn}• A motif W is a consensus string w1…wK• Find motif W*with “best” match to x1, …, xnDefinition of “best”:d(W, xi) = min hamming dist. between W and a word in xid(W, S) = Σid(W, xi)Approaches• Exhaustive Searches• CONSENSUS• MULTIPROFILER, TEIRESIAS, SP-STAR, WINNOWER7Exhaustive SearchesPattern-driven algorithm:For W = AA…A to TT…T
View Full Document
Unlocking...