论文摘要
早在193 8年，T．Dpbzhansky和A．H．Sturtevant就研究了基因组重组问题，证明两种果蝇的染色体基因序列可以通过基因组的17次翻转来进行相互转换，之后的研究证明，基因组重组是微生物，植物，动物进化的一种重要模式。一条染色体由一个基因序列组成，基因组是染色体的集合。基因组重组是基因组改变其中基因排列顺序的过程，因此可将一次基因组重组看作改变基因排列顺序的一次操作。最基本的重组操作有三种：翻转(reversal)，移位(translocation)和转位(transposition)。一般为了简单，在讨论基因组重排距离时，人们只考虑一种或两种操作。给定两个基因组A，B，在规定了可以使用的操作之后，计算A，B之间的距离等价于寻找从A到B的最短变换序列。我们将求这些基因组之间变换距离的问题称为基因组排序问题。本文主要讨论无向基因组的翻转排序算法及其实现方法。Caprara已经证明了无向基因组翻转排序问题是NP难解问题，Bafna和Pevzner对此问题给出一个近似度为7／4的算法。在这个算法提出前，Kececiogin和Sankoff曾给出一个近似度为2的贪心算法。目前较好的算法是christie(1998)给出的一个近似度为3／2时间复杂度为O(n~4)的近似算法。本文引入选择图的概念，通过求选择图的最大独立集完成圈分解，克服了原3／2近似算法进行圈分解时没有综合考虑圈图中二圈之间灰边和黑边的共享情况这一不足；而后根据求得的圈分解把无向基因组排列转化为有向基因组排列，再使用有向翻转排序算法进行排序，从而给出一个时间复杂度为O(n~2)近似度为3／2的近似算法。在此基础上我们还给出了一个求解无向基因组翻转排序问题的遗传算法，实验数据结果表明本文给出的O(n~2)的改进算法与遗传算法的平均解值比Christie的原3／2的近似算法有所改善。本文的主要创新点如下：·提出了选择图的概念，设计了一个求选择图最大独立集的启发式算法，通过此算法进行圈分解，改进了原3／2算法的圈分解方法。·根据圈分解把无向排列转化为有向排列，再使用有向翻转排序算法进行排序，避免了原算法中寻找翻转序列时，反复用红色顶点代表的翻转操作对翻转图进行翻转以确定是否产生新的无向连通分支的步骤，从而将原3／2算法的时间复杂度降为O(n~2)。·设计了一个求解无向基因组翻转排序问题的遗传算法。·用java实现了O(n~2)的改进算法和遗传算法，试验数据表明我们给出的改进算法和遗传算法的平均解值比原3／2的算法有所改善。本文的实验结果和数据对分子生物学中生物进化过程的研究具有一定的指导意义。