本文關(guān)鍵詞：生物序列比對(duì)算法的并行優(yōu)化設(shè)計(jì)與實(shí)現(xiàn)

  更多相關(guān)文章： 雙序列比對(duì) 并行化算法 多序列比對(duì) 后綴樹

【摘要】：生物序列比對(duì)是生物信息學(xué)的基礎(chǔ)和核心,隨著生命科學(xué)的迅猛發(fā)展,需要研究的蛋白質(zhì)和核酸序列的信息顯著增加。常見的雙序列比對(duì)串行算法時(shí)間復(fù)雜度為O(N2),多序列比對(duì)時(shí)間復(fù)雜度更高,隨著序列長度的增加和比對(duì)規(guī)模的擴(kuò)大,時(shí)間開銷難以接受。在此情況下如果能夠挖掘算法的潛在并行性,通過數(shù)據(jù)劃分、流水處理等方式將算法并行化,使其在多個(gè)處理器上并行執(zhí)行,可以大大提升算法效率。本文首先對(duì)生物序列比對(duì)和并行算法的相關(guān)概念進(jìn)行了介紹。采取流水處理方式,將Needleman-Wunsch算法進(jìn)行并行化設(shè)計(jì)。在此基礎(chǔ)上提出了多個(gè)序列比對(duì)算法的并行化方法。通過找到多個(gè)checkpoint將矩陣劃分若干部分,為每個(gè)處理器分配矩陣的一個(gè)部分,使各處理器并行執(zhí)行子矩陣的Hirschberg算法并對(duì)完成后的結(jié)果進(jìn)行整合,將Hirschberg算法進(jìn)行并行化;通過提出使用活動(dòng)結(jié)點(diǎn)和活動(dòng)結(jié)點(diǎn)鏈表創(chuàng)建后綴樹的方法,使按分支并行構(gòu)建后綴樹和按分支獲取最大唯一匹配可以并行執(zhí)行并且擺脫了對(duì)后綴鏈表的依賴,之后并行對(duì)錨點(diǎn)間的空位進(jìn)行合并,將MUMmer算法進(jìn)行并行化;通過對(duì)角線并行方式并行獲取和擴(kuò)展熱點(diǎn)區(qū)域,采取將距離矩陣進(jìn)行分塊方式使多處理器并行獲取不同對(duì)角線上熱點(diǎn)區(qū)域的距離長度,將FASTA算法進(jìn)行并行化;通過距離矩陣分塊方式并行獲取序列兩兩比對(duì)的距離長度,以及并行從進(jìn)化樹的葉子向根進(jìn)行合并的方式,將Clustal W算法進(jìn)行了并行化。最后對(duì)上述4種算法及并行化算法分別進(jìn)行了實(shí)現(xiàn),將串行算法運(yùn)行時(shí)間與雙核及四核條件下并行算法的運(yùn)行時(shí)間進(jìn)行了比對(duì)。實(shí)驗(yàn)結(jié)果證明了并行化算法比串行化算法速度得到了很大提升,并且得到了不錯(cuò)的加速比,更適用于多核結(jié)構(gòu)。
【關(guān)鍵詞】：雙序列比對(duì) 并行化算法 多序列比對(duì) 后綴樹
【學(xué)位授予單位】：哈爾濱工業(yè)大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類號(hào)】：Q811.4;TP301.6
【目錄】：

• 摘要4-5
• Abstract5-8
• 第1章 緒論8-13
• 1.1 課題的研究背景和意義8
• 1.2 國內(nèi)外研究現(xiàn)狀8-12
• 1.2.1 常用序列比對(duì)算法9-10
• 1.2.2 并行序列比對(duì)現(xiàn)狀10-12
• 1.3 論文的主要內(nèi)容12-13
• 第2章 序列比對(duì)和并行計(jì)算13-27
• 2.1 序列比對(duì)13-18
• 2.1.1 全局比對(duì)14-16
• 2.1.2 局部比對(duì)16-18
• 2.1.3 近似比對(duì)18
• 2.1.4 多序列比對(duì)18
• 2.2 序列比對(duì)相關(guān)知識(shí)18-22
• 2.2.1 后綴樹18-21
• 2.2.2 利用后綴樹進(jìn)行字符串匹配21-22
• 2.3 并行計(jì)算22-26
• 2.3.1 OPENMP簡(jiǎn)介23
• 2.3.2 Needleman-Wunsch算法并行化23-25
• 2.3.3 分析算法的潛在并行性25-26
• 2.4 本章小結(jié)26-27
• 第3章 雙序列比對(duì)算法的并行化設(shè)計(jì)27-47
• 3.1 Hirschberg算法的并行化設(shè)計(jì)27-31
• 3.1.1 Hirschberg算法步驟27-29
• 3.1.2 Hirschberg算法并行化29-30
• 3.1.3 實(shí)驗(yàn)結(jié)果和分析30-31
• 3.2 MUMmer算法的并行化設(shè)計(jì)31-40
• 3.2.1 MUMmer算法步驟31-33
• 3.2.2 MUMmer算法并行化33-39
• 3.2.3 實(shí)驗(yàn)與實(shí)驗(yàn)結(jié)果分析39-40
• 3.3 FASTA算法的并行化設(shè)計(jì)40-45
• 3.3.1 FASTA算法步驟40-42
• 3.3.2 FASTA算法的并行化42-45
• 3.3.3 實(shí)驗(yàn)與分析45
• 3.4 本章小結(jié)45-47
• 第4章 多序列比對(duì)算法的并行化研究47-53
• 4.1 Clustal W算法步驟47-50
• 4.2 Clustal W算法的并行化50-51
• 4.2.1 距離矩陣的并行化獲取50-51
• 4.2.2 通過進(jìn)化樹獲取多序列比對(duì)結(jié)果51
• 4.3 實(shí)驗(yàn)與分析51-52
• 4.4 本章小結(jié)52-53
• 結(jié)論53-54
• 參考文獻(xiàn)54-58
• 攻讀學(xué)位期間發(fā)表的學(xué)術(shù)論文58-60
• 致謝60

【參考文獻(xiàn)】

中國期刊全文數(shù)據(jù)庫 前1條

1 陳潤生;生物信息學(xué)[J];生物物理學(xué)報(bào);1999年01期

，

本文編號(hào)：691000