基于DP的若干序列比对算法构件开发及其装配生成

发布时间：2020-07-04 12:14

【摘要】：序列比对是一种通过排列基因组序列来识别序列相似性区域,从而获得待比对序列之间的功能、结构或进化关系的技术。随着人类基因组计划的实施,测序技术的发展产生了大量的有关生物分子的原始序列数据,面对如此丰富的基因组序列数据,如何去高效处理和分析这些数据,比较两序列之间的相似区域和保守性位点,寻求序列同源结构,揭示生物遗传、变异和进化等问题,成为了序列比对算法研究的主要动力之一。目前,比对算法的研究大部分集中于序列比对算法问题域中的特定问题或者特定算法优化,而较少面向于整个序列比对算法问题域,难以得到一个具有更高抽象层次且适用于序列比对算法问题域的算法构件库,在一定程度上导致了序列比对算法的冗余性以及人为选择算法可能造成的误差等问题,也使得人们难以有效地了解算法结构,无法保证算法的正确使用,甚至于降低了序列比对结果的准确性。由于现有算法的专用性和低抽象性,不仅导致研究人员需要花费大量时间去学习和使用该类算法,降低了算法的可维护性和复用性,而且难以定位和解决算法产生的错误,加重了序列相似性分析的负担。通过深入分析基于动态规划的双序列比对算法(Dynamic Programming-based Pairwise Sequence Alignment Algorithm,DPPSAA)领域,利用产生式编程方法设计并建立了DPPSAA领域特征模型,其中主要包含特征模型和特征交互模型。然后利用PAR平台的高抽象程序设计语言Apla将上述领域特征模型中的特征作为构件进行形式化实现,并详细叙述了实现过程,建立了一个基于Apla程序的高抽象性的DPPSAA构件库,展示了基于该构件库装配形成Needleman-Wunsch算法的具体步骤。同时,利用PAR平台的C++程序转换系统,通过手动和自动结合的方式将上述构件库转换成为相对应的C++程序代码,并装配实现和运行了Needleman-Wunsch算法,结果表明通过DPPSAA构件库具有一定的实用性,在算法学习和实现方面有一定优势,为形式化装配实现序列比对算法提供了可能。之后以DPPSAA构件库为基础,改进和增加了部分构件库构件,使其能够支持装配基于DPPSAA构件库的多序列比对领域算法,并利用该扩充构件库,装配并实现了星比对算法,实验结果表明装配生成的星比对算法具有一定的实用性,不仅验证了DPPSAA构件库的复用性,且扩充了DPPSAA领域构件的适用范围。
【学位授予单位】：江西师范大学
【学位级别】：硕士
【学位授予年份】：2019
【分类号】：Q811.4;TP301.6
【图文】：

ADT转换结果

基于DP的若干序列比对算法构件开发及其装配生成

泛型子程序转换结果

【参考文献】