06_多序列比对(3).pdf

1 Copyright 2010 College of Life Science Capital Normal University 6 多序列比对 3 Multiple Sequence Alignment MSA Copyright 2010 College of Life Science Capital Normal University Outline MSA programs Web logo MEME 2 Copyright 2010 College of Life Science Capital Normal University 1 Web logo Crooks GE Hon G Chandonia JM Brenner SE WebLogoWebLogo A sequence logo generator A sequence logo generator Genome Research 14 1188 1190 2004 Schneider TD Stephens RM 1990 Sequence Sequence Logos A New Way to Display Consensus Logos A New Way to Display Consensus SequencesSequences Nucleic Acids Res 18 6097 6100 Copyright 2010 College of Life Science Capital Normal University 3 Copyright 2010 College of Life Science Capital Normal University Copyright 2010 College of Life Science Capital Normal University 4 Copyright 2010 College of Life Science Capital Normal University Copyright 2010 College of Life Science Capital Normal University 5 Copyright 2010 College of Life Science Capital Normal University Entropy From information theory a measure of the unpredictable nature of a set of possible elements The higher the level of variation within the set the higher the entropy Shannon C E 1948 Bell System Tech J 27 379 423 623 656 Copyright 2010 College of Life Science Capital Normal University Entropy where K is a positive constant Shannon C E 1948 Bell System Tech J 27 379 423 623 656 6 Copyright 2010 College of Life Science Capital Normal University Creation of Logos 1 TACGAT TATAAT TATAAT GATACT TATGAT TATGTT H 1 f T 1 log2f T 1 f G 1 log2 G 1 5 6 log2 5 6 1 6 log2 1 6 0 8333 0 2630 0 1666 2 585 0 2192 0 4307 0 6499 Copyright 2010 College of Life Science Capital Normal University Creation of Logos 2 TACGAT TATAAT TATAAT GATACT TATGAT TATGTT 7 Copyright 2010 College of Life Science Capital Normal University Creation of Logos 3 TACGAT TATAAT TATAAT GATACT TATGAT TATGTT Copyright 2010 College of Life Science Capital Normal University 2 MEME MMultiple E Em for MMotif E Elicitation http meme sdsc edu meme4 3 0 intro html References Timothy L Bailey Nadya Williams Chris Misleh and Wilfred W Li MEME discovering and analyzing DNA and protein sequence motifs Nucleic Acids Research Vol 34 pp W369 W373 2006 Timothy L Bailey and Charles Elkan Fitting a mixture model by expectation maximization to discover motifs in biopolymers Proceedings of the Second International Conference on Intelligent Systems for Molecular Biology pp 28 36 AAAI Press Menlo Park California 1994 8 Copyright 2010 College of Life Science Capital Normal University Expectation Maximization Algorithm The EM algorithm consists of two steps which are repeated consecutively Step 1 the expectation step Step 2 the maximization step Copyright 2010 College of Life Science Capital Normal University An example Suppose that there are 10 DNA sequences having very little similarity with each other each about 20 nucleotides long and thought to contain a binding site near the middle 4 residues based on biochemical and genetic evidence To find the most probable location of the binding sites in each of the 10 sequences 9 Copyright 2010 College of Life Science Capital Normal University The Initial Setup of EM Algorithm Copyright 2010 College of Life Science Capital Normal University The Initial Setup of EM Algorithm Columns not in motif provide background frequencies Columns defined by a preliminary alignment of the sequences provide initial estimates of frequencies of bases in each motif column profile 10 Copyright 2010 College of Life Science Capital Normal University Step 1 the expectation step Sequence 1 Use previous estimate of profile and multiply by to calculate probability of motif in this position background probabilities in the remaining positions Psite1 sequence1 Copyright 2010 College of Life Science Capital Normal University Step 1 the expectation step Sequence 1 Psite1 sequence1 11 Copyright 2010 College of Life Science Capital Normal University Step 1 the expectation step Sequence 1 Psite1 sequence1 Psite2 sequence1 Psite17 sequence1 The probability of the best locationthe best location in sequence 1 say at site k is the ratioratio of thisthis site probability at ksite probability at k divided by the other sum of all site probabilitiesthe other sum of all site probabilities P site k in sequence 1 Psitek sequence1 Psite1 sequence1 Psite2 sequence1 Psite17 sequence1 Copyright 2010 College of Life Science Capital Normal University Step 1 the expectation step The probability of the site location in each sequence is then calculated in this manner 12 Copyright 2010 College of Life Science Capital Normal University Step 2 the maximization step Copyright 2010 College of Life Science Capital Normal University Step 2 the maximization step In the maximization step the base frequencies found in the expectation step are used as an updatedupdated estimate of the profile In this case the PSSM are more complete than the initial estimatemore complete than the initial estimate because all possible sites in each of the sequences have been evaluated The expectation and maximization steps are repeatedrepeated until the estimate of the PSSM do not change 13 Copyright 2010 College of Life Science Capital Normal University The MEME Suite http meme sdsc edu meme4 3 0 intro html Copyright 2010 College of Life Science Capital Normal University 14 Copyright 2010 College of Life Science Capital Normal University Copyright 2010 College of Life Science Capital Normal University 15 Copyright 2010 College of Life Science Capital Normal University Copyright 2010 College of Life Science Capital Normal University 16 Copyright 2010 College of Life Science Capital Normal University Copyright 2010 College of Life Science Capital Normal University 17 Copyright 2010 College of Life Science Capital Normal University Copyright 2010 College of Life Science Capital Normal University 18 Copyright 2010 College of Life Science Capital Normal University Copyright 2010 College of Life Science Capital Normal University View BLOCK 19 Copyright 2010 College of Life Science Capital Normal University View FASTA Copyright 2010 College of Life Science Capital Normal University View RAW 20 Copyright 2010 College of Life Science Capital Normal University View PSPM Copyright 2010 College of Life Science Capital Normal University MAST program 21 Copyright 2010 College of Life Science Capital Normal University Copyright 2010 College of Life Science Capital Normal University 22 Copyright 2010 College of Life Science Capital Normal University Copyright 2010 College of Life Science Capital Normal University Programs for MSA 23 Co