版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、生物信息學(xué)是20世紀(jì)80年代末,隨著人類(lèi)基因組計(jì)劃的不斷發(fā)展,基因序列和蛋白質(zhì)數(shù)據(jù)的急速增加,以及信息理論和計(jì)算機(jī)技術(shù)的不斷發(fā)展而逐漸形成的。在過(guò)去的十幾年中人類(lèi)對(duì)生物信息學(xué),特別是DNA和人類(lèi)基因序列的研究取得了長(zhǎng)足的發(fā)展。海量DNA序列的測(cè)試完成和發(fā)布使人們可以利用計(jì)算機(jī)技術(shù)對(duì)包括DNA、RNA和蛋白質(zhì)等生物序列進(jìn)行分析,為生物學(xué)家提供更多有價(jià)值的信息。 在DNA序列分析中,重復(fù)片段查找是一個(gè)重要的基礎(chǔ)性問(wèn)題。人類(lèi)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)的
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- DNA序列中相似性重復(fù)片段查找技術(shù)研究.pdf
- DNA序列中串聯(lián)重復(fù)體查找算法研究.pdf
- 24104.dna序列中串聯(lián)重復(fù)定位的研究
- 時(shí)間序列挖掘與相似性查找技術(shù)研究.pdf
- DNA序列中基于后綴樹(shù)的重復(fù)體識(shí)別算法.pdf
- 左手β螺線管折疊子序列內(nèi)部重復(fù)片段分析.pdf
- 基因序列中Tandem Repeats查找方法研究.pdf
- Immunoglobulin-like β-sandwich類(lèi)和JellyRolls類(lèi)蛋白序列內(nèi)部重復(fù)片段研究.pdf
- 16952.生物基因序列中重復(fù)序列的研究
- DNA計(jì)算中若干DNA序列設(shè)計(jì)方法的研究.pdf
- dna簡(jiǎn)單重復(fù)序列基因分型的新方案
- 網(wǎng)絡(luò)備份中重復(fù)數(shù)據(jù)刪除技術(shù)研究.pdf
- 交叉分片技術(shù)在DNA序列挖掘中的應(yīng)用.pdf
- 語(yǔ)言無(wú)關(guān)的重復(fù)代碼查找工具.pdf
- 時(shí)間序列挖掘和相似性查找技術(shù)的研究.pdf
- 視頻序列中的笑臉識(shí)別技術(shù)研究.pdf
- 序列密碼中若干關(guān)鍵技術(shù)研究.pdf
- 重復(fù)數(shù)據(jù)刪除技術(shù)研究.pdf
- 重復(fù)正負(fù)序列模式挖掘關(guān)鍵技術(shù)的研究.pdf
- (ngs)dna序列分析技術(shù)-thermofisherscientific
評(píng)論
0/150
提交評(píng)論