有向基因组复合操作重组排序算法研究

论文摘要

比较基因组学是生物信息学的一个重要研究分支,计算两个基因组的量化距离是比较基因组学的基本问题,应用于构建进化树、探索基因功能、分析疾病致病原理等实践中。基因组是一个染色体集合,染色体为一个基因序列,每个基因表示为一个整数。基因组分有向和无向两种数据形式,每个基因相对所在染色体中的相邻基因,均有两个方向,在有向基因组中,采用“+”和“-”分别表示-个基因的两个方向。基因组的重组揭示了基因组改变基因排列次序的行为,在基因组重组排序问题中表述为改变基因排列次序的操作,有翻转（Reversal）、移位（Translocation）、转位（Transposition）等基本形式。给定两个基因组A、B,基因组重组排序要求寻找将A转化为B的一组有序操作,最小化操作次数,将A转化为B的最小重组次数即为A与B的重组距离。沿着由简而繁的路线,人们讨论了多种形式的基因组重组排序问题,和它们的算法与复杂性。Bafna和Pevzner首先给出有向基因组翻转排序近似度为1.5的多项式算法,Hannenhalli和Pevzner设计出O（n5）时间精确算法,Kaplan、Shamir和Tarjan将算法时间复杂度改进为O（n2）。对于基因组的移位排序问题,Hannenhalli首次设计出O（n3）时间精确算法,朱大铭和马绍汉将该算法的时间复杂度改进为O（n2logn）,王鲁生、朱大铭、刘晓文和马绍汉进一步将算法的时间复杂度改进为O（n2）,李国君、亓兴勤、王骁力和朱滨海给出了计算移位距离的O（n）时间算法。对于基因组转位排序问题,Bafana与Pevzner最早给出近似度为1.5的O（n2）时间算法。Hartman和Shamir又给出近似度为1.5的更为简洁的近似算法。Elias和Hartman将近似度改进为1.375。最近Bulteau、Fertin和Rusu证明该问题是NP-hard问题。我们将包含多种操作形式的基因组重组排序称为基因组的复合重组排序问题。因复合重组排序更具一般性,所以显得更有应用价值。Walter、Dias和Meidanis给出基因组的翻转和转位排序近似度为2的近似算法。Gu、Peng和Sudborough给出了基因组的翻转、转位和反转位排序问题近似度为2的近似算法。Hartman和Sharan给出基因组的翻转和反转位排序问题近似度为1.5的近似算法。Hannenhalli和Pevzner设计出基因组的翻转和移位排序问题的多项式时间精确算法。尹晓和朱大铭给出这一问题的一个新多项式算法。尹晓和朱大铭于2010年设计出基因组的移位、分断和连接排序的精确算法,时间复杂性为O（n（?））。人们还发现在基因组的重组演化中,伴有插入与删除基因片段的动作,许多分子生物学实践需要人们在基因组中实施插入与删除基因片段的操作。亓兴勤、李国君、李曙光等首次讨论了有向基因组的移位和删除排序问题,他们给出了有向基因组移位和删除排序的多项式算法,近似度达到OPT+2, OPT为两个基因组的移位删除距离。另外,亓兴勤、李国君、李曙光等描述了基因组的移位、插入和删除排序问题,并给出了解决该问题的一个启发式算法。我们仍然讨论有向基因组的移位、插入与删除排序算法。问题的输入数据为两个有向基因组A和B,移位删除排序要求寻找将A转化为B的移位、删除操作序列,使移位、删除次数最小化；移位插入删除排序问题要求寻找将A转化为B的移位、插入、删除操作序列,使移位、插入、删除次数最小化。首先讨论有向基因组移位和删除排序问题的求解算法。仍然利用圈图表达两个基因组的基因排列次序差异。圈图中含有一种被称为极小子排列的特殊结构子图,其数目和相对位置是影响有向基因组移位删除距离的关键因素。可将圈图中的极小子排列和它们相邻关系表示为一个森林。我们进一步根据圈图中描述极小子排列的森林的不同结构特征,分34种情况分别给出了有向基因组移位删除距离的精确数值。亓兴勤等给出的移位删除距离含有基因数目、染色体条数、圈的数目、偶隔离带存在性和极小子排列奇偶性辅助参数、间接圈数目、间接极小子排列数目,共6个参数。我们重新观察了圈图结构性质,引入两个新的特征参数：不可消除间接极小子排列数和打破间接极小子排列的间接普通圈数后,把所有情况下最小的移位删除次数统一为移位删除距离计算公式。推导移位删除距离公式的过程,自然地给出基因组的移位删除精确算法。（第3章）有向基因组移位插入删除排序求解,可先利用移位删除算法构造一个中间基因组,然后将源基因组由插入操作得到中间基因组,再调用移位删除算法将中间基因组变换为目标基因组而完成。由有向基因组的移位删除距离公式,我们给出了有向基因组移位插入删除距离的计算公式。（第4章）继续讨论了包含副本染色体和副本基因的有向基因组翻转,移位,转位,块交换,分断,连接排序的求解方法。划分为删除副本、同尾化基因组、规范化基因组重组排序三个功能模块,得到基因组复合重组排序的一个实用计算软件。最后给出初步的实验结果。（第5章）本文创新点可以归纳如下：1).首次给出了基因组的移位和删除距离公式,并给出求解该距离值及对应重组序列的一个多项式时间精确算法。2).将有向基因组移位和删除排序的时间复杂度由O（n3）时间改进到O（n2）时间。3).首次给出了基因组的移位、插入和删除距离公式,同时给出有向基因组移位插入删除排序的一个新多项式时间精确算法。

论文目录

• 摘要
• ABSTRACT
• 符号说明
• 第1章 绪论
• 1.1 有向基因组排序算法进展
• 1.2 本文的主要贡献
• 第2章 有向基因组排序问题介绍
• 2.1 基因组的表示方法
• 2.2 基因组排序问题模型
• 2.2.1 重组操作
• 2.2.2 对输入基因组的约束
• 2.3 问题定义及输出
• 2.4 研究工具——圈图
• 2.5 本文研究的具体问题
• 第3章 基因组的移位和删除排序问题
• 3.1 问题介绍
• 3.1.1 问题描述
• 3.1.2 预备知识
• 3.2 问题分析
• 3.3 有的算法
• 3.4 基因组的移位和删除排序精确算法
• 3.4.1 对所有情况的分析
• 3.4.2 基因组的移位和删除距离公式
• 3.4.3 算法性能分析
• 3.5 结论
• 第4章 基因组的移位和删除排序问题扩展
• 4.1 基因组的移位和删除排序问题的较快算法
• 4.1.1 基因组的移位和删除排序问题的较快算法
• 4.1.2 较快算法分析
• 4.2 相关操作的可逆性
• 4.3 基因组的移位和插入排序问题
• 4.3.1 问题描述
• 4.3.2 归约为"基因组的移位和删除排序问题"
• 4.4 基因组的移位、插入和删除排序问题
• 4.4.1 问题描述
• 4.4.2 算法及分析
• 4.5 结论
• 第5章 一般基因组的复合操作排序问题
• 5.1 问题描述
• 5.2 启发式方案的架构设计
• 5.2.1 解决该问题的三个功能模块
• 5.2.2 解决方案的实现组件
• 5.3 去除多倍染色体和副本基因
• 5.3.1 染色体丢失组件
• 5.3.2 副本基因标识组件
• 5.3.3 反任意片段复制组件
• 5.4 同尾化基因组
• 5.4.1 加帽基因组
• 5.4.2 各种操作在加帽前后的对应关系
• 5.4.3 同尾化基因组的实现组件
• 5.5 规范基因组的排序
• 5.6 结果与分析
• 第6章 总结与展望
• 6.1 本文总结
• 6.2 研究展望
• 参考文献
• 致谢
• 攻读学位期间发表的学术论文目录
• 在读期间参与科研项目情况
• 学位论文评阅及答辩情况表
• 外文论文