DNA序列中重復(fù)片段查找技術(shù)研究.pdf

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

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

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

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

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

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