论文部分内容阅读
早在上个世纪六十年代,Dobzhansky和Sturtevant发表了一篇重要的论文,其中证明了两个不同物种Drosophilia pseudoobscura和Miranda的染色体基因序列可以通过基因组的17次反转来进行相互转换。在之后的研究证明,基因组的重组是微生物,植物,动物进化的一种重要模式。对这种基因重组问题的研究形成了生物信息学,也称计算生物学中的一个分支——基因重组。 物种的遗传信息是由染色体记录的,一条染色体由一系列基因构成,不同的基因决定着物种不同的性状。一个基因组是由多条染色体构成。在上个世纪八十年代,人们发现不同物种有着基本上相同的基因,只不过这些基因的排列顺序有所不同。生物之间的亲缘和进化关系可以通过比较这些基因的排列顺序得到。生物的进化过程也就看作是一个基因的重组过程,虽然这个过程十分复杂,但是如果只考虑几种基本的操作,比如反转(reversal),移位(translocation),转位(transposition)和块交换(block-interchange)等,就可以简化问题。 基因重组的问题也可以看作是基因排序的问题,给定两个基因组A,B,在规定了可以使用的变换的集合之后,计算A,B之间的距离等价于寻找从A到B的最短变换序列。在过去十几年里,这个领域的问题得到了广泛的研究。其中很重要的一个研究方法就是断点图(break point graph),也称作圈图(cycle graph),的引入。利用这个研究方法,取得了很多理论结果和有用的算法。比如,人们证明无向的反转排序问题是NP—hard的,而有向的反转排序问题则有确定的多项式算法。 本文主要对转位排序问题和块交换排序问题进行研究。转位排序问题是相对比较难的问题,直到现在还不清楚其所属的复杂性类,很长一段时间以来的最好的研究结果都是近似度为1.5的算法,直到最近一个近似度为1.375的算法被提出来。虽然进展缓慢,但是研究该问题的理论不断得到简化,近似算法的时间复杂度也被不断降低。近似度为1.5的算法的最好时间复杂度的算法是由Hartman提出的,其时间复杂度为O(n3/2(logn1/2))。块交换比较简单,约十年前Christie就已经提出了时问复杂度为O(n2)的确定算法。