学位论文 > 优秀研究生学位论文题录展示

计算生物学中有关基因组移位—删除排序问题的研究

作　者: 郝勇
导　师: 栾峻峰
学　校: 山东大学
专　业: 计算机软件与理论
关键词: 基因组时间复杂度移位删除
分类号: Q75
类　型: 硕士论文
年　份: 2011年
下　载: 14次
引　用: 0次
阅　读: 论文下载

内容摘要

计算生物学是当今世界发展最为迅速、最热门的学科之一,计算生物学研究的成果影响着人类在生物进化、基因制药、基因治疗等领域的研究进展。生物学、化学、数学、计算机科学等各领域的专家学者都在参与着计算生物学的研究,并取得了一系列的进展和突破。随着大尺度DNA绘图的出现,基因组排序问题在分子生物学和计算生物学中的地位越来越重要。生物学家通过对整个基因组测序或使用比较物理图谱得到基因次序,并用排列来表示基因组以便于分析不同物种的基因列。推导物种的进化史,一个比较有前途的方法是比较两个基因组中的基因排列顺序。20世纪80年代末,Jeffrey Palmer和同事在对比甘蓝与芜菁甘蓝的基因序列时发现,排列形成两种基因序列的分子几乎完全相同,只是分子在两种基因中的排列顺序不一致。这一发现和以后的一系列研究表明,两个相近的物种往往含有相同的基因集合,只是基因排列的顺序有所不同。在生物进化的过程中,最常见到的基因重排事件是翻转(Reversal),它指在一个染色体中发生的基因重排事件,和移位(Translocation),它指在不同的染色体间发生的基因重排事件。本文就基因组移位-删除排序问题进行了研究,得到了一下两个主要结果：(1)基于时间复杂度为O(n3)的基因组移位-删除算法进行了改进,通过改进其在不同情况下的树结构处理方式和采用的合并、分解操作以及采用时间复杂度更低的移位排序子程序,将该算法的时间复杂度将为O(n2)。(2)受到基因组移位排序算法的启发,我们不在一开始便讨论基因组移位-删除排序中所遇到的各种情况,而是在执行完所有可行性移位之后,对剩余的最小子排列进行归类分析。这样,既可以使讨论的情况更加简单,更具有代表性,又可以给出一个通用的、处理各种复杂情况的处理办法。最终设计出了一种移位-删除排序问题的快速处理算法。

全文目录

摘要  8-10
Abstract  10-12
第一章绪论  12-17
  1.1 本文的研究背景  12-13
  1.2 基因、染色体以及基因组的数学表示  13-14
  1.3 基因组移位排序问题及移位-删除排序问题  14-15
  1.4 本文的主要结果及创新点  15
  1.5 内容安排  15-17
第二章理论基础  17-30
  2.1 基因组排序的基本概念  17-21
  2.2 Bergeron的经典移位排序算法  21-22
  2.3 基因组移位排序问题O(n~2)的快速算法  22-30
    2.3.1 最小子排列搜索算法  23-24
    2.3.2 最右灰边  24-25
    2.3.3 基于最右灰边的剩余子排列分段  25-27
    2.3.4 搜索有效合理移位的顶点删除算法  27-28
    2.3.5 搜索有效合理移位算法  28-29
    2.3.6 快速移位排序算法  29-30
第三章基因组移位-删除问题  30-35
  3.1 基因组移位-删除问题介绍  30
  3.2 基因组移位-删除问题的形式化定义及基本移位规则  30-32
  3.3 基因组移位-删除排序的时间复杂度为O(n~3)的算法  32-35
第四章基于O(n~2)快速移位排序的有向基因组移位-删除排序改进算法  35-41
  4.1 原有基因组移位-删除排序算法中可以优化的点  35
  4.2 针对不同情况的基因组移位-删除问题的处理子程序  35-38
  4.3 时间复杂度的证明  38-41
第五章基因组移位-删除排序问题O(n~2)时间复杂度的快速算法  41-46
  5.1 基因组移位-删除排序问题一种新的解决思路  41-42
  5.2 基因组移位-删除排序中处理剩余最小子排列的方法  42-44
  5.3 关于时间复杂度的证明  44-46
结论  46-47
参考文献  47-49
致谢  49-50
学位论文评阅及答辩情况表  50

计算生物学中有关基因组移位—删除排序问题的研究

内容摘要

全文目录

相似论文