基因組斷點(diǎn)標(biāo)本字符串提取算法.pdf

1、從90年代初開(kāi)始,隨著人類基因組計(jì)劃的展開(kāi)與深入,科學(xué)工作者發(fā)現(xiàn),人類的各種遺傳、性狀和甚至疾病等都與基因有著密切的聯(lián)系?；虻妮d體是染色體,即一條完整的基因序列。不同的染色體代表某個(gè)個(gè)體在不同方面的性狀。以往的研究表明,對(duì)應(yīng)同一性狀的兩個(gè)個(gè)體的染色體的基因序列的相似程度,與這兩個(gè)個(gè)體的某種性狀的相似程度相關(guān)。
　　 本文只討論一個(gè)基因組僅包括一條染色體的且允許同一基因組包含重復(fù)基因(但同一種基因最多出現(xiàn)兩次)的情況。1999年

2、,D.Sankoff提出了一個(gè)去解決允許—條染色體上有重復(fù)基因的基因組重排問(wèn)題的方法,即分別生成源基因組和目標(biāo)基因組的一個(gè)包含所有基因且沒(méi)有重復(fù)的子串。因?yàn)樯傻淖哟赡苡卸喾N情況,目標(biāo)就是找到這樣一個(gè)子串對(duì):它包含的兩個(gè)子串互相轉(zhuǎn)換所需的操作步數(shù)在所有的子串對(duì)中是最少的。由此建立了這樣一個(gè)比較兩條染色體基因序列的相似程度問(wèn)題的數(shù)學(xué)模型:假設(shè)兩條待比較的染色體上所含的基因種類是相同的。每條染色體看作一個(gè)字符串,每個(gè)基因是一個(gè)字母。一條染

3、色體上的基因可以重復(fù),問(wèn)兩條染色體是否存在這樣一個(gè)公共子串:子串中每種基因均出現(xiàn)且只出現(xiàn)一次。是否存在這樣的公共子串從某種程度上量化了兩個(gè)基因組參與某一個(gè)生物進(jìn)程的共同程度。
　　 本文考慮一個(gè)基因組只包含一條染色體且每種基因在每個(gè)基因組上最多出現(xiàn)兩次的情況。首次提出了無(wú)符號(hào)的情況下,解決這個(gè)問(wèn)題的一個(gè)精確算法。詳細(xì)分析了它的時(shí)間復(fù)雜度,給出了它的正確性證明,用Java語(yǔ)言實(shí)現(xiàn)了它,并用隨機(jī)生成的實(shí)驗(yàn)數(shù)據(jù)驗(yàn)證了該算法的性能。