基于动态规划的双序列比对算法构件设计与实现

来源：计算机研究与发展杂志2019年第9期北京时间：

作者：石海鹤,周卫星,

摘要：双序列比对算法是生物信息学中的一个关键算法，广泛应用于序列相似性分析以及基因组序列数据库搜索.现有研究主要针对特定应用问题优化和使用相对应比对算法，缺乏高抽象层算法框架的细致研究，在一定程度上导致了序列比对算法的冗余性以及人为选择算法可能造成的误差等问题，也使得人们难以有效地了解算法结构.通过深入分析基于动态规划的双序列比对算法(dynamicprogramming-basedpairwisesequencealignmentalgorithm,DPPSAA)领域，在建立该算法领域的特征模型以及对应算法构件交互模型基础上，利用PAR平台形式化实现双序列比对算法构件库，并装配生成具体算法，保证了形式化装配算法的可靠性，为序列相似性分析算法应用提供了一条有价值的参考途径.最后，利用PAR平台C++程序生成系统将组装的比对算法转换为C++程序，运行结果表明DPPSAA算法构件库具有一定的实用性.

关键词：双序列比对算法, 动态规划, 特征模型, 构件交互模型, PAR平台,