Motif Finding及其Closest String相关问题的算法研究

论文摘要

生物信息学(又称生物计算学)是一门生物学与计算机科学以及应用数学等学科相互交叉而形成的一门新兴学科，其主要任务是揭示海量生物学数据中蕴含的生物学意义、探索生命活动的奥秘。Motif Finding和Closest String问题都是生物计算中基础而重要的研究问题，在很多领域得到了广泛的应用，甚至生物计算以外的编码理论。近年来这两个问题得到了广泛的研究，如何应用最新的研究技术，如分布式系统和固定参数理论，为这两个问题提出更好的解决方案是本文研究的重点。论文在深入分析已有算法的基础上，提出了Motif Finding问题的分布式算法，并设计与实现了分布式系统，对问题进行有效求解，实际测试结果表明分布式算法是正确且高效的；综合已有算法的优点，提出了计算广义Closest String问题最优上界的新方法，对Closest String问题的下界进行了推导，设计并优化了下界相关算法，弥补了固定参数算法在d较大且不存在结果时运行时间太长的缺憾，为判断在下界是否存在结果和求所有解提供了快速有效的方法。论文对算法的设计思想及实现作了详细的说明，对测试结果也作了深入的分析，实验结果表明这些算法是可行且高效的。

论文目录

• 摘要
• ABSTRACT
• 第一章 绪论
• 1.1 生物信息学相关研究内容
• 1.2 Motif Finding问题
• 1.2.1 问题定义
• 1.2.2 研究现状
• 1.3 Closest String问题
• 1.3.1 问题定义
• 1.3.2 研究现状
• 1.4 Motif Finding问题与 Closest String问题的关系及研究意义
• 1.5 研究目标与内容
• 1.6 论文组织结构
• 第二章 MOTIF FINDING问题求解
• 2.1 典型算法
• 2.1.1 序列模型
• 2.1.2 从序列生成k分图
• 2.1.3 在k分图中寻找k-clique
• 2.2 新算法分析与设计
• 2.2.1 k分图形成算法
• 2.2.2 k-clique寻找算法
• 2.3 算法分布式处理
• 2.3.1 生成k分图
• 2.3.2 查找k-clique
• 2.4 关键算法实现技术
• 2.4.1 顶点数据结构
• 2.4.2 k分图存储
• 2.4.3 随机读写k分图
• 2.4.4 整合k分图
• 2.5 实验结果及分析
• 2.5.1 判断两个顶点间是否有边
• 2.5.2 寻找k-clique
• 2.6 小结
• 第三章 CLOSEST STRING问题求解
• 3.1 已有算法
• 3.1.1 固定参数算法
• 3.1.2 整数规划算法
• 3.2 下界推导及计算最优上界
• 3.2.1 d的下界推导
• 3.2.2 计算最优上界
• 3.3 下界相关算法
• 3.3.1 下界相关算法设计
• 3.3.2 下界算法相关优化
• 3.4 应用下界相关算法求所有解
• 3.5 关键算法实现技术
• 3.5.1 循环产生组合
• 3.5.2 下界相关算法优化
• 3.6 实验结果对比与分析
• 3.6.1 计算最优上界
• 3.6.2 与固定参数算法比较
• 3.6.3 求解所有解
• 3.7 小结
• 第四章 分布式计算系统设计
• 4.1 系统设计
• 4.1.1 系统设计方案
• 4.1.2 系统模块与流程
• 4.2 系统关键技术
• 4.2.1 分布式算法与分布式系统的信息交流
• 4.2.2 容错机制
• 4.2.3 分布式系统的配置
• 4.3 小结
• 第五章 总结与展望
• 5.1 工作总结
• 5.2 将来进一步的研究工作
• 参考文献
• 致谢
• 攻读硕士期间主要的研究成果