零抽样断点距离的一个改进算法

摘要

基因组学出现于1980年，随着几个物种基因组计划的启动，基因组学得到了很好的发展。近年来，随着各种新技术的出现，基因组学更是进一步的发展。海量的基因组数据从这些新技术中不断的出现，面对爆炸性增长的数据，我们急需要一种新方法来对这些数据进行处理，比较基因组学应运而生。
　　比较基因组学中最重要的问题之一就是抽样断点距离问题。该问题在文献中已经被广泛的研究。抽样断点距离问题描述为:对于两个输入基因组，找到它们各自的抽样序列，使这两个抽样的断点距离最小。抽样断点距离问题的特殊版本为:两个输入基因组中每一个基因家族至多出现两次，并且判定它们是否存在断点距离是零的抽样序列，即是否能归约成相同的基因组。我们把这样的问题称为零抽样断点距离问题，简称为ZEBD(2，2)问题。 Blin等人已经证明零抽样断点距离问题是NP-Hard的，并且不存在任何参数化的算法，即使每一个基因家族在一个基因组中至多出现两次。
　　目前存在的判定ZEBD(2，2)问题的算法中，时间复杂度最好为O(n21.86121n)。在本文中，我们改进了该算法，将时间复杂度提高到了O(n21.84931n)。如果抽样图中每一个基因家族构成的子图至多有两条边，可以在多项式时间内判定出这两个基因组是否存在断点距离为零的抽样。我们算法首先就是把两个输入基因组构成的抽样图经过处理，使其满足每一个基因家族构成的子图至多有两条边。我们通过穷举达到这样的目的。我们算法就是通过减少穷举的次数，提高了时间复杂度。具体方法为:我们同时分析两个基因家族构成的复杂分支对，将它们分解成每一个基因家族只含两条边的子图，分支对至多能分解出三个这样的子图;然后，将满足一定条件的分支对，再添加一个基因家族构成分支Triple，并对这个分支Triple进行分解，分支Triple最多能分解出五个子图。经过这样的处理，使得分支对的分解个数由原来的4个减少到3个，分支Triple的分解个数由原来的8个减少到5个。因此降低了算法的时间复杂度。

目录

声明

摘要

第一章 绪论

1．1 算法及其复杂性

1．2 研究背景

1．3 本文研究内容

1．4 本文组织结构

第二章 相关研究

2．1 ZEBD(2，2)是NP-Complete的

2．2 EBD(2，2)不存在近似算法和参数算法

2．2．1 抽样断点距离不存在近似算法

2．2．2 抽样断点距离不存在参数算法

2．3 本章小节

第三章 时间复杂度是O(n21．84931n)的精确算法

3．1 概述

3．2 两个基因组的抽样图

3．3 找到简单抽样图中的抽样集合

3．4 时间复杂度是O(n21．84931n)的算法

3．4．1 分解复杂分支对

3．4．2 分解复杂分支Triple

3．4．3 抽样图的分解

3．4．4 时间复杂度是O(n21．84931n)的算法

3．5 本章小节

第四章 总结和展望

4．1 本文总结

4．2 研究展望

参考文献

致谢