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

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

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