基因组Reversal/Transposition排序的快速计算研究

摘要

基因组重组是基因组改变基因排列顺序的生化过程。基因组重组排序问题来源于基因组中基因排列顺序的比较。其目标是找到最短的重组操作序列，将一个基因组转变为另一个基因组。基因组重组排序用于推断生命因重组而演化的过程，基因组重组排序计算有助于确切分析疾病的致病原理，有助于快速诊断疾病以有效治疗疾病，有助于精确设计医药的分子结构，提高药物疗效。 一条染色体由一个基因序列组成，基因组是染色体的集合。可以将一次基因组重组看做改变基因排列顺序的一次操作。假设自然界总是选择最省力的方式或以最快方式完成生命演化的，因此人们以重组操作次数最少为目标，来计算一个基因组转化为另一个基因组的重组操作序列作为基因组间的重组演化过程。Sankoff等人最早设计了基因组的翻转（Reversal）和移位（Translocation）排序算法。 给定两个基因组A，B，在规定了可以使用的操作之后，A，B之间的距离为从A转换到B的最少变换操作次数。将求这些基因组之间的变换距离及变换序列的问题称为基因组重组排序问题。最基本的重组操作有三种：翻转（reversal），移位（translocation）和转位（transposition）。为了简单，在讨论基因组重排距离时，人们往往只考虑一种或两种操作。本文研究使用翻转和转位操作对有符号基因组进行排序的问题。其中每个基因组均为一个有符号整数序列，一个整数符号表示一个基因。 基因组翻转/转位排序要求寻找一个翻转或转位操作序列，将一个给定的有符号整数排列转化为另一个有符号整数排列。Gu Q P给出该问题的一个近似性能比为2的多项式时间近似算法，但未见该算法的实现程序和算法计算性能的实际测试结果。 本文主要讨论基因组翻转/转位排序算法的实现方法。首先介绍近似性能比为2的算法思想，然后讨论该算法的C程序实现方法，并以实际数据测试程序的求解性能。在算法的实现中，采用一维数组和链表存储整数排列，从而使子序列的翻转和转位操作可在常数时间内完成。在第四章中，根据少量数据手工测试和大量数据实际执行的结果，找到近似性能比最坏的例子是所有的元素全部包括在一个圈链表中且每次操作只能减少一条黑边，特殊情况下可以求得最优解。 本文的如下工作有所创新： （1）首次设计实现了近似性能比为2的有向基因组翻转/转位排序算法，验证了算法的求解性能和最低界限： （2）利用算法找到一个实例，算法求解该实例的近似性能比为2； （3）采用一维数组和链表存储整数排列，提高了程序的运行速度。

目录

文摘

英文文摘

声明

第一章 绪论

1.1背景与意义

1.2研究思路和方法

1.3相关知识

1.3.1翻转(reversal)

1.3.2移位(transposition)

1.3.3转位(reversal+transposition)

1.3.4最短距离d(π)

1.3.5断点图G(π)

1.3.6段、圈、交替

1.4本文的工作与组织

第二章 基因组排序的快速计算方法

2.1排序算法设计原理

2.1.1预备工作

2.1.2过程与证明

2.2算法思想

2.3算法的设计

2.3.1数据结构

2.3.2重要子程序

第三章 算法的最低界限和近似性能比

3.1最低界限的证明

3.2算法的最低界限

3.3算法的近似性能比

第四章 快速排序算法的实现与改进

4.1概述

4.2原算法实现与改进

4.2.1原算法使用R/T操作的实现

4.2.2实现过程中的改进

4.2.3改进算法的实现

4.3实例流程分析

4.3.1近似性能比最差实例

4.3.2单圈近似性能比实例

4.3.3多圈近似性能比

4.3.4近似性能比最佳实例

4.4运行比较与分析

第五章 结论与展望

5.1本文结论

5.2本文的不足与展望

参考文献

致谢