DNA序列中串聯(lián)重復(fù)體查找算法研究.pdf

1、在DNA序列分析中，串聯(lián)重復(fù)體查找是一個(gè)重要的基礎(chǔ)性問題。人類DNA序列50％以上是由串聯(lián)重復(fù)體組成的。串聯(lián)重復(fù)體在基因表達(dá)、調(diào)控和遺傳等方面起著十分重要的作用，同時(shí)它是產(chǎn)生多種疾病的病因。另外以串聯(lián)重復(fù)體為基礎(chǔ)的“DNA指紋技術(shù)”在法醫(yī)學(xué)等領(lǐng)域廣泛應(yīng)用。因此關(guān)于串聯(lián)重復(fù)的研究具有十分重要的意義。
　　 本文主要研究了串聯(lián)重復(fù)體查找算法。⑴針對(duì)精確串聯(lián)重復(fù)體提出了一種基于LZ分解查找串聯(lián)重復(fù)體的算法。對(duì)于存儲(chǔ)在后綴樹上的字符串S

2、，該算法能在線性的時(shí)間找到所有出現(xiàn)在S中的串聯(lián)重復(fù)體。為了進(jìn)一步提高算法的效率，我們對(duì)后綴樹進(jìn)行了改進(jìn)，給中間節(jié)點(diǎn)加入了葉子信息數(shù)組，這樣就避免了算法對(duì)子樹的遍歷。⑵引入了一種新類型的近似串聯(lián)重復(fù)體-進(jìn)化串聯(lián)重復(fù)體，由于以前提出的算法都不能解決進(jìn)化串聯(lián)重復(fù)體的查找問題，因此提出了基于海明距離的查找算法。對(duì)于給定的重復(fù)單元的長度Z，該算法的時(shí)間復(fù)雜度為O(ln2)，解決了進(jìn)化串聯(lián)重復(fù)體的查找問題。為了說明算法的正確性和有效性，本文將這兩種