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

Design and Implementation of Pairwise Sequence Alignment Algorithm Components Based on Dynamic Programming

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

Pairwise sequence alignment algorithm is a key algorithm in bioinformatics, and it is widely used in sequence similarity analysis and genomic sequence database searching. The existing study mainly focuses on the optimization and use of relative alignment algorithms for specific application problems. To some extent, those studies lack a high-level algorithm framework that not only has led to the redundancy of the sequence alignment algorithms and the possible errors caused by the artificial selection algorithm, but also made the structure of algorithm difficult to be understood effectively. Through in-depth analysis of the dynamic programming-based pairwise sequence alignment algorithms domain(DPPSAA), a domain feature model and the corresponding algorithm component interactive model have been established, a DPPSAA component library has been formally implemented by the PAR platform, and a concrete algorithm has been assembled, thus the reliability of the algorithm for formal assembly is guaranteed, moreover a valuable reference for the application of sequence similarity analysis algorithms is provided. Finally, the C++ program generation system of PAR platform is used to transform the assembly alignment algorithm into C++ program and the running results show that the dynamic programming-based pairwise sequence alignment algorithm component library has certain practicability.