目标函数在形式化开发多序列比对算法中的重要性

2023-10-25 理论教育版权反馈

【摘要】：在序列比对的过程中，由于无法使用能否准确反映生物学意义这一概念来衡量序列比对结果的质量，因此我们引入了目标函数这一数学模型对序列比对结果进行评价。然而，在多序列比对中，目标函数的计算要复杂得多，且如何选择合适的目标函数也需要加以考虑。理论上目标函数可以尽可能准确、有效地反映多序列比对结果的质量，并能发现更多的生物学意义。目前，对于目标函数的研究还在持续地进行，相关的优化方式也在不断提出。

在序列比对的过程中，由于无法使用能否准确反映生物学意义这一概念来衡量序列比对结果的质量，因此我们引入了目标函数（objective function，OF）这一数学模型对序列比对结果进行评价。在双序列比对中，对比对结果进行打分较为容易，我们可直接根据相应的替换矩阵与罚分模型进行计算，且分数的高低可以较好地体现生物学意义。然而，在多序列比对中，目标函数的计算要复杂得多，且如何选择合适的目标函数也需要加以考虑。理论上目标函数可以尽可能准确、有效地反映多序列比对结果的质量，并能发现更多的生物学意义。目前，对于目标函数的研究还在持续地进行，相关的优化方式也在不断提出。广泛使用的目标函数主要有两种：比对和函数（sum-of-pairs function）以及COFFEE函数（consistency based objective function for alignment evaluation）。

比对和函数的分值简称为SP值，基于SP的多序列比对已被证明是一个NP难题。比对和函数的理论基础是得分函数具有相加性，多序列比对的得分可以通过序列两两之间的比对得分相加得到。比对和函数的得分（score）计算公式如下：

alignment（Si，Sj）表示下标顺序为i、j的两条序列的双序列比对得分。如果有一个多序列比对结果的得分值为score（A'）且score（A'）=max（score（A）），则称该多序列比对结果是一个最优比对。

COFFEE函数是在比对和函数之后提出的，目前也得到了学术界的广泛应用.它的计算方式与比对和函数的计算方式不同：它的计算不依赖替换矩阵和罚分模型，这些信息都隐藏在它根据双序列比对建立的扩展库中。COFFEE函数反映的是多序列比对和序列组中两两比对形成的扩展库之间的一致性程度。COFFEE函数的提出可以让更多的双序列比对算法思想用于多序列比对，且其准确性相较于比对和函数有所提升，尤其在序列相似度较低时，但其计算的速度相较于比对和函数更慢。

COFFEE函数的使用主要由两部分组成：(www.chuimin.cn)

（1）根据双序列比对建立扩展库，扩展库中至少需包含序列组中所有两两比对的情况；

（2）计算多序列比对和扩展库信息一致性的COFFEE函数。具体的COFFEE函数计算公式如下：

其中，Aij代表序列Si和Sj的双序列比对，len（Aij）代表比对长度，score（Aij）代表多序列比对和扩展库中Aij比对结果的匹配残基数目，Wij表示双序列比对的权值，该权值最简单的计算方式是直接赋值为双序列比对相似度百分比。

目标函数在形式化开发多序列比对算法中的重要性

相关推荐