基于种子的序列比对方法研究

论文摘要

生物信息学是由生物学、数学、计算机科学相互交叉、渗透所形成的学科,是生物技术的核心。序列比较是生物信息学中最基本、最重要的操作,通过序列比较可以发现生物序列中的功能、结构和进化的信息,而序列比较的基本操作是比对。其中多序列比对问题是生物信息学中的主要研究方向之一,是一个NP完全问题,它的求解至今仍是生物信息学中的一个难题。为了加速同源性搜寻,已经提出并开发了许多方案,BLAST是一种最广泛使用的一种局部定位搜索工具,而Pattern Hunter算法与它不同在于发现“有间隙”的种子,替代了被那些短而“精确”的种子。本文在研究原有的Pattern Hunter算法的基础之上,深入了解和掌握了两种改进方法(SRT方法和块矩阵方法)的思想和理论,它们通常能够以较少的运行时间计算“有间隙”的种子在一个随机区域上的灵敏度。并且实现了基于动态规划思想的SRT方法。同时,运用改进的Pattern Hunter算法实现了基于Monte Carlo的最优种子寻找方法,通过算法中参数的调节,能高效地找到最佳种子(或次优种子)。

论文目录

• 内容提要
• 第1章 绪论
• 1.1 论文的选题背景和意义
• 1.1.1 选题背景
• 1.1.2 选题意义
• 1.2 序列比对研究现状
• 1.3 论文的组织
• 第2章 序列比对的基础知识
• 2.1 序列比对的基本概念
• 2.2 PATTERN HUTER算法介绍
• 2.2.1 相关概念
• 2.2.2 Pattern Hunter算法
• 第3章 计算种子敏感度的方法研究
• 3.1 基于SRT的方法研究与实现
• 3.1.1 SRT算法的基本思想
• 3.1.2 SRT算法用到的数据结构
• 3.1.3 SRT算法的关键函数的设计
• 3.1.4 SRT的算法分析
• 3.1.5 算法的实验结果
• 3.2 基于BLOCK-MATRIX算法的方法研究
• 3.2.1 Block-matrix的基本思想
• 3.2.2 算法的流程
• 第4章 基于MONTE CARLO方法的种子寻找方法
• 4.1 MONTE CARLO算法的基本流程和分析
• 4.2 MONTE CARLO算法的实现
• 4.3 MONTE CARLO算法的实验结果与分析
• 第5章 总结与展望
• 参考文献
• 摘要
• ABSTRACT
• 致谢