虚线箭头表示在算法执行过程中两个构件之间需进行交互，例如多序列比对模式构件需调用双序列比对构件、目标函数构件、系统发生树构件来进行组装操作。......
2023-10-25
4.3秒速完成多序列比对的算法
【摘要】：由此可见，双序列比对也是MSAA的重要组成部分。在多序列比对中常用的双序列比对算法包括动态规划算法和启发式快速比对算法，动态规划算法主要包括NW算法、SW算法、Hirschberg算法等。本文研究中所需的双序列比对算法也是应用了《基于动态规划的双序列比对算法构件设计与实现》一文中的实现方式。以保留的种子片段在靶序列中出现的位置为基础进行两端的扩展，并形成比对，比对的方式可以是动态规划算法。
由于双序列比对算法可以找到两条序列之间的相似性区域，以及保守位点等信息，通过比对分值可对序列之间的距离远近进行初步的评估，因此目前很多常用多序列比对算法的第一步都是双序列比对，通过双序列比对对序列组进行初步的处理，以此为基础进行后续的算法步骤。由此可见，双序列比对也是MSAA的重要组成部分。
在多序列比对中常用的双序列比对算法包括动态规划算法和启发式快速比对算法，动态规划算法主要包括NW算法、SW算法、Hirschberg算法等。关于动态规划算法的分析，我们团队之前已进行了相关的研究。本文研究中所需的双序列比对算法也是应用了《基于动态规划的双序列比对算法构件设计与实现》一文中的实现方式。这一节主要对另一种启发式快速比对算法进行分析。
启发式快速比对算法通常基于分治法的算法思想，将序列比对问题通过其建立的索引进行划分，将问题转换为寻找各个片段的最优解。启发式算法主要有两种类型：基于哈希表索引的算法和基于后缀树索引的算法。FASTA、BLAST算法属于前者，MUMmer、AVID算法属于后者。此外，Wilbur和Lipman在1983年提出了一种基于k-mer匹配的全局比对算法。该算法大大缩小了比对所需的时间，且具有较高的准确性，适用于数据量较大的比对。这里我主要详细说明一下目前常用的BLAST算法，它属于基于哈希表的seed算法，广泛应用于数据库搜索。
BLAST算法步骤主要有四步，描述如下：
（1）寻找待比对序列与靶序列之间高度相似的片段。通过预设的长度对待比对序列进行切割形成种子片段，通常DNA种子片段的长度为3，蛋白质种子片段的长度为11。BLAST在这一步骤中会对种子片段进行筛选，过滤掉重复且复杂度极低的片段，避免后续产生过多无生物学意义的结果。(www.chuimin.cn)
（2）通过在数据库中建立的索引表，快速定位种子片段在候选序列中的位置。这里需要用到相应的替换矩阵计算比对分值，比对分值必须达到事先设定的阈值，才能保留其相应的种子片段。
（3）以保留的种子片段在靶序列中出现的位置为基础进行两端的扩展，并形成比对，比对的方式可以是动态规划算法。这里需预设一个阈值t，当扩展到比对得分低于t时结束，保留相应的比对结果。
（4）对比对结果进行评估。BLAST引入了E-value来评估比对结果的统计显著性，确保比对结果不是由随机因素产生的。
有关形式化开发多序列比对算法的文章
- 详细阅读
-
多序列比对算法：渐进式设计详细阅读
经过上述分析，我们可以对图5-2中的交互模型做进一步细化，将模型中关于渐进式比对的构件进行拆分，形成图5-4所示的渐进式多序列比对算法构件交互模型。图5-3常见的渐进式比对算法的步骤下面对关键构件进行简单的形式化描述，以便于该领域算法构件的实现。seq_check构件图5-4渐进式多序列比对算法构件交互模型msa_mode构件|[in user settings out msa_mode：ADT]|AQ：用户的相关设置。......
2023-10-25
-
多序列比对算法形式化实现详细阅读
本节根据MSAA的特征模型和渐进式比对算法构件的交互模型，利用Apla语言的高抽象性、对泛型及ADT的良好支持以及易于正确性验证等优点，来形式化实现多序列比对算法构件。prog构件该构件为ADT类型HMSAA中的泛型子程序，根据传入不同类型的计算比对步骤进行渐进式比对。result_op构件该构件为ADT类型，泛型子程序multiAlign_op在多序列比对结果的基础上，对结果进行格式化输出。......
2023-10-25
-
形式化开发多序列比对算法详细阅读
已经存在的多序列比对算法主要有三类：精确比对算法，渐进式比对算法和迭代比对算法。Thompson和Higgins于1994年对渐进式多序列比对算法进行了实现，提出了Clustal W算法。它在数据量较大和距离较远的序列比对中更准确，且消耗时间更短，该算法还在不断改进以适应数据量剧增的多序列比对需求。......
2023-10-25
-
多序列比对算法开发-构件组装与修改详细阅读
图6-1模块交互关系构件库模块。该模块主要包括两部分，一部分是存储在文件中已完成转换的构件源代码，另一部分是存储在数据库中需进行人工开发或修改的Apla构件组装代码。在完成构件选择后，该模块根据选择的构件，从后台数据库中获取所需的Apla组装代码，用户可对组装代码进行相应的修改，以正确调用构件库中被选择的构件。......
2023-10-25
-
领域分析：形式化开发多序列比对算法详细阅读
通过对目前常用的多序列比对算法进行研究，利用FODM的建模方法对MSAA进行特征建模。多序列比对操作是MSAA的核心服务，双序列比对操作、系统发生树构建操作、启发式多序列比对操作，目标函数是该领域中的主要功能，其中双序列比对操作、系统发生树构建操作为可选择的功能，目标函数和启发式多序列比对是必选的功能。此外，目标函数计算参数选择也是其行为特点，包括罚分模型和替换矩阵两个值。图5-1MSAA的特征模型......
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
相关推荐