无符号基因组切割再粘贴重组问题的算法研究

摘要

基因组是一组染色体的集合,染色体记录了物种的遗传信息,一条染色体由一系列基因构成,不同的基因决定着物种不同的性状。随着越来越多的基因组被测序,使得全基因组之间的比对成为可能。不同的物种从其共同的祖先那里继承了相似的基因,一些看似远亲的物种之间也发现了大规模的基因重组。人们普遍认为,将一个基因组转变为另一个基因组所需的基因组重组次数可以用来衡量两个物种之间的进化距离。基因组重组是生物进化的一种普遍模式,也是植物、哺乳动物及细菌等呈现多样性的主要因为之一。
　　 作为研究基因次序和基因家族进化的重要工具,若干基于基因组重组的数学模型被提出来,其中最常用的方法就是在最节俭的原则假设下推断重组操作序列:给定两个具有相同基因集合的基因组,计算将一个基因组转变为另一个基因组所需最少的重组操作序列。该序列的长度被称为这两个基因组之间的距离。常见的重组操作有:反转(reversal),转位(transposition)和带有反转的转位(transreversal)等。这些操作是进化过程中单染色体上经常发生的,它们有一个共同的特点,即先从染色体上断下一段,反转或不反转,然后再接入原来的染色体中。如果反转后接入的位置与断下的位置相同,则是一个反转操作:如果反转后接入的位置与断下的位置不同,则是一个带有反转的转位操作；如果不反转但是接入的位置与断下的位置不同,则是一个转位操作。鉴于此,人们提出一种一般性的操作--切割再粘贴操作来描述这些重组操作。一个切割再粘贴操作可以是一个反转操作,也可以是一个转位操作,还可以是一个带有反转的转位操作。将生物体的一条染色体或一个基因组表示为基因的一个排列,基因组重组问题就可以看做是用切割再粘贴操作对排列排序的问题:给定两个排列A和B,寻找将A变为B所需最短的切割再粘贴操作序列,这个过程中最短的操作个数称为A和B之间的距离。
　　 生物学家通过对整个基因组测序或使用比较物理图谱得到基因次序。测序提供有关基因方向的信息并且允许用有符号排列来表示基因组。但是,对整个基因组进行测序的花费较为昂贵,仍有许多有关基因次序的试验数据是基于比较物理图谱的。物理图谱常常不提供有关基因方向的信息,因而也用无符号排列来表示基因组。这就衍生出了两类组合问题:用最少的重组操作对有符号排列或无符号排列进行排序。
　　 近年来,基因组重组排序问题吸引了许多计算机科学家和生物学家的研究兴趣,出现了大量研究成果。对于反转操作,Hannenhalli和Pevzner利用断点图解决了有符号基因组的反转排序问题,他们设计了一个时间复杂度为O(n4)的多项式时间精确算法,而断点图也成为解决这一类问题的主要研究工具。目前反转距离已经能在线性时间计算出来。相比之下,无符号基因组反转排序问题则并不容易解决,该问题被证明是NP-hard问题,目前最好的近似度为1.375。
　　 对于转位操作,由于其不改变基因的方向,因而只讨论无符号基因组,目前已有若干近似度均为1.5的近似算法,该问题的复杂度仍然未知。目前最好的近似度为1.375。
　　 上面提到的都是单一的重组操作,实际的生物进化可能涉及多种重组操作,目前的研究中对有符号基因组的讨论较为充分。Gu等人给出了用转位和带有反转的转位排序的2-近似度算法。Lin和Xue给出了用反转、转位、带有反转的转位和双反转四种操作排序的1.75近似度算法。Harman和Sharan设计了一个用转位和带有反转的转位排序的1.5近似度算法。Eriksen为反转赋权值1,为转位和带有反转的转位赋权值2,设计了一个该权值下的1+ε似度算法。但是对于无符号基因组排序问题,目前仅有一个3近似度算法和改进后的2.8386+δ近似度算法,这两个算法允许的操作都是反转和转位。
　　 Cranston等人首先研究了对无符号排列用切割再粘贴操作排序的上下界。他们证明:每个无符号线排列都可以用至多[2n/3]次切割再粘贴操作排好序。该结论可以扩展到圆排列上,但是他们的算法并没有任何的近似度保证。
　　 本文主要研究无符号基因组,主要贡献如下:
　　 (1)对于无符号基因组切割再粘贴排序问题,本文设计了针对圆排列的近似度为2.25的多项式时间近似算法。这是该问题目前能得到的具有最小近似度的算法。算法在断点图中识别出一种叫做结(tie)的结构来表示长度为5的交错路。该结构可以划分为6类,针对每一类都详细给出清除其断点的方法,使得每个切割再粘贴操作都能平均至少清除4/3个断点。由于上下界中仅涉及断点数这一个变量,避免了传统方法对无符号排列中圈分解个数的讨论,获得了较好的近似度。如果还允许另一种操作--双反转,算法同样可以用来对无符号线排列排序,并且获得相同的近似度。
　　 (2)本文修正了单元素受限的无符号排列反转排序问题的多项式时间算法。通过仔细分析反转一个规范2-带对圈数的影响,将原算法中要取反的2-带限制为一个子集；在此基础上更新了最优旋转的定义,解决了原有算法中失败的情况。
　　 (3)本文研究了用赋权的切割再粘贴操作对无符号排列排序问题,其中反转与转位/带有反转的转位赋权比为1:2。利用有符号排列的赋权距离公式,发现对于无单元素排列,反转排序问题的最优旋转同样是赋权排序问题的最优旋转,因而对单元素受限的无符号排列得到了与有符号排列相同的近似度。
　　 本文结构如下:
　　 第一章介绍若干基因组重组排序问题,包括各类问题及其子问题的基本定义、表示方法、重要结论和研究现状。
　　 第二章研究了对无符号圆排列用切割再粘贴操作重组排序问题。首先在断点图中识别出两种结构:“结”和“折”,通过研究结和折的交叉关系和具体分类,设计了近似度为2.25的多项式时间算法。本章最后给出了在增加双反转的情况下如何利用该算法对线排列排序并且获得相同的近似度。
　　 第三章修正了Hannenhalli和Pevzner对单元素受限的无符号排列反转排序问题的多项式时间算法,指出其中一种失败的情况并给出新的算法和证明。
　　 在第三章的基础上,第四章研究了无符号排列赋权排序问题,其中反转与转位/带有反转的转位赋权比为1:2。利用Eriksen关于有符号排列赋权排序问题的1+ε近似度算法和赋权距离公式,设计了针对单元素受限的无符号排列赋权排序问题的1+ε近似度算法。

目录

文摘

英文文摘

TABLE OF CONTENTS

符号说明

第1章 基因组重组排序问题的基本定义和研究现状

1.1 重组操作与排序距离

1.2 用反转进行排序

1.2.1 用反转对无符号排列进行排序

1.2.2 用反转对有符号排列进行排序

1.2.3 用固定长度的反转进行排序

1.2.4 用前缀反转进行排序

1.3 用转位进行排序

1.3.1 用普通转位进行排序

1.3.2 用受限制的转位进行排序

1.3.3 转位直径问题

1.3.4 用前缀转位进行排序

1.4 用块交换进行排序

1.5 用移位、分断、连接操作进行排序

1.5.1 用移位对有符号排列进行排序

1.5.2 用移位对无符号排列进行排序

1.6 用切割再粘贴操作进行排序

第2章 无符号圆排列切割再粘贴排序问题的2.25近似度算法

2.1 引言

2.2 基本定义

2.2.1 切割再粘贴操作

2.2.2 无符号圆排列的断点图

2.3 针对无符号圆排列的2.25近似度算法

2.3.1 结和折

2.3.2 单元素分裂

2.3.3 对无单元素的坏排列排序

2.3.4 算法描述和分析

2.4 对线排列排序

2.5 本章小结

第3章 单元素受限的无符号排列反转排序问题的修正算法

3.1 引言

3.2 基本定义

3.3 HP算法失败的情况

3.4 无单元素排列的超r-旋转的最优性证明

3.5 单元素数在O(logn)以内的无符号排列反转排序问题的修正算法

3.6 本章小结

第4章 单元素受限的无符号排列赋权排序问题的1+ε似度算法

4.1 引言

4.2 基本定义

4.3 无符号排列赋权排序问题的近似算法

4.3.1 为长带和2-带赋正负号

4.3.2 无单元素排列的赋权排序算法

4.3.3 单元素数在O(logn)以内的无符号排列赋权排序算法

4.4 本章小结

结束语

参考文献

致谢

攻读博士学位期间发表的学术论文目录

在读期间参与科研项目情况

学位论文评阅及答辩情况表

附:外文论文