基于de Bruijn圖的短序列拼接算法的優(yōu)化及并行化.pdf

1、中圖分類號(hào)U D CT P 3 9 16 0 0碩士學(xué)位論文學(xué)校代碼密級(jí)1 0 5 3 3基于d e B r u i j n 圖的短序列拼接算法的優(yōu)化及并行化A p a r a l l e la n d o p t i m i z e d a l g o r i t h m sf o rd e n O V O S l a O r tr e a da s s e m b l y U S l n g d e 1 5 r u l l n z

2、r a o n s ，' - ， ?作者姓名 學(xué)科專業(yè)研究方向?qū)W院( 系、所)指導(dǎo)教師： 邱 鳳：計(jì)算機(jī)科學(xué)與技術(shù)：生物信息學(xué)：信息科學(xué)與工程學(xué)院：胡志剛教授答辯委員會(huì)主席中 南 大 學(xué)二零一三年四月 一令一二，半幽月基于d e B r u i j n 圖的短序列拼接算法的優(yōu)化及并行化摘要：基因組測序一直是基因組學(xué)的核心內(nèi)容，隨著測序技術(shù)的產(chǎn)生和發(fā)展，人們能在較短時(shí)間內(nèi)獲得大量測序數(shù)據(jù)。測序技術(shù)朝著高通量、低成本、高精度的方向發(fā)

3、展，積累的測序數(shù)據(jù)也隨之越來越多。如何快速、準(zhǔn)確地處理海量測序數(shù)據(jù)己成為D N A 測序發(fā)展的瓶頸。本文通過對(duì)現(xiàn)有基于d eB r u i j n 圖算法的新一代測序技術(shù)優(yōu)缺點(diǎn)的深入分析和研究，針對(duì)得到的r e a d 片段長度短、數(shù)量多以及通量高的特點(diǎn)，研究設(shè)計(jì)了基于d e B r u i j n 圖的優(yōu)化算法。在序列拼接的過程中引入決策表的概念，通過決策表中的信息更新來優(yōu)化d e B r u i j n圖中最優(yōu)路徑的選擇，縮小后繼k

4、 ．m e r 的選擇范圍，從而達(dá)到縮短序列拼接時(shí)間，提高c o n t i g 準(zhǔn)確率的目的。在優(yōu)化算法的基礎(chǔ)上，提出了算法的并行化處理方案，通過分別對(duì)I ／O 讀取和存儲(chǔ)的并行化以及拼接過程中的并行化設(shè)計(jì)，達(dá)到進(jìn)一步縮短拼接時(shí)間，減少單機(jī)上存儲(chǔ)壓力，提高計(jì)算性能的目的。仿真實(shí)驗(yàn)結(jié)果表明，本文提出的基于d eB r u i j n 圖算法的短序列拼接算法的優(yōu)化及并行化設(shè)計(jì)與新一代測序技術(shù)中的基于d eB r u i j n圖算法相比，