生物信息学两两序列比对改.ppt

全局比对(global alignment)从全长序列出发，考虑序列的整体相似性，即。Needleman-Wunsch算法是一种经典的基于动态规划的整体比对算法，其最佳比对中包括了全部的最短匹配序列。 局部比对(Local alignment)考虑序列部分区域的相似性，即有时两个序列总体并不很相似，但某些局部片断相似性很高。局部相似性比对的生物学基础是蛋白质功能位点往往是由较短的序列片段组成的，这些部位的序列具有相当大的保守性，尽管在序列的其它部位可能有插入、删除或突变。此时，局部相似性比对往往比整体比对具有更高的灵敏度，其结果更具生物学意义。Smith-Waterman算法是在Needleman-Wunsch算法基础上发展而来的一种经典的局部比对算法 序列比对 0 A G C 0 0 (-/-) -2 (A/-) -4 (AG/--) -6 (AGC/) A -2 (-/A) 1 (A/A) -1 (AG/A) -3 (AGC/A) A -4 (--/AA) -1 (A/AA) 0 (AG/AA) -2 (AGC/AA) A -6 (/AAA) -3 (A/AAA) -2 (AG/AAA) -1 (AGC/AAA) C -8 (/AAAC) -5 (A/AAAC) -4 (AG/AAAC) -1 (AGC/AAAC) 序列比对 0 A G C 0 0 (-/-) -2 (A/-) -4 (AG/--) -6 (AGC/) A -2 (-/A) 1 (A/A) -1 (AG/A) -3 (AGC/A) A -4 (--/AA) -1 (A/AA) 0 (AG/AA) -2 (AGC/AA) A -6 (/AAA) -3 (A/AAA) -2 (AG/AAA) -1 (AGC/AAA) C -8 (/AAAC) -5 (A/AAAC) -4 (AG/AAAC) -1 (AGC/AAAC) 序列比对结果 AAAC / -AGC 序列比对结果 AAAC-/-AG-C 序列比对结果 AAAC/AG-C AAAC/A-GC N-W is guaranteed to find optimal alignments, although the algorithm does not search all possible alignments. It is an example of a dynamic programming algorithm: an optimal path (alignment) is identified by incrementally extending optimal subpaths. Thus, a series of decisions is made at each step of the alignment to find the pair of residues with the best score. Needleman-Wunsch: dynamic programming Page 80 Try using needle to implement a Needleman-Wunsch global alignment algorithm to find the optimum alignment (including gaps): http://www.ebi.ac.uk/emboss/align/ Page 81 Queries: beta globin (NP_000509) alpha globin (NP_000549) Global alignment (Needleman-Wunsch) extends from one end of each sequence to the other. Local alignment finds optimally matching regions within two sequences (“subsequences”). Local alignment is almost always used for database searches such as BLAST. It is useful to find domains (or limited regions of homology) within sequences. Smith and Waterman (1981) solved the problem of performing optimal local sequence alignment. Other methods (BLAST, FASTA) are faster but less thoroug