《生物信息学1.ppt》由会员分享，可在线阅读，更多相关《生物信息学1.ppt（98页珍藏版）》请在三一文库上搜索。
1、1,Chapter 2:,Pairwise Sequence Alignment,2,Sequence Alignment,Question: Are two sequences related? Compare the two sequences, see if they are similar significantly. Example: pear and tear Similar words, different meanings,4,Biological Sequences,Similar biological sequences tend to be related Provide
2、 Information on : Functional Structural Evolutionary,5,Biological sequences,Common mistake: Sequence similarity is not homology! Homologous sequences: derived from a common ancestor,A:Gene duplication and speciation events; B: Othologs; C: Convergent genes; and D: Gene horizontal transfer.,7,Relatio
3、n of sequences,Homologous: similar sequences in 2 different organisms derived from a common ancestor sequence.(同源） Orthologs: Similar sequences in 2 different organisms that have arisen due to a speciation event. （直系同源） Functionality Retained.,8,Relation of sequences,Paralogs: Similar sequences with
4、in a single organism that have arisen due to a gene duplication event.（并系同源） Xenologs: similar sequences that have arisen out of horizontal transfer events (symbiosis, viruses, etc)（异同源）,9,Relation of sequences,Image Source: http:/www.ncbi.nlm.nih.gov/Education/BLASTinfo/Orthology.html,10,Edit Dista
5、nce,Sequence similarity: function of edit distance between two sequences P E A R | | | T E A R,11,Hamming Distance,Minimum number of letters by which two words differ Calculated by summing up the number of mismatches Hamming Distance between PEAR and TEAR is 1,12,Gapped Alignments,Biological sequenc
6、es Different lengths Regions of insertions and deletions Notion of gaps (denoted by -) A L I G N M E N T | | | | | | | - L I G A M E N T,13,Possible Residue Alignments,Match Mismatch substitution: among species and polymorphism or mutation: within species Insertion/Deletion (INDELS gaps),14,Alignmen
7、ts,Which alignment is best? A C G G A C T | | | | | A T C G G A T C T A T C G G A T C T | | | | | | | A C G G A C T,15,Alignment Scoring Scheme,Possible scoring scheme: match: +2 mismatch: 1 indel: 2 Alignment 1: 5 2 1 (1) 4 (2) = 10 1 8 = 1 Alignment 2: 7 2 0 (1) 2 (2) = 14 4 = 10,16,Alignment Meth
8、ods,Visual Dot matrix analysis. Brute Force Dynamic Programming Word-Based (k-tuples (元组 ), i.e. common patterns) (such as FASTA and BLAST),17,Visual Alignments (Dot Plots),Matrix Rows: Characters in one sequence Columns: Characters in second sequence Filling Loop through each row; if character in r
9、ow, column match, fill in the cell Continue until all cells have been examined,18,Example Dot Plot,19,Noise in Dot Plots,Nucleic Acids (DNA, RNA) 1 out of 4 bases matches at random Dot plots can be filtered for stringency requiring: Window size is considered Percentage of bases matching in the windo
10、w is set as threshold,20,Reduction of Dot Plot Noise,21,Reduction of Dot Plot Noise,22,Human globin vs. human myoglobin,23,Information Inside Dot Plots,Regions of similarity: diagonals Insertions/deletions One potential application is to determine the number of coding regions (exons,外显子) contained w
11、ithin a processed mRNA.,24,Insertions/Deletions,25,Information Inside Dot Plots,Repeats and Inverted Repeats Inverted repeats = reverse complement Used to determine folding of RNA molecules,26,Repeats/Inverted Repeats,27,Available Dot Plot Programs,Every lab that does sequence analysis should have a
12、t least one dot matrix program available: say, GCG software package: Comparehttp:/www.hku.hk/bruhk/gcgdoc/compare.html DotPlot+http:/www.hku.hk/bruhk/gcgdoc/dotplot.html Dotter(http:/www.cgr.ki.se/cgr/groups/sonnhammer/Dotter.html) EMBOSS,28,shortcoming of visual methods,The shortcoming of visual me
13、thods is that they do not yield a direct measure into the similarity between two sequences.,29,In order to get a measure into sequence similarity, dynamic programming can be employed.,30,Dynamic Programming,Used in Computer Science Solve optimization problems by dividing the problem into independent
14、 sub-problems,31,Dynamic Programming,Scoring scheme for matches, mismatches, gaps Highest set of scores defines optimal alignment between sequences Match score: DNA exact match; Amino Acids mutation probabilities,32,Dynamic Programming,Guaranteed to provide optimal alignment given: Two sequences Sco
15、ring scheme,33,Steps in Dynamic Programming, Initialization Matrix Fill (scoring) Trace back (alignment),34,DP Example,Sequence #1: GAATTCAGTTA; M = 11 Sequence #2: GGATCGA; N = 7 s(aibj) = +5 if ai = bj (match score) s(aibj) = -3 if aibj (mismatch score) w = -4 (gap penalty),35,View of the DP Matri
16、x,M+1 rows, N+1 columns,36,Global Alignment(Needleman-Wunsch),Attempts to align all residues of two sequences INITIALIZATION: First row and first column set Si,0 = w * i S0,j = w * j,37,Initialized Matrix (Needleman-Wunsch),38,Matrix Fill(Global Alignment),Si,j = MAXIMUM Si-1, j-1 + s(ai,bj) (match/
17、mismatch in the diagonal) Si,j-1 + w (gap in sequence #1), Si-1,j + w (gap in sequence #2) ,39,40,Matrix Fill (Global Alignment),S1,1 = MAXS0,0 + 5, S1,0 - 4, S0,1 - 4 = MAX5, -8, -8,41,Matrix Fill (Global Alignment),S1,2 = MAXS0,1 -3, S1,1 - 4, S0,2 - 4 = MAX-4 - 3, 5 4, -8 4 = MAX-7, 1, -12 = 1,42
18、,Matrix Fill (Global Alignment),43,Filled Matrix (Global Alignment),44,Trace Back (Global Alignment),maximum global alignment score = 11 (value in the lower right hand cell). Traceback begins in position SM,N; i.e. the position where both sequences are globally aligned. At each cell, we look to see
19、where we move next according to the pointers.,45,Trace Back (Global Alignment),46,Global Trace Back,G A A T T C A G T T A | | | | | | G G A T C G - A,47,Checking Alignment Score,G A A T T C A G T T A | | | | | | G G A T C G - A + - + - + + - + - - + 5 3 5 4 5 5 4 5 4 4 5 5 3 + 5 4 + 5 + 5 4 + 5 4 4
20、+ 5 = 11,Local Alignment,48,49,Local Alignment,Smith-Waterman: obtain highest scoring local match between two sequences Requires 2 modifications: Negative scores for mismatches When a value in the score matrix becomes negative, reset it to zero (begin of new alignment),50,Local Alignment Initializat
21、ion,Values in row 0 and column 0 set to 0.,51,Matrix Fill(Local Alignment),Si,j = MAXIMUM Si-1, j-1 + s(ai,bj) (match/mismatch in the diagonal), Si,j-1 + w (gap in sequence #1), Si-1,j + w (gap in sequence #2), 0 ,52,Matrix Fill (Local Alignment),S1,1 = MAXS0,0 + 5, S1,0 - 4, S0,1 4,0 = MAX5, -4, -4
22、, 0 = 5,53,Matrix Fill (Local Alignment),S1,2 = MAXS0,1 -3, S1,1 - 4, S0,2 4, 0 = MAX0 - 3, 5 4, 0 4, 0 = MAX-3, 1, -4, 0 = 1,54,Matrix Fill (Local Alignment),S1,3 = MAXS0,2 -3, S1,2 - 4, S0,3 4, 0 =MAX 0 - 3, 1 4, 0 4, 0 = MAX-3, -3, -4, 0 = 0,55,Filled Matrix(Local Alignment),56,Trace Back (Local
23、Alignment),maximum local alignment score for the two sequences is 14 found by locating the highest values in the score matrix 14 is found in two separate cells, inplying alternative alignments producing the maximal alignment score,57,Trace Back (Local Alignment),Traceback begins in the position with
24、 the highest value. At each cell, we look to see where we move next according to the pointers When a cell is reached where there is not a pointer to a previous cell, we have reached the beginning of the alignment,58,Trace Back (Local Alignment),59,Trace Back (Local Alignment),60,Trace Back (Local Al
25、ignment),61,Maximum Local Alignment,G A A T T C - A | | | | | G G A T C G A + - + + - + - + 5 3 5 5 4 5 4 5,G A A T T C - A | | | | | G G A T C G A + - + - + + - + 5 3 5 4 5 5 4 5,62,Drawbacks to DP Approaches,Compute intensive Memory Intensive O(n2) space, between O(n2) and O(n3) time,63,Incorporat
26、ion of Scoring Matrices,64,Certain amino acid substitutions commonly occur in related proteins from different species. Since the proteins in all of the species are functional, the substitutions maintain protein structure and function. Often the substitutions result in a chemically similar amino acid
27、. Other substitutions are relatively rare.,65,Scoring Matrices,match/mismatch score Not bad for similar sequences Does not show distantly related sequences Thus we need likelihood matrix Scores residues dependent upon likelihood substitution is found in nature More applicable for amino acid sequence
28、s,66,Percent Accepted Mutation (PAM or Dayhoff) Matrices,Because changes observed in closely related proteins represent amino acid substitutions that do not significantly change the function of protein. Hence they are called “accepted mutations” defined as amino acid changes “accepted” by natural se
29、lection.,67,Percent Accepted Mutation (PAM or Dayhoff) Matrices,Studied by Margaret Dayhoff,Percent Accepted Mutation (PAM or Dayhoff) Matrices,Amino acid substitutions Alignment of common protein sequences 1572 amino acid substitutions 71 groups of protein, 85% similar,68,69,Percent Accepted Mutati
30、on (PAM or Dayhoff) Matrices,Similar sequences organized into phylogenetic trees Number of amino acid changes into every other amino acid were counted Relative mutabilities were by counting the number of changes of each amino acid divided by a normalization factor.,70,Percent Accepted Mutation (PAM
31、or Dayhoff) Matrices,The factor which means exposure to mutation of the amino acid, is defined as F= fi *N fi is the frequency of occurrence of the amino acid in that group, and N is the total number of all amino acid changes that occurred in that group per 100 sites.,71,Percent Accepted Mutation (P
32、AM or Dayhoff) Matrices,This normalized the data for variations in amino acid composition, mutation rate, and sequence length. The normalized frequencies were then averaged for sequence groups,72,Percent Accepted Mutation (PAM or Dayhoff) Matrices,The amino acid exchange counts and mutability values
33、 were used to generate a 20 20 mutation probability matrix representing all possible amino acid changes. A detailed example of calculating the PAM matrix is located in Mount, p82 (table 3.2).,73,PAM1 matrix (see p80-81),normalized probabilities multiplied by 10000 A l a A r g A s n A s p C y s Gl n
34、G l u G l y H i s Il e L e u L y s M e t P h e P r o S e r T h r T r p T y r V a l A R N D C Q E G H I L K M F P S T W Y V A 9867 2 9 1 0 3 8 1 7 2 1 2 6 4 2 6 2 2 2 3 5 3 2 0 2 1 8 R 1 9 9 1 3 1 0 1 1 0 0 0 1 0 3 1 1 9 4 1 4 6 1 8 0 1 N 4 1 9 8 2 2 3 6 0 4 6 6 2 1 3 1 1 3 0 1 2 2 0 9 1 4 1 D 6 0 4
35、2 9 8 5 9 0 6 5 3 6 4 1 0 3 0 0 1 5 3 0 0 1 C 1 1 0 0 9 9 7 3 0 0 0 1 1 0 0 0 0 1 5 1 0 3 2 Q 3 9 4 5 0 9 8 7 6 2 7 1 2 3 1 3 6 4 0 6 2 2 0 0 1 E 1 0 0 7 5 6 0 3 5 9 8 6 5 4 2 3 1 4 1 0 3 4 2 0 1 2 G 2 1 1 1 2 1 1 1 3 7 9 9 3 5 1 0 1 2 1 1 3 2 1 3 0 0 5 H 1 8 1 8 3 1 2 0 1 0 9 9 1 2 0 1 1 0 2 3 1 1
36、1 4 1 I 2 2 3 1 2 1 2 0 0 9 8 7 2 9 2 1 2 7 0 1 7 0 1 3 3 L 3 1 3 0 0 6 1 1 4 2 2 9 9 4 7 2 4 5 1 3 3 1 3 4 2 1 5 K 2 3 7 2 5 6 0 1 2 7 2 2 4 1 9 9 2 6 2 0 0 3 8 1 1 0 1 1 M 1 1 0 0 0 2 0 0 0 5 8 4 9 8 7 4 1 0 1 2 0 0 4 F 1 1 1 0 0 0 0 1 2 8 6 0 4 9 9 4 6 0 2 1 3 2 8 0 P 1 3 5 2 1 1 8 3 2 5 1 2 2 1
37、1 9 9 2 6 1 2 4 0 0 2 S 2 8 1 1 3 4 7 1 1 4 6 1 6 2 2 1 7 4 3 1 7 9 8 4 0 3 8 5 2 2 T 2 2 2 1 3 4 1 3 2 2 1 1 1 2 8 6 1 5 3 2 9 8 7 1 0 2 9 W 0 2 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 9 9 7 6 1 0 Y 1 0 3 0 3 0 1 0 4 1 1 0 0 2 1 0 1 1 2 9 9 4 5 1 V 1 3 2 1 1 3 2 2 3 3 5 7 1 1 1 1 7 1 3 2 1 0 0 2 9 9 0 1,74,P
38、ercent Accepted Mutation (PAM or Dayhoff) Matrices,By these scores, Asn, Ser, Asp, and Glu were the most mutable amino acids, and Cys and Trp were the least mutable.,75,PAM1 matrix,This is a Markov chain matrix Summation along each column = 1.0 Asymmetry matrix obtained (why),76,Percent Accepted Mut
39、ation (PAM or Dayhoff) Matrices,PAM 1 matrix can be multiplied by itself N times to give transition matrices for sequences that have undergone N mutations (why?) (Markov chain model),77,Percent Accepted Mutation (PAM or Dayhoff) Matrices,PAM 1: 1 accepted mutation event per 100 amino acids; PAM 250:
40、 250 mutation events per 100 amino acids. Many of them are multiple substitutions.,78,Percent Accepted Mutation (PAM or Dayhoff) Matrices,PAM 250: 20% similar; PAM 120: 40%; PAM 80: 50%; PAM 60: 60% The PAM250 matrix provides a better-scoring alignment than lower-numbered PAM matrices for distantly
41、related proteins of 14-27% similarity.,79,Log Odds Matrices,PAM matrices converted to log-odds matrix Calculate odds ratio for each substitution Taking scores in previous matrix(PAM250) Divide by frequency of amino acid,80,Log Odds Matrices,Take average of log odds ratio for converting A to B and co
42、nverting B to A Result: Symmetric matrix Convert ratio to log10 and multiply by 10 EXAMPLE: Mount pp. 83,81,PAM250 Log odds matrix,82,Blocks Amino Acid Substitution Matrices (BLOSUM),Larger set of sequences considered Sequences organized into signature blocks Consensus sequence formed 60% identical:
43、 BLOSUM 60 80% identical: BLOSUM 80,83,All BLOSUM matrices are based on observed alignments; they are not extrapolated from comparisons of closely related proteins. BLOSUM 62 is the default matrix in BLAST 2.0. Though it is tailored for comparisons of moderately distant proteins, it performs well in
44、 detecting closer relationships. A search for distant relatives may be more sensitive with a different matrix.,84,Equivalent PAM and Blossum matricesThe following matrices are roughly equivalent.PAM100 = Blosum90 PAM120 = Blosum80 PAM160 = Blosum60 PAM200 = Blosum52 PAM250 = Blosum45,85,Differences
45、between PAM and BLOSSUM1. PAM matrices are based on an explicit evolutionary model (that is, replacements are counted on the branches of a phylogenetic tree), whereas the Blosum matrices are based on an implicit rather than explicit model of evolution.,86,Differences between PAM and BLOSSUM,2. The m
46、ethod used to count the replacements is different, unlike the PAM matrix, the Blosum procedure uses groups of sequences within which not all mutations are counted the same.,87,Differences between PAM and BLOSSUM,3. The sequence variability in the alignments used to count replacements. The PAM matric
47、es are based on mutations observed throughout a global alignment, this includes both highly conserved and highly mutable regions. The Blosum matrices are based only on highly conserved regions in series of alignments forbidden to contain gaps.,88,Nucleic Acid Scoring Matrices,Two mutation models: Uniform mutation rates (Jukes-Cantor) ( = common rate of base substitution),89,Nucleic Acid Scoring Matrices,Two separate mutation rates (Kimura) Transitions and Transversions respectively = rate of transitions; = rate of transversions,90,Nucleic Acid Scoring Matrices,91,DNA Mutations,92,PAM1