| 摘要 | 第1-5页 |
| ABSTRACT | 第5-7页 |
| 目录 | 第7-10页 |
| 1 绪论 | 第10-20页 |
| ·生物信息学 | 第10-13页 |
| ·概述 | 第10-11页 |
| ·简单分子生物学基础 | 第11-12页 |
| ·生物信息学的部分研究领域 | 第12-13页 |
| ·本文的研究内容 | 第13-14页 |
| ·生物序列模体发现 | 第13-14页 |
| ·基因组序列比较算法 | 第14页 |
| ·文献资源 | 第14-16页 |
| ·论文组织 | 第16-20页 |
| 2 算法理论基础和并行计算模型 | 第20-32页 |
| ·算法复杂性的度量和算法分析的方法 | 第20-24页 |
| ·算法的概念和复杂性度量 | 第20-21页 |
| ·NP完全算法 | 第21-23页 |
| ·并行算法的概念和复杂性度量 | 第23-24页 |
| ·传统的并行计算模型 | 第24-28页 |
| ·PRAM模型——SM-SIMD模型 | 第25-26页 |
| ·分布存储SIMD模型——DM-SIMD模型 | 第26页 |
| ·异步PRAM模型——SM-MIMD模型 | 第26-27页 |
| ·BSP模型——DM-MIMD模型 | 第27页 |
| ·LogP模型——MPP模型 | 第27-28页 |
| ·其它新型计算模型 | 第28页 |
| ·Cell Matrix模型——纳米计算模型 | 第28页 |
| ·LARPBS模型——可重构光总线系统模型 | 第28页 |
| ·并行算法的基本设计技术 | 第28-30页 |
| ·本章小结 | 第30-32页 |
| 3 DNA序列模体发现的组合算法 | 第32-44页 |
| ·模体发现问题 | 第32-35页 |
| ·DNA序列上模体发现生物背景 | 第32-34页 |
| ·DNA序列上模体发现问题基本定义 | 第34-35页 |
| ·基于序列比较和样本驱动的模体发现算法 | 第35-41页 |
| ·简单模式驱动和样本驱动算法 | 第35-36页 |
| ·基因组序列比较算法 | 第36-40页 |
| ·算法试验性能分析 | 第40-41页 |
| ·本章小结 | 第41-44页 |
| 4 基于纳米计算模型的生物序列模体发现和生物序列比对算法 | 第44-70页 |
| ·Cell Matrix模型简介 | 第44-54页 |
| ·纳米计算机与Cell Matrix模型 | 第45-47页 |
| ·Cell Matrix模型上算法时空开销分析 | 第47-54页 |
| ·Cell Matrix模型上的双序列比对 | 第54-61页 |
| ·Cell Matrix上的计算双序列比对分值的算法 | 第55-59页 |
| ·改进的Cell Matrix上的双序列比对算法 | 第59-61页 |
| ·双序列比对实现的开销分析 | 第61页 |
| ·Cell Matrix模型上的序列模体发现算法 | 第61-67页 |
| ·模体发现问题模型和模式驱动算法 | 第61-63页 |
| ·Cell Matrix模型上的模式驱动算法 | 第63-66页 |
| ·Cell Matrix上的模式驱动算法复杂性分析 | 第66-67页 |
| ·本章小结 | 第67-70页 |
| 5 PRAM和LARPBS模型上的有向符号排列翻转排序问题并行算法 | 第70-98页 |
| ·基因组重排问题 | 第70-75页 |
| ·基因组序列的数学表示与翻转排序问题的定义 | 第71-73页 |
| ·基因组序列翻转距离的计算 | 第73-75页 |
| ·基于PRAM模型并行计算有向符号排列翻转距离 | 第75-82页 |
| ·并行构建有向符号序列断点图 | 第75-77页 |
| ·求有向符号序列断点图中圈数的并行算法 | 第77-79页 |
| ·求排列中障碍数目和堡垒的并行算法 | 第79-82页 |
| ·计算有向符号排列翻转距离的O(log~2n)并行算法 | 第82页 |
| ·LARPBS系统上并行计算有向符号排列翻转距离 | 第82-92页 |
| ·LARPBS计算模型及其基本数据移动操作 | 第82-85页 |
| ·LARPBS模型上并行构建断点图 | 第85-87页 |
| ·LARPBS模型上并行计算有向序列断点图中圈数 | 第87-88页 |
| ·LARPBS模型上求障碍数目和堡垒的并行算法 | 第88-91页 |
| ·LARPBS模型上并行计算有向符号排列翻转距离算法总结 | 第91-92页 |
| ·LARPBS系统上的有向符号排列翻转排序并行算法 | 第92-96页 |
| ·有向符号排列翻转排序的基本策略 | 第92-93页 |
| ·LARPBS模型上有向排列翻转排序并行算法 | 第93-96页 |
| ·本章小结 | 第96-98页 |
| 6 计算有向符号排列的翻转中值排列 | 第98-122页 |
| ·中值序列问题研究背景和基本定义 | 第98-104页 |
| ·基因组的距离和生物进化树 | 第99-101页 |
| ·重建进化树和三条基因组序列求中值 | 第101-102页 |
| ·三条基因组序列求中值问题定义 | 第102-104页 |
| ·基于翻转距离的三点中值问题简单算法 | 第104-110页 |
| ·有向符号序列的翻转图和求翻转中值简单算法 | 第104-106页 |
| ·三条有向序列翻转中值的性质和改进算法 | 第106-110页 |
| ·求三条有向序列翻转中值的分支限界算法 | 第110-117页 |
| ·求三条有向序列翻转中值的分支限界策略 | 第110-113页 |
| ·三条有向序列翻转中值的分支限界算法 | 第113-116页 |
| ·三条有向序列翻转中值的算法试验性能分析 | 第116-117页 |
| ·基于其它基因组重排机制的中值问题 | 第117-118页 |
| ·本章小结 | 第118-122页 |
| 7 总结 | 第122-126页 |
| ·本文工作 | 第122-123页 |
| ·本文贡献和创新之处 | 第123-124页 |
| ·进一步的工作 | 第124-126页 |
| 附录 | 第126-128页 |
| A 算法索引 | 第126页 |
| B 插图索引 | 第126-127页 |
| C 表格索引 | 第127-128页 |
| 致谢 | 第128-129页 |
| 在读期间所参加的科研项目 | 第129-130页 |
| 在读期间所发表和录用的论文 | 第130页 |
