基于第一降序小隊翻轉(zhuǎn)排序算法的設(shè)計與實現(xiàn).pdf

1、基因組翻轉(zhuǎn)排序在基因組重組研究與實踐中具有重要價值，本文研究基因組翻轉(zhuǎn)排序的計算方法?；蚪M翻轉(zhuǎn)排序目的是計算兩個基因組之間的最少翻轉(zhuǎn)次數(shù)，最少翻轉(zhuǎn)次數(shù)稱為兩個基因組之間的翻轉(zhuǎn)距離。有向基因組翻轉(zhuǎn)排序由Hannenhalli等最先給出多項式時間求解算法，目前所知最好的算法時間復(fù)雜性為O(n<'2>)。無向基因組翻轉(zhuǎn)排序由Capara證明為NP-Hard。 已有的無向基因組翻轉(zhuǎn)排序算法過程復(fù)雜，實現(xiàn)困難。本文提出了無向基因組翻轉(zhuǎn)排

2、序的一種新啟發(fā)式算法，編程實現(xiàn)了該算法，本文簡稱為FDSR算法。在PentiumIll800/256M計算機上的實驗表明，F(xiàn)DSR計算193個基因符號的翻轉(zhuǎn)所需計算時間為10毫秒，計算5000符號的基因組翻轉(zhuǎn)所需計算時間為1.282秒。本文證明了算法的正確性。我們利用程序驗證了算法求解的優(yōu)化程度，實驗結(jié)果表明，對于100個較小的基因組，用本文算法得到的解中有68個為最優(yōu)解。 FDSR算法主要思想為，先在基因排列中找降序小隊，

3、在其末元素和逆相鄰元素之間作相應(yīng)的翻轉(zhuǎn)操作。算法難點在于當(dāng)基因排列不存在降序小隊時，需要通過調(diào)整獲得降序小隊。 程序的實現(xiàn)過程是，首先設(shè)置并初始化一個基因排列的存儲空間，然后讀入基因排列的數(shù)據(jù)項，接著校驗基因排列是否正確，若正確則對其進行斷點式轉(zhuǎn)換并進行翻轉(zhuǎn)排序，否則中止程序的運行。 本文創(chuàng)新點表現(xiàn)在下面幾個方面： (1)本文將兩個斷點之間的部分序列稱為一個斷點式。通過翻轉(zhuǎn)斷點式使斷點的個數(shù)逐步減少，從而

4、接近目標(biāo)基因組序列。 (2)論文中提出了第一降序小隊概念。降序小隊是翻轉(zhuǎn)斷點式的基點，采用第一降序小隊作為基點可以減少查找基點的時間，從而提高了算法的時間效率。 (3)論文給出了算法的正確性證明，算法時間復(fù)雜度為O(n<'2>)，n為基因排列中基因個數(shù)。 (4)設(shè)計并用C++語言實現(xiàn)了翻轉(zhuǎn)排序算法。在算法實現(xiàn)中，基因排列的存儲空間不僅能存儲數(shù)掘，還能夠根據(jù)需要存儲斷點。利用增加空間的方法，減少確定斷點式和翻