DNA序列中重復片段查找技術研究.pdf

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

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

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

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

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

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