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

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

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

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

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