最佳全序列排比.ppt

* * 最佳全序列排比--Globally optimal sequence alignment: The Needleman-Wunsch-Sellers Algorithm (Dynamic programming) 强制性分段(COMPULSIVE DETAIL SECTION) 两个序列N-端的第一行或列的最高分值就是全序列最佳排比的分值，在上例中为5，亦即全序列排比将有5个匹配。让我们再回过头来追踪所走过的路径，看看5这个值是如何得来的。可以简单的将进程向后倒退，记下所有对5这个值有实际贡献的单元格，为简单起见，略去所有对总值无贡献的单元格。 最佳全序列排比--Globally optimal sequence alignment: The Needleman-Wunsch-Sellers Algorithm (Dynamic programming) 强制性分段(COMPULSIVE DETAIL SECTION) 根据上述规则(即忽略gaps)，所有这些排比都是等价的。Needleman-Wunsch-Sellers 算法(NWS)将输出一个这样的排比。也就是说它并不保证还可以找出特有的同等最佳排比。因此有必要利用各种不同的打分矩阵而不仅仅是单一矩阵。 最佳全序列排比--Globally optimal sequence alignment: The Needleman-Wunsch-Sellers Algorithm (Dynamic programming) Gap扣分(Gap penalties) 如果我们引入gap扣分，即每当需要加入一个离开对角线的单元格的值时，将总值减1，以此方式在排比中引入gaps，所得矩阵如下： 最佳全序列排比--Globally optimal sequence alignment: The Needleman-Wunsch-Sellers Algorithm (Dynamic programming) Gap扣分(Gap penalties) 按照原先的规则，即暂不考虑gaps，上述这两个排比还是等价的，最终我们可以给末端的gap扣分，使第一个排比成为唯一的最佳排比。 一旦给gap和gap延伸打分，就意味着要用到一个离开对角线的单元(off diagonal element)，就得从排比中减去相应的gap分值。显然，在gap扣分的大小和打分矩阵的刻度之间存在着一定的关系，我们必须考虑应如何给gap扣分才更合理。 Smith and Waterman对这一原理做了重要的改良。 最佳局部排比--Local Optimal Alignment Sequence Alignment: The Smith Waterman Algorithm 局部最佳排比 局部最佳排比是Needleman Wunsch所描述的动态程序方法的一个变种，用以产生最佳局部排比。它完全依靠另一种打分矩阵来达成，由此也可见打分矩阵在序列排比过程中是何等的重要。 最佳局部排比--Local Optimal Alignment Sequence Alignment: The Smith Waterman Algorithm 局部最佳排比 Smith Waterman算法也象Needleman Wunsch算法一样，在排比时构造出一条路径。局部排比的最重要特征是为随机排比定义一个负值，使得随机排比和其它不匹配延伸降低路径的总分值，当总的路径矩阵运算完成后，最佳局部排比就被简单化为一个在路径矩阵中从最高分单元(左上)开市的路径，包含所有为该最高分值有贡献的单元格(考虑了gap产生和延伸扣分之后)，一直向右下后退至零分的单元格。 这个算法被用在UWGCG程序“BESTFIT”。 最佳局部排比--Local Optimal Alignment Sequence Alignment: The Smith Waterman Algorithm GCG程序“BESTFIT” “BESTFIT”采用Smith Waterman的局部同源算法来找出两个序列之间相似度最大的区段，同时也插入gaps来获得该区段的最佳排比，然后将排比结果显示出来。用于排比的序列长度可以差别很大，页可以只有其中一小段相似。例如，可以拿一小段RNA序列来对整个线粒体基因组进行排比。在从未知相关性的序列中找出最相似的区段方面， “BESTFIT”是UWGCG软件包中功能最强大的排比方法。 最佳局部排比--Local Optimal Alignment Sequence Alignment: The Smith Waterman Algorithm GCG程序“BESTFIT” “BESTFIT”从打分矩阵中读取各个