计算生物学中基因组重组排序问题的算法研究

论文摘要

计算生物学是现今世界的热门学科，计算生物学研究的有关成果直接影响着人类在生物进化、基因制药等领域的研究进展。生物学、化学、数学、计算机科学等各领域专家学者都在关注着计算生物学的发展。 20世纪80年代末，Jeffrey Palmer及其同事在对比甘蓝与芜菁甘蓝的基因序列时发现，排列形成两种基因序列的分子几乎完全相同，只是这些分子在两种基因中的排列顺序不一样。这一发现以及其后的研究表明，基因重组是生物演化过程中的一个基本特征，是微生物、植物、动物进化的一种重要模式。自此以后，与基因重组有关的技术与理论研究成为计算生物学研究中的一个热点，其在生物种族进化研究、生物分类学研究、生物制药研究等研究领域中显示出重要的研究价值。 一条染色体由一个基因序列组成，一个基因组是染色体的集合。显然，染色体可以看作是由单条染色体构成的基因组。基因序列可以呈线状（linear）或环状（circular）分布。若基因序列中每个基因的方向是已知的，则称此序列是带符号的（signed），否则称为无符号的（unsigned）。同理可定义带符号的基因组和无符号的基因组。虽然基因组的重组过程十分复杂，但是只存在几种基本的操作。在变异的过程中，这几种变换为：反转（reversal），移位（translocation）和对换（transposition）。生物物种之间的进化实际上就是生物基因的变异过程。生物之间的进化关系可以通过基因组之间的变换来描述。给定两个基因组Π和Γ，在规定了可以使用的变换的集合之后，寻找从Π到Γ的最短的变换序列的问题称为基因组重组排序问题。一般情况下，基因组重组排序问题可以进行以下的简化：即假设基因组中不存在重复的基因。在这一简化下，对于一个含有n个基因的基因组，我们通常用一个定义在{1，2…，n}上的排列（n-排列）来表示。若此基因组含有多个染色体，这个n-排列将被分成多个连续的“块”，其中每个块表示一个染色体。 基因组的重组排序问题在近几年得到了广泛的研究，已有大量的结果。对应的三种不同的操作的排序问题难度有所不同。反转操作是将一个基因序列的一个子序

论文目录

• Chinese abstract
• English abstract
• Notation index
• Chapter 1. Introduction
• 1.1 Motivation: background of the research of genome rearrangement
• 1.2 Some key concepts of algorithms
• 1.3 Mathematical dcnotations
• 1.4 Combinatoric problems in genome rearrangements
• 1.4.1 Sorting by reversals
• 1.4.2 Sorting by transpositions
• 1.4.3 Sorting by reciprocal translocations
• 1.4.4 Sorting by bounded operations
• 1.4.5 Sorting by weighted operations
• 1.4.6 Sorting by mixed operations
• 1.5 Thesis outline
• Chapter 2. Sorting signed permutation by fixed-length reversals
• 2.1 Introduction
• 2.2 Preliminaries
• 2.3 Equivalent Transformations
• 2.4 Equivalence Classes under Fixed-length Signed Reversals
• 2.4.1 For special k=1, n-1 and n
• 2.4.2 Equivalence Classes in SLPG（k, n）
• 2.4.3 Equivalence Classes in SCPG（k, n）
• 2.5 Conclusion
• Chapter 3. Sorting by length weighted transpositions
• 3.1 Introduction
• 3.2 Preliminaries
• 3.3 Upper bounds on the minimum cost sufficient to sort any sequence
• 3.4 Lower bounds on the minimum cost sufficient to sort any sequence
• 3.5 Algorithms
• 3.5.1 Approximation algorithm when 0≤α＜1
• 3.5.2 Approximation algorithms when α=1
• 3.5.3 Approximation algorithms when 1＜α＜2
• 3.5.4 Efficient algorithm when α≥2
• 3.6 Conclusions and Open problems
• Chapter 4. Sorting signed genomes by translocations and deletions/insertions
• 4.1 Introduction
• 4.2 Preliminaries
• 4.2.1 The cycle graph
• 4.2.2 The sub-permutation
• 4.2.3 The forest of SPs
• 4.2.4 Effects of a translocation on SPs
• 4.2.5 The translocation distance
• 4.3 On sorting by translocations and deletions
• 4.3.1 New definition for the cycle graph
• 4.3.2 New definition for the translocation
• td （Π,Γ）'>4.4 A lower bound on d_td（Π,Γ）
• 4.5 An approximation algorithm for sorting by translocations and deletions
• 4.5.1 Failed cases and corresponding sub-procedures
• 4.5.2 Main lemmas
• 4.5.3 The approximation algorithm
• 4.6 Analysis of the algorithm
• 4.7 Conclusions and open problem
• Bibliography
• Acknowledgements
• Curriculum Vitae
• 学位论文评阅及答辩情况表