本文關(guān)鍵詞：高通量轉(zhuǎn)錄組測(cè)序片段快速比對(duì)算法研究

  更多相關(guān)文章： De Bruijn圖 二維線段樹 序列比對(duì) 動(dòng)態(tài)規(guī)劃

【摘要】：基因序列比對(duì)技術(shù)是基因序列數(shù)據(jù)分析的重要組成部分,也是人們深入了解生物的遺傳特性,分析各種疾病,預(yù)防和抵御各種傳染疾病的基礎(chǔ)。新一代測(cè)序技術(shù)產(chǎn)生序列數(shù)據(jù)的速度更快,通量更高。因此出現(xiàn)了很多新型的RNA序列比對(duì)工具。然而,高速,精確地比對(duì)高通量RNA序列數(shù)據(jù)是一項(xiàng)非常具有挑戰(zhàn)性的任務(wù),當(dāng)前新型的RNA序列比對(duì)工具在速度和準(zhǔn)確率方面仍然有一定的不足。因此,開發(fā)一款速度快,準(zhǔn)確率高的RNA序列比對(duì)工具是一項(xiàng)非常有意義的工作。本文提出了一個(gè)高通量轉(zhuǎn)錄組測(cè)序片段快速比對(duì)工具RNA-fat。RNA-fat利用種子在read和參考基因組上位置的關(guān)系識(shí)別種子間的剪切點(diǎn)和結(jié)構(gòu)性變異,并且通過對(duì)種子構(gòu)圖,高效地尋找種子覆蓋read的最優(yōu)路徑。由于選擇出的最優(yōu)路徑對(duì)read具有很高的覆蓋度,算法在序列比對(duì)階段的計(jì)算量大幅降低。RNA-fat對(duì)參考基因組構(gòu)建De Bruijn圖,提取De Bruijn圖中所有的單一路徑并進(jìn)行排序,最終生成RNA-fat的索引。該索引由三個(gè)相互關(guān)聯(lián)的子索引構(gòu)成,且具有非常高的查詢效率。在剪切和結(jié)構(gòu)性變異的影響下,read未覆蓋區(qū)域的比對(duì)邊界在read上會(huì)出現(xiàn)交叉,在參考基因組上會(huì)出現(xiàn)長(zhǎng)空位。為了保證序列比對(duì)的準(zhǔn)確性,RNA-fat對(duì)每一種情況進(jìn)行判斷,精確計(jì)算出read未覆蓋區(qū)域在read和參考基因組上的比對(duì)邊界,并采用不同的比對(duì)策略進(jìn)行序列比對(duì)。通過實(shí)驗(yàn)數(shù)據(jù),我們首先驗(yàn)證了最優(yōu)覆蓋路徑的準(zhǔn)確性,這就為未覆蓋區(qū)域比對(duì)邊界搜索的準(zhǔn)確性打下了基礎(chǔ)。通過對(duì)尋找最優(yōu)路徑的動(dòng)態(tài)規(guī)劃算法優(yōu)化前后的效率對(duì)比,我們驗(yàn)證了二維線段樹對(duì)RNA-fat性能優(yōu)化的顯著作用。最后,我們將RNA-fat和現(xiàn)有的RNA序列比對(duì)工具在相同的實(shí)驗(yàn)環(huán)境和實(shí)驗(yàn)數(shù)據(jù)下進(jìn)行性能對(duì)比,我們發(fā)現(xiàn)RNA-fat具有高通量,速度快的優(yōu)勢(shì),且在read比對(duì)的正確率和堿基比對(duì)的正確率方面與現(xiàn)有RNA序列比對(duì)工具相當(dāng)。
【學(xué)位授予單位】：哈爾濱工業(yè)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：Q811.4

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

1 楊燁;劉娟;;第二代測(cè)序序列比對(duì)方法綜述[J];武漢大學(xué)學(xué)報(bào)(理學(xué)版);2012年05期

2 涂俐蘭;;兩兩序列比對(duì)的一種新方法[J];數(shù)學(xué)雜志;2006年01期

3 張濤濤;郭茂祖;鄒權(quán);;參數(shù)序列比對(duì)算法研究(英文)[J];生物信息學(xué);2008年02期

4 李方潔;劉希玉;陳潔;;基于改進(jìn)蟻群算法的DNA雙序列比對(duì)[J];南京師大學(xué)報(bào)(自然科學(xué)版);2010年04期

5 楊潔;劉海;;生物序列比對(duì)算法的研究現(xiàn)狀[J];中國(guó)科技信息;2011年09期

6 唐玉榮;生物信息學(xué)中的序列比對(duì)算法[J];計(jì)算機(jī)工程與應(yīng)用;2003年29期

7 李小妹,王能超;生物序列比對(duì)算法的簡(jiǎn)述[J];云南民族大學(xué)學(xué)報(bào)(自然科學(xué)版);2004年01期

8 劉陽(yáng);王小磊;李江域;毛逸清;趙東升;;局部序列比對(duì)算法及其并行加速研究進(jìn)展[J];軍事醫(yī)學(xué);2012年07期

9 王非;楊欣;June Y.Liberamy;;生物序列比對(duì)算法的實(shí)現(xiàn)與集成[J];計(jì)算機(jī)與應(yīng)用化學(xué);2004年04期

10 李大衛(wèi);;基于動(dòng)態(tài)規(guī)劃的序列比對(duì)的并行算法研究[J];井岡山大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年03期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前4條

1 王盛;吳長(zhǎng)剛;孫慰遲;;帶約束星形序列比對(duì)復(fù)雜性的研究[A];2006年全國(guó)理論計(jì)算機(jī)科學(xué)學(xué)術(shù)年會(huì)論文集[C];2006年

2 許龍飛;段敏;陳孝衛(wèi);冉麗;朱嬋;;生物DNA序列比對(duì)算法研究[A];第二十一屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集（技術(shù)報(bào)告篇）[C];2004年

3 方慧生;陳凱先;;一個(gè)有效解決遠(yuǎn)距離同源蛋白質(zhì)結(jié)構(gòu)預(yù)測(cè)及序列比對(duì)的有效方法[A];中國(guó)化學(xué)會(huì)第26屆學(xué)術(shù)年會(huì)化學(xué)信息學(xué)與化學(xué)計(jì)量學(xué)分會(huì)場(chǎng)論文集[C];2008年

4 陳婷婷;郭婷婷;李林;安冬;;基于生物信息學(xué)的功能蛋白基因序列分類研究[A];2011年全國(guó)通信安全學(xué)術(shù)會(huì)議論文集[C];2011年

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前5條

1 陳科;最優(yōu)化方法在生物序列比對(duì)中的應(yīng)用與研究[D];電子科技大學(xué);2010年

2 唐玉榮;生物信息學(xué)中的序列比對(duì)算法研究[D];中國(guó)農(nóng)業(yè)大學(xué);2004年

3 李玉崗;生物大分子序列比對(duì)和蛋白質(zhì)結(jié)構(gòu)分類算法[D];中國(guó)科學(xué)院研究生院（計(jì)算技術(shù)研究所）;2004年

4 康曉軍;基因序列比對(duì)算法在SNP中的研究及應(yīng)用[D];華中農(nóng)業(yè)大學(xué);2011年

5 夏飛;生物序列分析算法硬件加速器關(guān)鍵技術(shù)研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2011年

中國(guó)碩士學(xué)位論文全文數(shù)據(jù)庫(kù) 前10條

1 汪浩;基因序列比對(duì)算法的優(yōu)化研究[D];中國(guó)農(nóng)業(yè)科學(xué)院;2015年

2 盧山;高通量轉(zhuǎn)錄組測(cè)序片段快速比對(duì)算法研究[D];哈爾濱工業(yè)大學(xué);2015年

3 李研;生物序列比對(duì)算法的并行優(yōu)化設(shè)計(jì)與實(shí)現(xiàn)[D];哈爾濱工業(yè)大學(xué);2015年

4 薛倩斐;DNA序列比對(duì)并行算法研究及應(yīng)用[D];上海大學(xué);2015年

5 曹金玲;基于種子的序列比對(duì)方法研究[D];吉林大學(xué);2008年

6 黃寧;生物序列比對(duì)[D];蘇州大學(xué);2009年

7 呂艷萍;生物序列比對(duì)問題的研究[D];福州大學(xué);2005年

8 劉淼;基于平衡分割的并行序列比對(duì)[D];西安電子科技大學(xué);2007年

9 陳斐;蟻群算法在序列比對(duì)中的應(yīng)用研究[D];湖南大學(xué);2008年

10 尚婧;下一代測(cè)序短序列比對(duì)軟件算法比較及評(píng)價(jià)[D];蘇州大學(xué);2013年

，

本文編號(hào)：1218436