基于Profile 比对的改进星比对算法

陈俊涛，邹 权

(电子科技大学基础与前沿研究院 成都 610054)

多序列比对是生物信息学研究中重要的课题之一，对于识别未知基因功能、分析物种间的进化关系、识别基因之间的保守区域等问题有着重要作用。随着测序技术的发展，基因序列数据快速增长，现有软件难以处理大规模的多序列比对问题。

目前大多数软件采用的是渐进式比对策略或者迭代式比对策略[1]，如MAFFT[2]、Kalign3[3]、Clustal[4-5]、MUSCLE[6]、T-Coffee[7]、HAlign[8]等。渐进式比对需要先计算两两序列之间的距离，再根据距离矩阵使用层次聚类算法，如UPGMA、Neighbor Joining 等构建一颗比对的指导树，沿着指导树的枝干进行两两比对与合并，最后得到最终结果。而迭代式比对策略在此基础上，还要对合并的最终结果选取适当的策略，如剪枝、局部重新比对和随机选取序列重新比对进行迭代，直到比对精确收敛或者迭代次数达到上限。迭代式比对策略可以解决渐进式比对初期可能遗留下的问题。因为渐进式比对策略是贪心策略，在初期局部的比对结果上可能陷入局部最优，而错误会一直保留至最终结果中。而通过迭代式比对可以选取适当的策略，去更正局部比对的一些错误，但迭代式比对增加了时间复杂度。这两者都有着较高的时间复杂度，所以难以在有限时间内处理大规模数据的比对。

渐进式比对策略的时间复杂度与序列数量呈多项式级增长，因此在面对大规模数据的情况下，该策略时间复杂度太高、比对时间过长。而星比对是一种启发性的策略，其时间复杂度与序列数量呈线性增长，这有效降低了大规模序列比对的时间。然而，星比对算法在相似度不高的数据集上的比对精度较低，目前只能应用到相似度非常高的同源序列上，这大大限制了星比对的应用。

针对星比对精度低的问题，本文将渐进比对的模式应用于星比对中，提出了基于profile 比对的改进星比对算法。实验证明改进后的算法提高了比对的精度，同时也节省了比对时间。

1 算 法

本研究改进的星比对算法采用了渐进比对的思想，先构建一颗比对的指导树，然后沿着树的枝干进行比对。但是与传统的构建指导树的方法不同，本研究沿用了星比对的核心思想，即中心比对的思想。为了加快比对速度，引进了k-band 策略以加速双序列之间的比对。

1.1 双序列比对

对于双序列比对问题，主要采用动态规划的方法，有全局比对Needleman-Wunsch 算法[9]和局部比对Smith-Waterman 算法[10]。

图1 展示的是全局比对算法，即先建立一个得分矩阵然后根据计算规则计算最大得分(匹配+1、不匹配−1、空格−1)，再从右下角的最大得分回溯至左上角，得到最优比对。

图1 DNA 双序列比对动态规划算法

本研究采用的是仿射罚分与k-band 结合的双序列全局比对算法[8]。不同于图1 的线性罚分，仿射罚分的机制更为合理，这有效地避免了间断出现缺失的情况，使得比对结果更倾向于连续出现缺失，这也更符合生物学的进化过程，即一旦缺失位点出现，那么此位点就会有更大可能性再次出现缺失。k-band 策略指的是两条序列较为相似时，回溯路线一般会在对角线附近，非对角线附近区域的值可以不用计算，只用计算对角线附近的宽为k的带，这个宽为k的带被称为k-band。k-band 这一启发性策略减少了比对的时间和空间复杂度，将时空复杂度由O(pn)降 低到了O(kn)(p和n为序列的长度，k为带的宽度)。如图1 所示，回溯路径只出现在k=1的 灰色带中。k的 初始值一般为p和n的差值的绝对值，然后进行k值的迭代，计算比对的最优得分，每次迭代k值翻倍，直到得分最大值收敛则停止迭代。

虽然采用k-band 策略的双序列比对算法可以减少算法的时间和空间复杂度，但是不能确保找到最优的比对，有可能会陷入局部最优解中。为了减少此类情况的发生，只对序列长度相近的序列采取k-band 策略的比对，对于序列长度相差较大的序列则采取全局比对的方法。因为两条序列长度相差较大，可能会导致k值迭代后的k-band 的区域很大，甚至超过原本pn大小的区域面积，不仅无法节省时间和空间，反而需要更大的时空复杂度。

1.2 传统的星比对算法

传统的星比对算法主要分为以下3 个步骤：

1)选取中心序列；

2)将中心序列与其余序列一一进行比对；

3)根据“once gap, always gap”的原则，将双序列比对的结果合并，得到最终的比对结果。

中心序列的选取是传统星比对算法步骤中时间复杂度最高的，因为需要计算两两序列之间的相似度。传统计算序列两两相似度的方法是动态规划，时间复杂度为O(n2)。但是由于其复杂度太高，目前使用较为广泛是使用k-mer 法计算序列相似度，其时间复杂度为O(n)。使用k-mer 计算序列间的相似度，选取中心序列的总体复杂度可降为O(m2n)，其中m为序列的条数，n为序列的长度。步骤2)需要将中心序列与其余序列一一做比对，其算法时间复杂度为O(kmn)。步骤3)合并序列比对结果的算法时间复杂度为O(mn)。结合3 个步骤的算法时间复杂度，该算法的总体时间复杂度为O(m2n+kmn)。

1.3 改进的星比对算法

本研究对传统的星比对算法进行了改进。首先，参考了cd-hit[11]聚类软件的思路，将最长的序列作为中心序列。然后，引进了渐进比对的思想，将构建指导树和profile 比对的策略加入到改进的星比对中来。

改进的星比对算法主要有以下4 个步骤：

1)选取最长序列；2)计算最长序列与其余序列之间的相似度；

3)根据步骤2)得到的相似度构建比对的指导树。构建指导树的原则为，先将相似度最高的序列聚合，再依次根据相似度，将序列加入树中，最终构建一颗单链指导树；

4)沿着指导树进行比对和合并，最终得到比对结果。

图2 展示了构建指导树和比对的过程。本研究将序列中的最长序列作为中心序列，这大大降低了选取中心序列的时间。改进后的星比对算法，双序列比对只会在首次比对的时候出现，在指导树的枝干上都是序列与profile 比对。与双序列比对不同，序列与profile 比对计算得分耗时会更长，在一定程度上会增加比对的时间。因此，改进后的星比对算法的时间复杂度与序列数量不呈现线性增长，其增长速度介于渐进比对和传统星比对之间。

图2 4 条DNA 序列构建指导树

2 实 验

本研究采用了模拟的RNA 数据来验证算法的有效性。根据序列数量将数据集分5 个组，序列数量 分 别 为：256 条、512 条、1024 条、2048 条、4096 条，序列平均长度约为1500 个碱基对。每个组分别有20 个不同数据集，测试多数据集以求取精度的平均值，可以验证算法的鲁棒性，避免因为偶然性影响实验结果的有效性。实验数据来自于公开数据集网站https://kim.bio.upenn.edu/software/csd.shtml.

实验采用了SP score 来衡量多序列比对的效果，该值是多序列比对中所有双序列组合的比对得分之和。双序列计算得分规则为：相同位置字符匹配则得1 分，不匹配或者两者都是空格则得0 分。SP 分值越高则代表比对的效果越好。而在数据较大的时候，SP 值过大不能准确展示其精度，因此本研究采用了SP 值的平均值来展示比对精度。

本研究对传统的星比对算法做了两项改进：1)改进选取“中心序列”的策略，以降低选取算法的时间复杂度；2)引进了渐进比对的思想，构造一棵特殊的指导树，加入profile 比对的策略。为了研究两项改进对比对精度的影响，本文设计了4 种实验的算法组合：传统的星比对算法+传统的中心序列选取策略、传统的星比对算法+选取最长序列、改进的星比对算法+传统的中心序列选取策略、改进的星比对算法+选取最长序列，比对4 组实验的精度和时间。4 组实验都是在CPU 为Xeon E3-1230，内存为32 G 的Ubuntu 20.04 系统环境下进行的。

实验结果如图3 和图4 所示。图3 展示了4 组算法在不同数据集上的精度。可以看到随着数据集的增大，比对的精度也随之降低。

图3 不同数据集的比对精度对比

图4 不同数据集的比对时间对比

在使用传统的星比对算法的基础上，对比使用不同的选取中心序列的策略。使用k-mer 法计算相似度选取中心序列的策略明显优于使用最长序列计算相似度的策略，可以观察到在5 组数据集中，使用最长序列策略的比对精度都要比传统的策略低。而在使用改进的星比对算法的基础上，两种选取中心序列的策略得到的比对效果近乎一致，无论是在比对精度的均值还是在比对精度的范围上，两者并无明显差异。

在使用传统策略选取中心序列的基础上，改进的星比对算法的比对精度明显要优于传统的星比对算法。同样，在使用最长序列作为中心序列的基础上，改进的星比对算法的比对精度也明显优于传统的星比对算法。

由图3 可知，在4 组实验中，可以看到改进的星比对算法的比对效果优于传统的星比对算法。从图4 可知，使用最长序列作为中心序列的策略，可在一定程度上减少比对的时间。因此改进的星比对算法加上使用最长序列作为中心序列的策略是最佳的组合方式，此组合可以得到最好的比对精度，同时不会显著提升星比对的比对时间。

3 结 束 语

本文将传统的星比对与渐进比对相结合，提出了基于profile 比对的改进星比对算法，改进后的星比对算法显著提高了比对的精度。为了减少比对时间，本研究还简化了中心序列的选取，直接将最长序列作为中心序列。改进前后的算法时间复杂度是一致的，但实际时间不一定一致，改进的星比对算法运行时间要略大于传统的星比对算法。同时，两者运行时间随着数据量级增大的增长速度是一致的。由此可见，本文提出的基于profile 比对的改进星比对算法不仅提高了比对的精度，又通过简化中心序列的选取减少了星比对中选取中心序列的时间，同时也并未增加比对算法的时间复杂度。