构建系统发生树的研究方案

2022-09-10

在计算机生物学中, 序列比对是最重要的原始操作, 是许多其他更复杂的操作的基础。同样, 也是本论文后面将讨论的构建分子进化树的基础。粗略地讲, 序列比对包括发现序列的类同与序列的不同两方面。然而在浅显简单的概念背后存在着各种不同的问题, 它们形式也不同, 有时需要使用完全不同的数据结构和算法以达到有效的求解。

1 序列比对

1.1 全局比对

在介绍全局比对前, 首先要介绍以下空位罚分。

在含有空位的比对打分时, 空位罚分就必须包含到打分函数中。空位比对的简

单打分公式如下:

但是, 如果一个序列中有多个空位, 而这些空位可能分开也可能连在一起。

由此, 空位罚分被分为两部分:

①起始罚分;由序列中产生的新空位串引起

②长度罚分;根据缺少的字符数而定

知道了空位罚分, 下面讨论一下动态规划算法:

(1) 算法开始时, 用空位罚分的倍数对表格第一行与第一列进行初始化。其

公式为:

(2) 可以给表格的第一个位置 (2, 2) 填上三种可能值之一:

a:把左边 (2, 1) 位置的值加上空位罚分, 这表示给纵轴序列加入一个空位。

b:把上方 (1, 2) 位置的值加上空位罚分, 这表示给横轴序列加入一个空位。

c:把左上方位置的值加上两轴上相应核苷酸间的匹配奖励或失配罚分, 这表示两个核苷酸之间进行了比对。

对于这三种选择, 选取了其中最大值填入表格。

由此得出公式:

表格填满后, 右下角方格的值代表了两序列间最优带有空位比对的得分。从上面的算法我们可以知道, 为得到这个得分, 并没有为两条序列间所有可能的比对打分。因此, 我们可以重建两条序列的最优比对。为了建立这条路径, 要从表格中当前位置开始找出下一个位置, 这个位置必须可以产生当前位置的得分。这条路径就代表着两条序列间的最优比对 (当然, 有时也不只一条路径) 。

要把路径转换成序列比对, 仅需要回忆一下当初打分矩阵的解释。一个纵向的移动表示在横轴加入一个空位, 一个横向移动表示在纵轴加入一个空位, 而斜对角的移动表示两序列当前位点的核苷酸进行了一次比对。根据这种方法就得到了两条序列全局比对的最优比对。

1.2 局部比对

算法:

(1) 局部比对的初始化是将表格的第一行和第一列全都设为零。

(2) 当填写部分打分表是, 要引入第4种选择:给表中的得分小于零的位置填上零。

其公式为:

用这种方法填入表格后, 在表中找到最大值。然后, 从这个值开始向前回溯, 知道遇上零。至于其得到最优比对的过程, 也就和全局比对大同小异了。

2 构建分子进化树

构建分子进化树的方法有很多种, 本文只介绍其中的3种。

2.1 非加权组平均法 (UPGMA)

非加权组平均法是所有树重建方法中最简单的一种。该方法最初于20世纪60年代早期提出, 用来协助进行表型特征的进化分析。UPGMA是基于统计的, 要求数据能够精简为所有被研究的物种两两之间遗传距离的度量。

UPGMA算法:

(1) 首先将两个距离最近的物种合成一个复合物种组。

(2) 第一次聚类以后, 要更新距离矩阵, 计算新组物种和其它物种之间的距离。 (3) 然后将新的距离中距离最小的两个物种再次合成一个复合物种组。

(4) 如此反复, 直到所有的物种聚类为一类。

2.2 距离变换法

这种方法首先有J.Farris在1977年提出, 充分利用了外群或外部参考物种——先于其他所有被考虑的物种从他们的共同祖先中分化出来的那些物种。

其具体算法为:

(1) 假设D是外部参考物种。

(2) 变换式为:

其中dij’是物种i和j之间的变换后距离, d D’是外部参考物种与全体内部能够之间的平均距离。

(3) 利用此变换式求出所有物种变换后的距离并天如距离矩阵中。

2.3 无权简约法

如果一个内部节点的两个直接后代节点上的核苷酸集的交集非空, 那么这个接点的最可能的候选核苷酸集就是这个交集;否则为它的两个后代节点上核苷酸集的并集。

当一个并集成为一个节点的核苷酸集时, 通向该节点的分支的某个位置上必定发生一个核苷酸替换。因此, 并集中核苷酸的数目也是发生外部节点上的核苷酸的最小替换数, 外部节点从它们的共同的祖先出发, 通过这些替换, 形成当前的核苷酸状态。

3 结语

进行序列的比较和构建分子进化树通常有多种方法。在进行序列比较时如果想全面分析序列之间的关系, 全局比对是一个很好的选择;当集中的比较某一段特殊序列则用局部比对。进行分子进化树的构建时, UPGMA法在不同谱系间进化速率有较大差异时常得出错误的拓扑结构, 可操作性极差, 因而该建树方法的使用极为有限。距离变换法在确定树的正确拓扑结构上优于单独使用UPGMA法:内部物种只是在分化发生后进化分离出来的, 所以它们积累的替换数目一定是从那以后才有了差异。因此, 外部参考物种为比较它们替换速率提供了客观参考的框架。无权简约法加入了信息位点, 不依赖任何进化模型, 能快速地分析出大量序列之间的系统发生关系, 所构建的树中的短分支更接近真实。但简约树的分值完全决定于所有重建祖先序列中的最小突变数, 而突变是否按照事先约定的核苷酸最少替代的途径进行是不得而知的, 单一的突变图谱可能会得出是似而非的结论。

摘要：系统发生树的构建是生物信息学研究和进化研究的一个重要方面。一个可靠的系统发生的推断, 将揭示出有关生物进化过程的顺序, 有助于我们了解生物进化的历史和进化机制。

关键词：序列比对,分子进化树