生物信息学中序列拼接程序的并行化研究

摘要

该文主要就是针对当前应用最为广泛的一个拼接程序phrap来作出分析,加以并行化改造以期在存储和时间上有所优化,扩展其处理能力并使得现有的计算资源能容纳更多的拼接任务.文章首先介绍了序列拼接所依赖的理论基础,然后着重分析了程序的数据结构,流程和主要函数,为并行化作好准备并提供方向.在第三和第四章分别针对phrap占用内存量大和运行时间的问题作出了并行化的改造.第五章就今后的工作的方向重点阐述了个人观点.该文主要贡献如下：1.针对目前还没有解决方案的phrap大量消耗存储问题,在集群上用共享存储的方式进行了改造,使得起码一半的内存消耗可以在集群各节点上基本均匀的分布,突破了phrap对单节点可用资源的依赖.对于一定的计算资源,从整体上扩充了其处理数据的能力,从而一定程度内缓解了当前数据产生速度和处理速度之间的矛盾.而且其中对内存分布的分析信息对以后同类工作提供了极大的便利.2.分析phrap中一个主要的耗时部分：序列拼接过程.对原来只能串行执行的过程挖掘出了其隐藏的并行性,实现并进行了测试,就作者所知,当前对怕phrap的时间优化主要是从程序的序列比对部分入手,针对拼接部分的算法优化是没有先例的,这部分的工作对phrap的优化在理论上是一个切实的推进,目前phrap中的主要部分都已经没有了结构上的串行性,对于以后的工作带来很大的便利.

目录

文摘

英文文摘

声明

第一章绪论

1.1生物信息学

1.2生物相关性

1.3生物序列

1.4生物序列的比较

1.4.1演化模型

1.4.2两序列联配

1.4.3全局联配

1.4.4局部联配

1.4.5 gap函数的讨论

1.4.6多序列联配

1.5小结

第二章拼接程序Phrap的分析

2.1测序简介

2.2序列拼接问题的描述

2.3 Phrap原理算法简介

2.3.1寻找重合部分

2.3.2决定over l ap的使用模式

2.3.3建立conti g数据

2.4 Phrap框架流程

2.5 Phrap的主要数据结构

2.6主要函数描述

2.7主要函数解析

2.7.1 readi n and match()

2.7.2 merge_master()

2.7.3 make conti g_db()

2.8小结

第三章phrap程序的并行化

3.1 Phrap程序的并行化需求

3.2并行编程模型简介

3.3 Phrap的资源消耗及可并行性分析

3.3.1资源消耗分析

3.3.2 readi n and match()函数分析

3.3.3 merge_master()的分析

3.3.4 make_conti g_db()函数分析

3.4共享存储模型下的并行化

3.4.1 get_parameters()的修改

3.4.2 readi ng_and_match()的修改

3.4.3 merge_master()的修改

3.4.4 make_contig_db()

3.5小结

第四章Phrap拼接部分的并行化

4.1工作背景

4.2基于SUP的多线程并行化

4.3 merge_master()中的并行化

4.4国际上关于phrap并行化的研究

4.5小结

第五章总结与展望

参考文献

致谢

作者简历