双序列比对线性空间算法的研究

摘要

序列比对是生物信息学中一种基本的信息处理问题，对于发现核酸和蛋白质序列上的功能、结构以及进化信息具有非常重要的意义。随着生物序列数据库中序列数据的激增，设计出能够处理大规模运算的并行算法就显得非常迫切。本文研究了生物信息学中的双序列比对及其并行算法，主要研究工作和取得的成果如下：
　　1.为了提升Hirschberg算法的性能，本论文利用共享存储的并行模型对Hirschberg算法进行了并行化设计，相对于Hirschberg算法，本文的并行Hirschberg算法不仅提升了时间性能，并且保持了线性的空间复杂度。
　　2.为了提升FA算法(Fast Alignment)的性能，本文把基于递归的FA算法改为了非递归算法，非递归FA算法进一步提高了时间性能，也同时保持了线性的空间复杂度。
　　本文给出了改进算法的实验设计和分析。实验表明，其运算效率较原算法均有所提高，为生物信息学的研究及实践提供进一步的支持。

目录

文摘

英文文摘

第一章 绪论

1.1 引言

1.2 生物信息学的序列比对

1.3 生物序列比对算法研究现状

1.4 论文主要研究内容

第二章 双序列全局比对算法

2.1 序列比对算法基础

2.2 序列比对算法中的动态规划算法

2.2.1 算法思想

2.2.2 算法伪代码描述

2.2.3 算法分析

2.3 线性空间Hirschberg算法

2.3.1 算法理论依据

2.3.2 算法思想

2.3.3 算法分析

第三章 并行Hirschberg算法

3.1 并行计算简介

3.1.1 并行计算定义

3.1.2 并行计算的研究内容

3.2 并行算法设计原则

3.3 并行OpenMP技术

3.4 影响并行Hirschberg算法性能的因素

3.4.1 数据分解

3.4.2 任务与交互

3.4.3 负载平衡的映射技术

3.4.4 伪共享

3.4.5 同步

3.5 并行Hirschberg算法的设计与实现

3.6 实验结果及分析

第四章 非递归FA算法

4.1 FA算法介绍

4.2 非递归FA算法的设计与实现

4.2.1 算法思想

4.2.2 算法伪代码描述

4.2.3 算法详细实现

4.3 实验结果及分析

第五章 结束语

5.1 全文总结

5.2 研究的不足和前景

致谢

参考文献