已经存在的多序列比对算法主要有三类：精确比对算法，渐进式比对算法和迭代比对算法。Thompson和Higgins于1994年对渐进式多序列比对算法进行了实现，提出了Clustal W算法。它在数据量较大和距离较远的序列比对中更准确，且消耗时间更短，该算法还在不断改进以适应数据量剧增的多序列比对需求。......
2023-10-25
形式化开发多序列比对算法：最具生物学意义的仿射空位罚分模型
【摘要】：仿射空位罚分模型是目前应用最广泛，且最具备生物学意义的罚分模型，它同时考虑了空位长度与空位发生对序列比对的影响。
由于序列比对中存在删除和插入的编辑现象，因此需要引入空位来进行描述，在比对结果中用符号“-”表示。空位现象产生的情况可能是只需要插入一个空位，也可能是需要插入一连串的空位。在插入空位时，我们需要考虑空位所处的位置、序列中空位的数量和连续空位的长度。目前常用的空位罚分模型有如下几种：
（1）常量空位罚分模型。这种空位罚分模型的特点是，序列比对中发生的所有空位均用一个相同的常量gap进行罚分，整个比对的总罚分wk为：
由于该模型未考虑在基因的不同位点上发生突变的概率不同，不具备相应的生物学意义，因此仅用于理论研究。
（2）恒定空位罚分模型。该模型同样仅用于理论研究，因为它将连续的空位当作一个空位来计算，忽略了空位长度对序列比对的影响，不具备应有的生物学意义。(www.chuimin.cn)
（3）仿射空位罚分模型。仿射空位罚分模型是目前应用最广泛，且最具备生物学意义的罚分模型，它同时考虑了空位长度与空位发生对序列比对的影响。它包括开放空位罚分（gap opening penalty）和扩展空位罚分（gap extension penalty）。对于一个连续长度为k的空格，其罚分wk的计算公式为：
通过分析大量的实验结果，我们发现连续空位发生的概率大于间隔空位发生的概率，因此实际应用中，开放空位罚分的值会大于扩展空位罚分的值。
有关形式化开发多序列比对算法的文章
- 详细阅读
-
领域分析：形式化开发多序列比对算法详细阅读
通过对目前常用的多序列比对算法进行研究，利用FODM的建模方法对MSAA进行特征建模。多序列比对操作是MSAA的核心服务，双序列比对操作、系统发生树构建操作、启发式多序列比对操作，目标函数是该领域中的主要功能，其中双序列比对操作、系统发生树构建操作为可选择的功能，目标函数和启发式多序列比对是必选的功能。此外，目标函数计算参数选择也是其行为特点，包括罚分模型和替换矩阵两个值。图5-1MSAA的特征模型......
2023-10-25
-
多序列比对算法形式化实现详细阅读
本节根据MSAA的特征模型和渐进式比对算法构件的交互模型，利用Apla语言的高抽象性、对泛型及ADT的良好支持以及易于正确性验证等优点，来形式化实现多序列比对算法构件。prog构件该构件为ADT类型HMSAA中的泛型子程序，根据传入不同类型的计算比对步骤进行渐进式比对。result_op构件该构件为ADT类型，泛型子程序multiAlign_op在多序列比对结果的基础上，对结果进行格式化输出。......
2023-10-25
-
多序列比对算法的形式化开发方法详细阅读
变换的开始、中间到结束、产物是一符号串，这种形式化方法称为完全形式化方法。所以，目前软件开发的形式化方法主要是以部分形式化方法为主。总体上，形式化软件开发方法大致可分为以下五类：基于模型的方法。......
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
-
多序列比对算法开发-构件组装与修改详细阅读
图6-1模块交互关系构件库模块。该模块主要包括两部分，一部分是存储在文件中已完成转换的构件源代码，另一部分是存储在数据库中需进行人工开发或修改的Apla构件组装代码。在完成构件选择后，该模块根据选择的构件，从后台数据库中获取所需的Apla组装代码，用户可对组装代码进行相应的修改，以正确调用构件库中被选择的构件。......
2023-10-25
-
领域设计：多序列比对算法详细阅读
虚线箭头表示在算法执行过程中两个构件之间需进行交互，例如多序列比对模式构件需调用双序列比对构件、目标函数构件、系统发生树构件来进行组装操作。......
2023-10-25
相关推荐