1、生物信息學(xué)是20世紀80年代末，隨著人類基因組計劃的不斷發(fā)展，基因序列和蛋白質(zhì)數(shù)據(jù)的急速增加，以及信息理論和計算機技術(shù)的不斷發(fā)展而逐漸形成的。在過去的十幾年中人類對生物信息學(xué)，特別是DNA和人類基因序列的研究取得了長足的發(fā)展。海量DNA序列的測試完成和發(fā)布使人們可以利用計算機技術(shù)對包括DNA、RNA和蛋白質(zhì)等生物序列進行分析，為生物學(xué)家提供更多有價值的信息。 在DNA序列分析中，重復(fù)片段查找是一個重要的基礎(chǔ)性問題。人類DNA序

2、列50％以上是由重復(fù)片段組成的，這些重復(fù)片段隱含了大量的生物進程信息，其中包含豐富的古生物記錄，并提供許多關(guān)鍵的生物進化線索。目前，重復(fù)片段作為一個重要的遺傳標記，已廣泛運用于精密遺傳連鎖作圖、腫瘤生化研究、法醫(yī)學(xué)個體識別、親子鑒定和群體遺傳學(xué)分析等領(lǐng)域。在這種研究背景下，本文深入研究了DNA序列中重復(fù)片段查找問題，提出了面向重復(fù)片段查找的輕量級索引結(jié)構(gòu)；針對重復(fù)片段的精確和相似性查找問題設(shè)計了高效的查找算法。本文的主要貢獻總結(jié)如下：

3、 (1)針對用于重復(fù)片段查找的后綴樹、增強后綴數(shù)組等索引結(jié)構(gòu)的空間需求過大的問題，提出了一種面向重復(fù)片段查找的輕量級索引結(jié)構(gòu)，稱為后繼數(shù)組。設(shè)計了一種基于基數(shù)排序的后繼數(shù)組建立算法，其創(chuàng)建效率要優(yōu)于后綴樹和增強后綴數(shù)組的創(chuàng)建算法。根據(jù)生物信息學(xué)中的應(yīng)用提出了面向多序列重復(fù)片段查詢的多序列后繼數(shù)組索引。分析了后繼數(shù)組和多序列后繼數(shù)組所需存儲空間，并提出了節(jié)約存儲空間的有效方法。分析表明，后繼數(shù)組所需的存儲空間遠小于后綴樹、增強后綴

4、數(shù)組等索引結(jié)構(gòu)，多序列后繼數(shù)組存儲空間也遠小于多序列后綴樹的存儲空間； (2)針對精確重復(fù)片段查找問題，提出了一種新的重復(fù)片段的定義，即最大模式重復(fù)片段(LPR)。與其它重復(fù)片段的定義相比，比如tandem repeat，maximalrepetition，最大模式重復(fù)片段的查找結(jié)果包含了tandem repeat、maximal repetition等概念的全部重復(fù)片段信息，并明確表達出了重復(fù)片段的模式，并從理論上證明了在長

5、度為n的序列中，最大模式重復(fù)片段的數(shù)量是O(n)數(shù)量級的。然后提出了在后綴樹上查找序列中全部最大模式重復(fù)片段的算法；設(shè)計了基于后繼數(shù)組的最大模式重復(fù)片段查找算法。性能分析表明基于后繼數(shù)組的最大模式重復(fù)片段查找算法的性能要優(yōu)于基于后綴樹的查找方法； (3)針對相似性重復(fù)片段查找問題，分別提出了基于海明距離和編輯距離的相似性重復(fù)片段查找方法。針對海明距離衡量片段間相似性的不足，提出了模式相似度和片段相似度的概念，并在此基礎(chǔ)上提出

6、了相似性重復(fù)片段的定義SATR，設(shè)計了基于后繼數(shù)組的SATR查找算法。在基于編輯距離的相似性重復(fù)片段查找中，通過對編輯距離的分析，提出了保守字符對的概念和重復(fù)片段相似性衡量方法，這種衡量方法既表達了距離與待比較片段間長度的關(guān)系，同時又避免了片段長度的限制；針對編輯距離計算的復(fù)雜性，提出了基于頻率距離、Pearson相關(guān)性以及分段頻率距離(Partitioned Frequency Distance)的重復(fù)片段候選集的過濾方法。針對傳統(tǒng)的