基因组比较算法研究

论文摘要

计算基因组学是一门处理基因组数据并从中获取生物信息的学科。其典型问题是计算基因组间的重组距离、依据同源基因重构祖先基因组序列以及处理生物测序技术所得基因组序列中冗余的和丢失的生物信息。但是,计算基因组学中的绝大部分问题都是NP-难的,越来越多的计算生物学研究者致力于设计多项式时间近似算法。同时,鉴于此类问题的生物应用,近似算法在实际生物数据处理时有可能计算出不精确的信息,因此应用参数化算法求解计算基因组学中的问题更加实用。计算基因组间的重组距离是计算生物学中的基本问题之一。基因组重组是非常复杂的过程,传统的重组操作包括翻转、转位、移位、合并、分裂和块交换。随着单一操作重组距离计算问题算法研究的进展,综合多种操作的重组距离更能全面反映多染色体基因组演化的过程,因此基于二次切割与连接（double cut and join,简记为DCJ）的基因组重组距离成为当前研究的热点。依据现存物种的同源基因,构建祖先基因组序列是计算基因组学的经典问题之一。随着越来越多的基因组序列的测定,生物信息学方法在祖先基因组重构过程中发挥着举足轻重的作用。目前最广泛应用方法是从已有物种的相关信息推测祖先基因组的连续遗传区（CARs）。可能的CARs都被存储在对应的PQ-树中。因此比较PQ-树之间的相似性及PQ-树与排列的距离成为预测祖先基因组（或者CARs）的关键。处理冗余和丢失的遗传信息也是计算生物学研究的重要组成部分。最常见的是在祖先基因组重构时,会发生个别基因在祖辈基因组中出现而在子辈基因组中消失的现象。剔出基因组图谱中的冗余数据和噪声数据是进行遗传信息分析的前提。在基因组组装不完全依赖全基因组测序的趋势下,将部分基因片段填充到不完整的基因组序列中以得到与原始基因组相近的替代基因组,从而可以完全摆脱全基因组测序的昂贵费用。本文对无符号多染色体线性基因组二次切割与连接距离问题、排列短块移动排序问题、字串最小公共划分问题、PQ-树断点距离问题、基因组最长带恢复问题及其补问题、基因组片段填充问题以及图的最大路径覆盖问题的复杂性和算法进行了研究,对于其中的NP-完全问题,设计了近似算法和参数化算法,P问题设计了多项式时间精确算法。本文的主要研究工作和创新点：一、算法设计理论方面1.首次提出亚核概念并应用于计算生物学问题的参数化算法设计。计算生物学中的绝大部分问题都是NPC的,这意味着设计多项式时间的精确算法几乎是不可能的（除非能证明P=NP）。同时,近似算法（即使是常数近似性能比的）对部分计算生物学问题没有实际意义。相反,参数化算法却能在可接受的时间内求得最优解。核心化是传统的参数化理论中对问题实例进行压缩的技术,而计算基因组学很多搜索问题实例是不能（或者很难）被压缩的。亚核是从搜索空间大小的角度对搜索问题进行压缩,即搜索空间的大小只与最优解的解值相关,而与问题的输入大小无关。本文中将亚核技术应于基因组二次切割并连接排序问题、基因组翻转排序问题、基因组最长带恢复问题以及图的最大路径集问题,并利用亚核心化技术设计了上述问题的参数化算法。二、基因组重组排序方面2.无符号多线性染色体基因组二次切割与连接排序问题。二次切割和连接操作（Double Cut and Join, DCJ）蕴含了所有传统的基因组重组操作,已经被广泛的应用于基因组重组距离的计算。虽然有符号基因组的DCJ距离是多项式时间可计算的,但是无符号基因组的DCJ排序问题已经被证明是NP-难的。本文借助多染色体（线型和圆型）基因组的排列图,应用图的最大匹配算法,在构造的排列图中搜索超过一半的2-圈,从而设计了无符号多线性染色体基因组DCJ排序问题的近似性能比为3/2的多项式时间算法。依据排列图中的所有1-圈都可以保存的性质,计算出大小为2K的亚核,进而设计了时间复杂性为O*（4k）的参数化算法。3.排列的短块移动排序问题。块移动是基因重组的一种重要形式。短块移动是将排列中的元素最多移动到偏离原来两个位置的块移动。本文讨论了具有伞形结构排列图的子排列的排序方法,设计了特殊子排列‘伞’短块移动排序的多项式时间精确算法。应用此算法,设计了一类特殊排列的短块移动排序的（1+ε）-近似算法。然后证明了排列短块移动距离的新下界,从而设计了近似性能比为14/11的短块移动排序新算法。4.字串的最小公共子串划分问题。字串的最小公共划分问题（Minimum Common String Partition, MCSP）是基因组重组的经典问题之一。其参数化复杂性至今未知。本文研究了MCSP的三个子问题：MCSP°要求构成字串的字母表的势最大为c;d-MCSP要求字串中每个字母重复次数最多为d;x-balance MCSP要求公共字串的长度与平均值之差最大为x。本文证明了当c≥2时,MCSP°是NP-难的；并分别设计了时间复杂性为O*（（d!）2k）和O‘（（2x）kk!）的参数化算法求解d-MCSP和x-balance MCSP。三、基因组数据处理方面5.基因组最长带恢复问题。给定两个基因组G1和G2（用两个长度为n的基因符号排列表示）,最长带恢复问题（Maximal Strip Recovery, MSR）就是保留最多的基因符号,使得被保留的基因组G*1和G*2可以被划分成相同的最长子串的集合,每个最长子串的长度至少为2。其补问题（CMSR）就是删除最少的基因符号以取得与MSR相同的效果。这两个问题都是NP-难的。本文证明了CMSR存在大小为18K的亚核,这是第一个非平凡的亚核的计算。另外,设计了CMSR问题的近似性能比为3的多项式时间近似算法和时间复杂度为0（3kn2）的参数化算法。6.基因片段填充问题。基因组片段填充问题是在非完整基因组组装的趋势下提出的。对照完整的基因组G,将基因组片段填充不完整基因组Ⅰ中得到基因组Ⅰ’,使得G和Ⅰ’的距离最小。本文研究了单面和双面、有重复和无重复基因组片段填充的断点距离、DCJ距离、最小公共划分及最大公共邻接问题。其中单面无重复基因组的断点距离和DCJ距离都是多项式时间可计算的；本文设计了双面无重复基因组的断点距离多项式时间算法：证明了计算单面有重复基因组的最小公共划分和最大公共邻接都是NP-难的；并设计了单面有重复基因组的最大公共邻接问题的4/3近似比算法。四、祖先基因组重构方面7.PQ-树断点距离和中心问题。PQ-树的断点距离问题就是给定两棵PQ树,分别寻找它们对应的一个排列,使得得到的两个排列的断点距离最小。PQ-树中心问题就是给定一棵PQ-树和一组排列,寻找该树蕴含的一个排列,使之与给定的排列的断点距离之和最小。本文证明了PQ-树的断点距离问题是NP-难的；说明了当给定排列不小于3个时,PQ-树中心问题是NP-难的,设计了PQ-树中心问题的时间复杂性为O*（3k）的参数化算法。如果能将PQ-树用图表示,则PQ-树中心问题非常类似于图的最大路径集覆盖问题。8.最大路径集覆盖的补问题。给定一个简单图G,删除最少的边,使得剩余的图中的每一个连通分支都是一条路径,即顶点度数不超过2并且没有圈。此问题包含汉密尔顿路径问题,从而是NP-难的。本文应用亚核技术,证明该问题存在大小为5K的亚核；并设计了时间复杂性位O*（6k/2）的参数化算法。本文的进一步工作主要包括：1.寻找亚核的更多的应用,特别是难以进行传统核心化的问题。2.重复度为2的基因组（Doubled Genomes）的DCJ距离计算问题。3.基因组最长带恢复问题的更小的亚核的计算。4证明单排列PQ-树中心问题的复杂性。5.最小公共划分问题的参数复杂性或设计参数化算法。6.最大路径集覆盖补问题更快的参数化算法及近似算法。

论文目录

• 摘要
• ABSTRACT
• 第1章 绪论
• 1.1 算法与计算复杂性
• 1.2 近似算法、近似性能比及不可近似性
• 1.2.1 L-归约与APX-hard
• 1.3 参数化算法与核心化
• 1.4 搜索问题与亚核
• 1.5 本文研究的问题及主要贡献
• 1.5.1 无符号多染色体线性基因组DCJ距离问题的亚核和近似算法
• 1.5.2 排列短块移动排序问题的近似算法
• 1.5.3 字串最小公共子串划分问题的复杂性和参数化算法
• 1.5.4 基因组最长带恢复问题及其补问题的亚核及算法
• 1.5.5 基因组片段填充问题的复杂性和近似算法
• 1.5.6 PQ-树断点距离相似性比较问题的复杂性和参数化算法
• 1.5.7 最大路径覆盖补问题的亚核和参数化算法
• 1.6 参考文献
• 第2章 基因组二次切割与连接排序问题的算法设计
• 2.1 引言
• 2.2 问题介绍
• 2.2.1 基因,染色体和基因组
• 2.2.2 断点图（Breakpoint Graph）
• 2.2.3 二次切割与连接操作（Double Cut and Join）
• 2.3 近似算法设计
• 2.3.1 无向基因组二次切割与连接排序的性质
• 2.3.2 算法形式化描述
• 2.4 核与参数化算法
• 2.5 结论
• 2.6 参考文献
• 第3章 基因组排列的短块移动排序问题
• 3.1 引言
• 3.2 短块移动问题简介
• 3.3 Heath的结论及算法
• 3.4 改进算法
• 3.4.1 伞排序
• 3.4.2 （1+ε）-近似算法
• 3.4.3 关联伞排序
• 3.4.4 短块移动排序近似算法
• 3.5 算法的近似性能比分析
• 3.5.1 特殊排列短块移动距离下界
• 3.5.2 算法近似性能比分析
• 3.6 结论
• 3.7 参考文献
• 第4章 最小公共划分问题
• 4.1 引言
• 4.1.1 问题介绍
• 4.1.2 相关工作
• 4.1.3 本文贡献
• c的复杂性'>4.2 MCSP^c的复杂性
• 4.3 d-MCSP的FPT算法
• 4.4 x-balance MCSP的FPT算法
• 4.5 总结
• 4.6 参考文献
• 第5章 基因组最长带恢复问题的亚核与算法
• 5.1 引言
• 5.2 问题介绍
• 5.2.1 参数化算法和亚核
• 5.3 线性亚核
• k参数化算法'>5.4 3^k参数化算法
• 5.5 3-近似算法
• 5.5.1 算法描述
• 5.5.2 近似性能比证明
• 5.6 结论
• 5.7 参考文献
• 第6章 基因组片段填充问题的算法与复杂性
• 6.1 引言
• 6.1.1 本文贡献
• 6.2 问题介绍
• 6.3 多项式时间算法
• 6.3.1 双面排列断点距离填充问题的多项式算法
• 6.3.2 双面排列断点二次切割与连接距离填充问题的多项式算法
• 6.4 复杂性证明
• 6.4.1 最小公共划分片段填充问题是NP-Complete的
• 6.4.2 最大公共邻接片段填充问题是NP-Complete的
• 6.5 最大公共邻接片段填充问题的近似算法
• 6.5.1 简单的2-近似算法
• 6.5.2 单面最大公共邻接片段填充问题的4/3-近似算法
• 6.6 结论
• 6.7 参考文献
• 第7章 PQ-树相似性比较问题复杂性与算法
• 7.1 动机
• 7.2 引言
• 7.2.1 排列、断点及中心
• 7.2.2 PQ-树
• 7.2.3 问题描述
• 7.2.4 有结果及本文贡献
• 7.3 PQ-树断点距离问题是NP-Complete的
• 7.4 单面MBP-PQ和p-MBM-PQ的参数化算法
• 7.4.1 PQ-树的图表示
• 7.4.2 单面MBP-PQ问题的FPT算法
• 7.4.3 参数化算法应用于p-MBM-PQ
• 7.5 结论
• 7.6 参考文献
• 第8章 最大路径集覆盖问题的亚核与参数化算法
• 8.1 引言
• 8.1.1 动机
• 8.1.2 研究状况
• 8.1.3 本文工作
• 8.2 问题介绍
• 8.3 5k亚核
• 8.4 改进参数化算法
• 8.5 结论
• 8.6 参考文献
• 第9章 总结与展望
• 9.1 本文总结
• 9.2 研究展望
• 致谢
• 攻读学位期间发表的学术论文
• 在读期间参与科研项目情况
• 学位论文评阅及答辩情况表
• 外文论文