领域分析：形式化开发多序列比对算法

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

【摘要】：通过对目前常用的多序列比对算法进行研究，利用FODM的建模方法对MSAA进行特征建模。多序列比对操作是MSAA的核心服务，双序列比对操作、系统发生树构建操作、启发式多序列比对操作，目标函数是该领域中的主要功能，其中双序列比对操作、系统发生树构建操作为可选择的功能，目标函数和启发式多序列比对是必选的功能。此外，目标函数计算参数选择也是其行为特点，包括罚分模型和替换矩阵两个值。图5-1MSAA的特征模型

通过对目前常用的多序列比对算法进行研究，利用FODM的建模方法对MSAA进行特征建模。多序列比对操作是MSAA的核心服务，双序列比对操作（PSAA）、系统发生树构建操作（PTA）、启发式多序列比对操作（HMSAA），目标函数（OF）是该领域中的主要功能，其中双序列比对操作、系统发生树构建操作为可选择的功能，目标函数和启发式多序列比对是必选的功能。对每个功能的描述仅关注主要组成部分，动态规划比对（DP）和快速比对（fast）是双序列比对操作的子功能，对于动态规划比对，动态规划模式选择（DP_mode）是其行为特点。该维度有两个值，分别是标准动态规划算法（normal），以及优化时空消耗的动态规划算法（space_opti）。距离法（dist），最大似然法（ML），最大简约法（MP）是系统发生树构建操作的子功能，对于距离法和最大似然法，遗传模型选择（genetic_model）是其行为特点。该维度有多个值，这里只显示了常用的遗传模型，分别是kimura两参数模型（kimura）和Judes-Cantor单参数模型（JC）。距离法有一个行为特点是对聚类算法的选择（dist_algorithm）。该维度主要有两个值，邻接法（NJ）和非加权配对算术平均法（UPGMA）。渐进式比对（prog）和迭代比对（iter）是启发式多序列比对的子功能，对于渐进式比对，渐进比对模式（prog_mode）是其行为特点。该维度有三个值，分别是基于系统发生树的比对（tree）、基于扩展库的比对（extend lib）和中心星比对（center）。对于迭代比对，迭代模式选择（iter_mode）是其行为特点。该维度可以有多个值，图5-1中只标出了迭代渐进式比对（ProgIter）以及基于隐马尔可夫模型（hidden markov）的迭代算法。对于目标函数（OF），目标函数选择（OF_sel）是其行为特点，包括一致性函数（COFFEE）和比对和函数（SP）两个值。此外，目标函数计算参数选择（para_set）也是其行为特点，包括罚分模型（penalty）和替换矩阵（sub Matrix）两个值。MSAA的特征模型如图5-1所示。

pagenumber_ebook=43,pagenumber_book=36 (www.chuimin.cn)

图5-1　MSAA的特征模型

领域分析：形式化开发多序列比对算法

相关推荐