多序列比对算法形式化实现

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

【摘要】：本节根据MSAA的特征模型和渐进式比对算法构件的交互模型，利用Apla语言的高抽象性、对泛型及ADT的良好支持以及易于正确性验证等优点，来形式化实现多序列比对算法构件。prog构件该构件为ADT类型HMSAA中的泛型子程序，根据传入不同类型的计算比对步骤进行渐进式比对。result_op构件该构件为ADT类型，泛型子程序multiAlign_op在多序列比对结果的基础上，对结果进行格式化输出。

本节根据MSAA的特征模型和渐进式比对算法构件的交互模型，利用Apla语言的高抽象性、对泛型及ADT的良好支持以及易于正确性验证等优点，来形式化实现多序列比对算法构件。由于主要是说明如何用Apla语言刻画算法构件，因此，本文只介绍基于树的渐进比对算法。基于动态规划的双序列比对构件在我们团队之前的工作中已经实现，所以本文只对其他构件予以介绍，在程序代码中只给出了对于MSAA构件的定义以及关键参数的具体释义。

（1）seq_check构件

检查序列组是否满足生物学定义，例如DNA序列的字符集为{A，T，C，G}。

（2）目标函数构件

为了便于目标函数的设置，将sp定义为ADT，同时将目标函数构件也设计为ADT，使用的是仿射空位罚分模型。gapOpen表示开放空位罚分，gapExtend表示扩展空位罚分，subMatrix表示替换矩阵的分值，并通过子程序setOFpara设置具体参数的取值。泛型子程序getOF中定义了泛型操作参数comp，可运用比对和函数或COFFEE函数计算目标函数的值。

（3）msa_mode构件

我们将msa_mode构件定义为一个ADT，它主要进行多序列比对操作模式的选择，以及对需要的数据结构和信息进行初始化。泛型子程序msa根据用户在组装过程中传入的ADT类型，生成不同的多序列比对算法。

（4）dist_matrix构件(www.chuimin.cn)

该构件包含一个泛型子程序calDistMat，可传入不同类型的双序列比对操作和遗传模型，利用序列组中的两两比对得分计算距离矩阵。函数get-Dist的作用是返回两条序列的距离值。

（5）phy_tree构件

我们首先将phylotree的数据结构定义为一个ADT，便于后续对树进行操作。将phy_tree构件也定义为ADT，该构件利用距离矩阵中序列间的距离计算系统发生树，该ADT内部包含泛型子程序generateTreeByDist，并将selAlgorithm作为它的泛型操作参数，可以通过不同的生成树算法生成系统发生树。calWeight子程序表示计算多序列比对得分所需的各个序列的权值，readTree子程序用于读取已生成的系统发生树中的信息，函数getSteps用于获取后续多序列比对的顺序。

（6）prog构件

该构件为ADT类型HMSAA中的泛型子程序，根据传入不同类型的计算比对步骤进行渐进式比对。

（7）result_op构件

该构件为ADT类型，泛型子程序multiAlign_op在多序列比对结果的基础上，对结果进行格式化输出。格式化模式常用的有Clustal W格式、Phylip格式、Html格式等。运用format泛型操作参数指定输出的格式化模式。子程序phyloTree_op将系统发生树结果进行输出。

多序列比对算法形式化实现

相关推荐