生物序列数据比较与模体发现算法研究

论文摘要

生物信息学是将计算机领域内的知识和技术应用于研究DNA(脱氧核糖核酸)、蛋白质等生物学问题的一个迅速发展的学科领域，而生物序列比较和模式发现是生物信息学的传统课题，在系统进化、基因调控、疾病治疗、病毒起源等重要领域的研究中处于核心地位。 近年来，随着生物测序技术的突飞猛进，生物序列数据以前所未有的速度增长。人工分析和处理生物序列数据无法再满足需求，计算机和网络技术的飞速发展，为分析和处理生物序列提供了新的强大手段。本文围绕生物序列信息比较与模体(motif)发现算法问题展开研究，完成以下工作： (1) DNA序列模体发现算法研究 DNA序列是最常见的生物序列数据，在DNA序列集合中发现模体的常见方法有统计学习方法和组合优化方法。本文围绕目前最常用的FM(Fixed number of Mutation)模体发现模型展开研究，首先给出一种基于样本序列比较来组合生成候选模体的方法，然后在此基础上设计出一种新的基于样本驱动的精确算法，与现有的模式驱动算法相比，在保持精度不变的情况下降低了搜索空间，同时克服了样本驱动算法适用面窄的问题。实验表明，该算法相对目前最优的MITRA(Mismatched Tree Algorithms)精确算法的性能有了较大的提高。 (2) 纳米计算平台的生物序列处理研究 对生物序列进行比较和在生物序列中发现模体往往涉及大计算量，因此并行化的设计是必不可少的，但是问题本身的串行处理特性使得并行处理较为困难。目前已提出的一种新的纳米计算平台上的系统结构模型——Cell Matrix能较好的解决序列处理问题，其同构的二维结构便于生产和扩展，用该结构来实现序列处理算法非常自然。本文实现了可以输出比对结果的双序列比对算法，它克服了Cell Matrix模型上已有的双序列比对算法只能输出比对得分的缺陷；首次在Cell Matrix模型上设计实现了生物序列模体发现算法。并用品格数量和晶格延迟两个参数分析了两个算法的时空开销。 (3) 基因组序列的翻转排序并行算法研究 基因组序列在遗传过程中最常见变异现象为部分子序列翻转。通过对翻转排序问题串行算法的研究，在PRAM模型和LARPBS模型上分别设计出时间复杂度为O(lg~2n)和O(lgn)的并行计算有向符号序列翻转距离算法(n为序列的长度)；同时在LARPBS模型上设计出一个线性时间并行翻转排序算法。

论文目录

• 摘要
• ABSTRACT
• 目录
• 1 绪论
• 1.1 生物信息学
• 1.1.1 概述
• 1.1.2 简单分子生物学基础
• 1.1.3 生物信息学的部分研究领域
• 1.2 本文的研究内容
• 1.2.1 生物序列模体发现
• 1.2.2 基因组序列比较算法
• 1.3 文献资源
• 1.4 论文组织
• 2 算法理论基础和并行计算模型
• 2.1 算法复杂性的度量和算法分析的方法
• 2.1.1 算法的概念和复杂性度量
• 2.1.2 NP完全算法
• 2.1.3 并行算法的概念和复杂性度量
• 2.2 传统的并行计算模型
• 2.2.1 PRAM模型——SM-SIMD模型
• 2.2.2 分布存储SIMD模型——DM-SIMD模型
• 2.2.3 异步PRAM模型——SM-MIMD模型
• 2.2.4 BSP模型——DM-MIMD模型
• 2.2.5 LogP模型——MPP模型
• 2.3 其它新型计算模型
• 2.3.1 Cell Matrix模型——纳米计算模型
• 2.3.2 LARPBS模型——可重构光总线系统模型
• 2.4 并行算法的基本设计技术
• 2.5 本章小结
• 3 DNA序列模体发现的组合算法
• 3.1 模体发现问题
• 3.1.1 DNA序列上模体发现生物背景
• 3.1.2 DNA序列上模体发现问题基本定义
• 3.2 基于序列比较和样本驱动的模体发现算法
• 3.2.1 简单模式驱动和样本驱动算法
• 3.2.2 基因组序列比较算法
• 3.2.3 算法试验性能分析
• 3.3 本章小结
• 4 基于纳米计算模型的生物序列模体发现和生物序列比对算法
• 4.1 Cell Matrix模型简介
• 4.1.1 纳米计算机与Cell Matrix模型
• 4.1.2 Cell Matrix模型上算法时空开销分析
• 4.2 Cell Matrix模型上的双序列比对
• 4.2.1 Cell Matrix上的计算双序列比对分值的算法
• 4.2.2 改进的Cell Matrix上的双序列比对算法
• 4.2.3 双序列比对实现的开销分析
• 4.3 Cell Matrix模型上的序列模体发现算法
• 4.3.1 模体发现问题模型和模式驱动算法
• 4.3.2 Cell Matrix模型上的模式驱动算法
• 4.3.3 Cell Matrix上的模式驱动算法复杂性分析
• 4.4 本章小结
• 5 PRAM和LARPBS模型上的有向符号排列翻转排序问题并行算法
• 5.1 基因组重排问题
• 5.1.1 基因组序列的数学表示与翻转排序问题的定义
• 5.1.2 基因组序列翻转距离的计算
• 5.2 基于PRAM模型并行计算有向符号排列翻转距离
• 5.2.1 并行构建有向符号序列断点图
• 5.2.2 求有向符号序列断点图中圈数的并行算法
• 5.2.3 求排列中障碍数目和堡垒的并行算法
• 2n）并行算法'>5.2.4 计算有向符号排列翻转距离的O（log²n）并行算法
• 5.3 LARPBS系统上并行计算有向符号排列翻转距离
• 5.3.1 LARPBS计算模型及其基本数据移动操作
• 5.3.2 LARPBS模型上并行构建断点图
• 5.3.3 LARPBS模型上并行计算有向序列断点图中圈数
• 5.3.4 LARPBS模型上求障碍数目和堡垒的并行算法
• 5.3.5 LARPBS模型上并行计算有向符号排列翻转距离算法总结
• 5.4 LARPBS系统上的有向符号排列翻转排序并行算法
• 5.4.1 有向符号排列翻转排序的基本策略
• 5.4.2 LARPBS模型上有向排列翻转排序并行算法
• 5.5 本章小结
• 6 计算有向符号排列的翻转中值排列
• 6.1 中值序列问题研究背景和基本定义
• 6.1.1 基因组的距离和生物进化树
• 6.1.2 重建进化树和三条基因组序列求中值
• 6.1.3 三条基因组序列求中值问题定义
• 6.2 基于翻转距离的三点中值问题简单算法
• 6.2.1 有向符号序列的翻转图和求翻转中值简单算法
• 6.2.2 三条有向序列翻转中值的性质和改进算法
• 6.3 求三条有向序列翻转中值的分支限界算法
• 6.3.1 求三条有向序列翻转中值的分支限界策略
• 6.3.2 三条有向序列翻转中值的分支限界算法
• 6.3.3 三条有向序列翻转中值的算法试验性能分析
• 6.4 基于其它基因组重排机制的中值问题
• 6.5 本章小结
• 7 总结
• 7.1 本文工作
• 7.2 本文贡献和创新之处
• 7.3 进一步的工作
• 附录
• A 算法索引
• B 插图索引
• C 表格索引
• 致谢
• 在读期间所参加的科研项目
• 在读期间所发表和录用的论文