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

论文摘要

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

论文目录

• 1 比对算法的建模过程
•   1.1 领域分析
•   1.2 特征建模流程
•   1.3 DPPSAA领域特征建模
• 2 比对算法构件的设计与实现
•   2.1 DPPSAA领域算法构件交互设计
•   2.2 Apla形式化实现
•     1) 罚分模型以及得分矩阵元素结构设计
•     2) 得分矩阵操作
•     3) 动态规划算法方式选择
•     4) 检查序列合法性
•     5) 记住得分来源
•     6) 回溯
•     7) 比对结果输出
•     8) 比对操作
• 3 NW算法的装配实现
• 4 实验及其结果分析
• 5 相关研究比较
• 6 结束语

文章来源

类型: 期刊论文

作者: 石海鹤,周卫星

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

来源: 计算机研究与发展 2019年09期

年度: 2019

分类: 信息科技,基础科学

专业: 数学,生物学

单位: 江西师范大学计算机信息工程学院

基金: 国家自然科学基金项目(61662035,61762049,61862033)~~

分类号: O221.3;Q811.4

页码: 1907-1917

总页数: 11

文件大小: 2275K

下载量: 149