發(fā)布時(shí)間：2017-06-20 07:06

  本文關(guān)鍵詞：DNA序列比對(duì)并行算法研究及應(yīng)用，，由筆耕文化傳播整理發(fā)布。

【摘要】：生物信息學(xué)(Bioinformatics),指的是利用信息技術(shù)和計(jì)算機(jī)科學(xué)等方法,以研究大量而復(fù)雜的生物數(shù)據(jù)的一門交叉學(xué)科。目前,基因組學(xué)中的DNA排序問題的研究是生物信息學(xué)的重要研究領(lǐng)域之一。研究DNA序列的基本途徑是序列比對(duì),它通過序列的排列規(guī)律尋找序列間的相似性和同源性,從而分析研究生物的遺傳進(jìn)化信息。近年來(lái),隨著生物學(xué)的發(fā)展,基因序列數(shù)據(jù)量成倍增加,傳統(tǒng)的串行序列比對(duì)算法無(wú)法滿足日益擴(kuò)大的數(shù)據(jù)規(guī)模的需要。本文基于序列比對(duì)算法的特征研究其并行算法,提出一種序列編碼算法和數(shù)據(jù)“首條序列劃分”法,以有效提高算法的并行效率,為解決大規(guī)模生物序列比對(duì)問題奠定基礎(chǔ)。本文主要的創(chuàng)新性工作包括:(一)提出一種新的DNA序列編碼算法,實(shí)現(xiàn)基于MPI的并行FED算法。本文分析比較了DNA序列中精確比對(duì)(Exact Sequence Alignment)類型的算法,發(fā)現(xiàn)隨著數(shù)據(jù)量的增長(zhǎng),算法計(jì)算時(shí)間會(huì)顯著增加。為了解決這一問題,首先,我們提出了一種基于位運(yùn)算的序列編碼方式,以此降低數(shù)據(jù)存儲(chǔ)空間,加快序列編碼速度,從而提高算法效率;然后,采用并行算法對(duì)FED算法進(jìn)行改進(jìn),并通過消息傳遞模型(MPI)在集群環(huán)境下實(shí)現(xiàn)算法的并行化,實(shí)驗(yàn)表明,該并行算法在20核環(huán)境下運(yùn)行時(shí),加速比達(dá)到16.1。(二)提出最適合CVoting算法的“首條序列劃分”法,并基于MPI實(shí)現(xiàn)算法的并行。本文研究了模體發(fā)現(xiàn)問題(Motif Finding Problem)中計(jì)算挑戰(zhàn)實(shí)例的算法,CVoting是目前具有代表性的能解決大型挑戰(zhàn)實(shí)例的算法,但是它計(jì)算(21,8)挑戰(zhàn)實(shí)例的時(shí)間依然需要超過20小時(shí)。因此,本文基于MPI的特點(diǎn),設(shè)計(jì)三種數(shù)據(jù)劃分方法,分析和比較三種方法對(duì)算法的適應(yīng)性,提出“首條序列劃分”方法是適合CVoting算法并行的最佳方式。該方式不僅實(shí)現(xiàn)算法的并行,將(21,8)挑戰(zhàn)實(shí)例的運(yùn)算時(shí)間降低到20分鐘以內(nèi),而且算法從1個(gè)計(jì)算核開始一直到128個(gè)計(jì)算核始終保持加速比的線性增長(zhǎng),其中,在128核時(shí)加速比達(dá)到96.2。
【關(guān)鍵詞】：并行計(jì)算 DNA序列比對(duì) 模體發(fā)現(xiàn) MPI
【學(xué)位授予單位】：上海大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：Q811.4;TP338.6
【目錄】：

• 摘要6-7
• ABSTRACT7-11
• 第一章 緒論11-17
• 1.1 研究目的與意義11-12
• 1.2 國(guó)內(nèi)外研究概述12-14
• 1.3 本文的研究?jī)?nèi)容14-15
• 1.4 本文的組織結(jié)構(gòu)15
• 1.5 本章小結(jié)15-17
• 第二章 并行計(jì)算概論17-28
• 2.1 并行計(jì)算機(jī)發(fā)展歷程17-21
• 2.1.1 并行計(jì)算機(jī)系統(tǒng)17-19
• 2.1.2 并行計(jì)算機(jī)分類19-21
• 2.2 并行算法設(shè)計(jì)與評(píng)估方法21-23
• 2.2.1 并行算法設(shè)計(jì)21-22
• 2.2.2 并行算法評(píng)估方法22-23
• 2.3 并行算法編程23-26
• 2.3.1 并行編程模型分類23-24
• 2.3.2 主流并行編程模型介紹24-26
• 2.4 本章小結(jié)26-28
• 第三章 基于MPI的DNA序列比對(duì)并行算法28-43
• 3.1 FED算法介紹29-34
• 3.1.1 DNA序列比對(duì)算法29-30
• 3.1.2 序列編碼方式30-32
• 3.1.3 比對(duì)算法32-34
• 3.2 FED算法的改進(jìn)與并行化34-39
• 3.2.1 改進(jìn)序列編碼算法34-37
• 3.2.2 FED并行算法37-39
• 3.3 實(shí)驗(yàn)數(shù)據(jù)與結(jié)果分析39-42
• 3.3.1 實(shí)驗(yàn)環(huán)境39
• 3.3.2 實(shí)驗(yàn)數(shù)據(jù)和結(jié)果39-41
• 3.3.3 實(shí)驗(yàn)結(jié)果分析41-42
• 3.4 本章小結(jié)42-43
• 第四章 模體發(fā)現(xiàn)算法的并行化43-59
• 4.1 模體發(fā)現(xiàn)問題43-45
• 4.1.1 算法類型與發(fā)展現(xiàn)狀43-44
• 4.1.2 問題的提出與相關(guān)定義44-45
• 4.2 Cvoting算法45-47
• 4.2.1 Voting算法介紹45-46
• 4.2.2 候選模體集計(jì)算46-47
• 4.3 Cvoting算法的并行化47-53
• 4.3.1 數(shù)據(jù)劃分方式設(shè)計(jì)48-50
• 4.3.2 數(shù)據(jù)劃分方式比較50-53
• 4.4 實(shí)驗(yàn)數(shù)據(jù)與結(jié)果分析53-58
• 4.4.1 實(shí)驗(yàn)環(huán)境53-54
• 4.4.2 實(shí)驗(yàn)數(shù)據(jù)和結(jié)果54-57
• 4.4.3 實(shí)驗(yàn)結(jié)果分析57-58
• 4.5 本章小結(jié)58-59
• 第五章 總結(jié)與展望59-61
• 5.1 結(jié)論59-60
• 5.2 展望60-61
• 參考文獻(xiàn)61-67
• 作者在攻讀碩士學(xué)位期間公開發(fā)表的論文67-68
• 作者在攻讀碩士學(xué)位期間所作的項(xiàng)目68-69
• 致謝69

【共引文獻(xiàn)】

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

1 關(guān)亞林;曾艷奇;逯貴禎;;基于并行計(jì)算環(huán)境的混波室三維仿真[J];中國(guó)傳媒大學(xué)學(xué)報(bào)(自然科學(xué)版);2008年03期

2 程克非;羅江華;李紅波;;一種新的基于HPM并行計(jì)算性能數(shù)據(jù)采集方法[J];重慶郵電大學(xué)學(xué)報(bào)(自然科學(xué)版);2011年01期

3 王結(jié)臣;王豹;胡瑋;張輝;;并行空間分析算法研究進(jìn)展及評(píng)述[J];地理與地理信息科學(xué);2011年06期

4 阮定益;;并行式matlab平臺(tái)搭建[J];電腦知識(shí)與技術(shù);2008年08期

5 胡海峰;;樹狀成本估算模型的并行處理[J];電腦知識(shí)與技術(shù);2009年28期

6 古奮飛;王良俠;;淺析Linux集群技術(shù)[J];電腦知識(shí)與技術(shù);2010年06期

7 古奮飛;王良俠;張莉;;基于Linux集群的高性能低成本的校園網(wǎng)解決方案[J];電腦知識(shí)與技術(shù);2012年02期

8 李焱;胡祥云;金鋼燮;吳桂桔;廖國(guó)忠;王程;;基于MPI的一維大地電磁并行計(jì)算研究[J];地球物理學(xué)進(jìn)展;2010年05期

9 李焱;胡祥云;吳桂桔;葉益信;廖國(guó)忠;;基于MPI的二維大地電磁正演的并行計(jì)算[J];地震地質(zhì);2010年03期

10 劉曉群;鄒欣;范虹;;基于并行云計(jì)算模式的建筑結(jié)構(gòu)設(shè)計(jì)[J];電子技術(shù)應(yīng)用;2011年10期

  本文關(guān)鍵詞：DNA序列比對(duì)并行算法研究及應(yīng)用，由筆耕文化傳播整理發(fā)布。

本文編號(hào)：464763