通过对目前常用的多序列比对算法进行研究，利用FODM的建模方法对MSAA进行特征建模。多序列比对操作是MSAA的核心服务，双序列比对操作、系统发生树构建操作、启发式多序列比对操作，目标函数是该领域中的主要功能，其中双序列比对操作、系统发生树构建操作为可选择的功能，目标函数和启发式多序列比对是必选的功能。此外，目标函数计算参数选择也是其行为特点，包括罚分模型和替换矩阵两个值。图5-1MSAA的特征模型......
2023-10-25
形式化开发多序列比对算法
【摘要】：已经存在的多序列比对算法主要有三类：精确比对算法，渐进式比对算法和迭代比对算法。Thompson和Higgins于1994年对渐进式多序列比对算法进行了实现，提出了Clustal W算法。它在数据量较大和距离较远的序列比对中更准确，且消耗时间更短，该算法还在不断改进以适应数据量剧增的多序列比对需求。
多序列比对是生物信息学中的核心问题之一，在序列分析、序列注释、基因和蛋白质的结构功能预测以及系统发育和进化分析等方面应用广泛。因多序列比对问题的NP完全性，目前研究人员都致力于寻找解决该问题的近似最优解，且已有的研究大多针对特定问题或特定算法，针对目标函数参数的优化也有一定的研究，但却甚少涉及算法的领域层面，存在着可重用性和开发效率较低、冗余性过高等问题。已经存在的多序列比对算法主要有三类：精确比对算法，渐进式比对算法和迭代比对算法。精确比对算法是动态规划思想在多序列比对问题中的实现，但其难以应用于实际研究，因此不加赘述。渐进式多序列比对算法的思想是于1987年由Feng和Doolittle提出的，它的基本思想是：进行比对的多条序列之间存在或远或近的进化关系，在确定序列的进化顺序后，沿着进化顺序对序列逐步进行比对，直到所有的序列都比对完毕，因此在进行渐进比对之前，需要先找到序列之间的进化关系。Thompson和Higgins于1994年对渐进式多序列比对算法进行了实现，提出了Clustal W算法。渐进式多序列比对算法最主要的缺点在于它的“一旦空位，永远空位”原则，比对过程中产生的错误会一直影响序列比对过程，导致算法得不到最优的比对结果，降低了算法精度，且无法处理大规模数据。Lassmann等在2005年运用Wu-Manber近似字符串匹配算法优化了距离矩阵的计算与渐进式比对的操作，进而提出了Kalign算法。它在数据量较大和距离较远的序列比对中更准确，且消耗时间更短，该算法还在不断改进以适应数据量剧增的多序列比对需求。此外，HAlign算法则是根据中心星比对的渐进式比对算法。为了提高比对的精度，获得更好的性能，我们主要使用迭代和一致性函数两种策略对渐进式思想进行优化。Notredame等人在2000年提出了T-Coffee（tree-based consistency objective function foralignment evaluation）算法。该算法利用一致性函数对渐进式比对算法进行了优化，提高了比对结果的质量，但比对的时间消耗也增加了。迭代比对的基本思想是：首先基于可以快速产生比对的算法，形成初步的比对结果，并通过一系列迭代来改进多序列比对，直到比对结果不再改善或是已经到了既定的迭代次数为止。利用迭代比对思想优化渐进式比对算法可以提高算法的鲁棒性，弥补了“一旦空位，永远空位”的缺陷，同时也拓宽了算法的适用范围。这类算法常见的有MAFFT、MUSCLE等。此外，还可以用基于随机优化的算法来迭代计算，如遗传算法、隐马尔可夫模型、模拟退火等策略。目前，Clustal算法的最新版本Clustal Omega算法也使用了基于隐马尔可夫模型的HHalign算法来调整最后的Profile比对。下面对Clustal W算法和MUSCLE算法的步骤进行分析。
Clustal W的算法步骤描述如下，算法图解如图4-3所示：
图4-3 Clustal W算法图解
（1）双序列比对。将比对序列组进行两两之间的比对，通过双序列比对得分建立距离矩阵（distance matrix），用来表示序列间的距离。
（2）生成系统发生树（phylogenetic tree）。利用距离矩阵中的信息，通过相应的聚类算法建立系统发生树，以指导后续的多序列比对操作。
（3）渐进式比对。先前的操作已生成了一棵指导树，最后一步就是根据指导树所反映出的比对顺序，从进化关系近的开始，以保留空位的形式逐步完成所有序列的比对。(www.chuimin.cn)
MUSCLE算法的步骤描述如下，算法图解如图4-4所示：
图4-4 MUSCLE算法图解
（1）粗略的渐进式比对（draft progressive）。这一步需要以较快的速度生成一个粗略的多序列比对，作为后续迭代精化的基础。首先使用基于k-mer的双序列比对生成距离矩阵D1，通过UPGMA方法生成系统发生树TREE1，进一步完成粗略的多序列比对MSA1。
（2）优化的渐进式比对（improved progressive）。在第一步中，误差产生的原因主要是根据k-mer双序列比对算法得出的距离矩阵误差较大，因此第二步利用MSA1的信息基于Kimura遗传模型计算新的距离矩阵D2，接着使用D2通过UPGMA方法生成TREE2，根据TREE2计算优化的渐进式比对MSA2。
（3）精化比对结果。删除一条边，将TREE2一分为二，再分别进行渐进式比对，计算profile-profile比对的SP值，保留SP值增加的情况，如果所有的边都不再发生变化或达到了用户定义的迭代次数，则算法停止，输出结果。
有关形式化开发多序列比对算法的文章
- 详细阅读
-
多序列比对算法形式化实现详细阅读
本节根据MSAA的特征模型和渐进式比对算法构件的交互模型，利用Apla语言的高抽象性、对泛型及ADT的良好支持以及易于正确性验证等优点，来形式化实现多序列比对算法构件。prog构件该构件为ADT类型HMSAA中的泛型子程序，根据传入不同类型的计算比对步骤进行渐进式比对。result_op构件该构件为ADT类型，泛型子程序multiAlign_op在多序列比对结果的基础上，对结果进行格式化输出。......
2023-10-25
-
《形式化开发多序列比对算法》实验结果与分析详细阅读
本实验采用C++语言，使用VS2019集成开发环境。替换矩阵采用Clustal W中默认的IUB矩阵。最终比对结果与Clustal W和Clustal O的比对结果，如图5-7所示。图5-7算法结果比较通过对PAR方法和PAR平台的使用，我们运用Apla语言以半自动的方式组装形成了基于系统发生树的渐进式比对算法，并将Apla程序转换成了C++代码，得到了可运行的算法程序，算法结果与Clustal W和Clustal O进行了比较，基本的保守位点和相似区域都可有效发现，具有一定的生物学意义。......
2023-10-25
-
多序列比对算法的形式化开发方法详细阅读
变换的开始、中间到结束、产物是一符号串，这种形式化方法称为完全形式化方法。所以，目前软件开发的形式化方法主要是以部分形式化方法为主。总体上，形式化软件开发方法大致可分为以下五类：基于模型的方法。......
2023-10-25
-
目标函数在形式化开发多序列比对算法中的重要性详细阅读
在序列比对的过程中，由于无法使用能否准确反映生物学意义这一概念来衡量序列比对结果的质量，因此我们引入了目标函数这一数学模型对序列比对结果进行评价。然而，在多序列比对中，目标函数的计算要复杂得多，且如何选择合适的目标函数也需要加以考虑。理论上目标函数可以尽可能准确、有效地反映多序列比对结果的质量，并能发现更多的生物学意义。目前，对于目标函数的研究还在持续地进行，相关的优化方式也在不断提出。......
2023-10-25
-
多序列比对算法开发-构件组装与修改详细阅读
图6-1模块交互关系构件库模块。该模块主要包括两部分，一部分是存储在文件中已完成转换的构件源代码，另一部分是存储在数据库中需进行人工开发或修改的Apla构件组装代码。在完成构件选择后，该模块根据选择的构件，从后台数据库中获取所需的Apla组装代码，用户可对组装代码进行相应的修改，以正确调用构件库中被选择的构件。......
2023-10-25
- 详细阅读
-
领域设计：多序列比对算法详细阅读
虚线箭头表示在算法执行过程中两个构件之间需进行交互，例如多序列比对模式构件需调用双序列比对构件、目标函数构件、系统发生树构件来进行组装操作。......
2023-10-25
相关推荐