基因組斷點標本字符串提取算法.pdf

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

2、,D.Sankoff提出了一個去解決允許—條染色體上有重復基因的基因組重排問題的方法,即分別生成源基因組和目標基因組的一個包含所有基因且沒有重復的子串。因為生成的子串可能有多種情況,目標就是找到這樣一個子串對:它包含的兩個子串互相轉(zhuǎn)換所需的操作步數(shù)在所有的子串對中是最少的。由此建立了這樣一個比較兩條染色體基因序列的相似程度問題的數(shù)學模型:假設兩條待比較的染色體上所含的基因種類是相同的。每條染色體看作一個字符串,每個基因是一個字母。一條染

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