發(fā)布時間：2021-06-08 15:21

　　伴隨著人類基因組計劃（HGP）的實(shí)施,使得生物學(xué)的相關(guān)數(shù)據(jù)迅速增長,但是對于這些大量的數(shù)據(jù)如何被處理,已成為生物科學(xué)家的一個難題。目前,基因序列的比較分析是生物信息處理中的最重要的研究內(nèi)容之一。Needleman-Wunsch算法是根據(jù)動態(tài)規(guī)劃算法的思想進(jìn)行研究與分析的,它也是研究雙序列比對問題的一個最根本的算法。該算法雖然可以獲得雙序列比對時的最優(yōu)結(jié)果,但是它的時間復(fù)雜度和空間復(fù)雜度較高,均為O（n*m）（其中n和m分別表示兩條序列的長度）。因此難以實(shí)現(xiàn)實(shí)際的生物序列比對問題。本文主要是以基于動態(tài)規(guī)劃思想的Needleman-Wunsch算法為研究對象,對其進(jìn)行研究與分析,進(jìn)而提出該算法的改進(jìn)方法。然后通過大量的實(shí)驗(yàn)對改進(jìn)前后該算法在實(shí)現(xiàn)雙序列比較時運(yùn)行所花費(fèi)的時間進(jìn)行比較與分析。實(shí)驗(yàn)的結(jié)果表明,當(dāng)兩條序列比對的得分和準(zhǔn)確率不變的情況下,Needleman-Wunsch的改進(jìn)算法可以有效地降低原來算法的運(yùn)行時間。本文主要研究的內(nèi)容和要完成的工作有以下幾點(diǎn):（1）首先了解了雙序列比對問題的研究現(xiàn)狀。同時,研究Needleman-Wunsch算法實(shí)現(xiàn)兩條序列比對的結(jié)果,從而分析該算法可能... 

【文章來源】：內(nèi)蒙古農(nóng)業(yè)大學(xué)內(nèi)蒙古自治區(qū)

【文章頁數(shù)】：53 頁

【學(xué)位級別】：碩士

【文章目錄】：
摘要
Abstract
1 緒論
    1.1 論文研究背景和意義
        1.1.1 研究背景
        1.1.2 研究意義
    1.2 雙序列比對算法的國內(nèi)外研究現(xiàn)狀
    1.3 論文的研究內(nèi)容
    1.4 論文的組織結(jié)構(gòu)
    1.5 本章小結(jié)
2 雙序列比對問題概況
    2.1 雙序列比對問題
        2.1.1 雙序列比對問題的描述
        2.1.2 雙序列比對問題的數(shù)學(xué)定義
        2.1.3 比對得分矩陣和空位罰分
    2.2 基于動態(tài)規(guī)劃的Needleman-Wunsch算法
        2.2.1 動態(tài)規(guī)劃思想描述
        2.2.2 Needleman-Wunsch算法
            2.2.2.1 Needleman-Wunsch算法基本思想
            2.2.2.2 Needleman-Wunsch算法實(shí)現(xiàn)流程及步驟
        2.2.3 Needleman-Wunsch算法的優(yōu)缺點(diǎn)
            2.2.3.1 Needleman-Wunsch算法的優(yōu)點(diǎn)
            2.2.3.2 Needleman-Wunsch算法的缺點(diǎn)
    2.3 本章小結(jié)
3 Needleman-Wunsch算法的改進(jìn)算法
    3.1 Needleman-Wunsch算法改進(jìn)思路
    3.2 改進(jìn)后Needleman-Wunsch算法的實(shí)現(xiàn)流程及步驟
    3.3 本章小結(jié)
4 實(shí)驗(yàn)與分析
    4.1 實(shí)驗(yàn)環(huán)境
    4.2 改進(jìn)前后Needleman-Wunsch算法的實(shí)現(xiàn)代碼分析
    4.3 改進(jìn)前后Needleman-Wunsch算法實(shí)驗(yàn)與分析
        4.3.1 基于動物基因的實(shí)驗(yàn)結(jié)果分析
        4.3.2 基于植物基因的實(shí)驗(yàn)結(jié)果分析
    4.4 實(shí)驗(yàn)小結(jié)
5 總結(jié)與展望
    5.1 總結(jié)
    5.2 展望
致謝
參考文獻(xiàn)
作者簡介


【參考文獻(xiàn)】：
期刊論文
[1]《運(yùn)籌學(xué)》課程教學(xué)探索與實(shí)踐[J]. 王小林.  長江大學(xué)學(xué)報(自然科學(xué)版)理工卷. 2010(03)
[2]序列比對算法的并行化研究與應(yīng)用[J]. 張福祥,周金玲.  濰坊學(xué)院學(xué)報. 2008(04)
[3]消息傳遞模型的并行性能研究[J]. 郭紅霞,潘斌.  成都大學(xué)學(xué)報(自然科學(xué)版). 2007(01)
[4]生物信息學(xué)中一個優(yōu)化的全局雙序列比對算法[J]. 唐玉榮.  計算機(jī)應(yīng)用. 2004(S1)
[5]兩序列比對的Hirschberg算法[J]. 張福祥.  濰坊學(xué)院學(xué)報. 2003(04)
[6]生物信息學(xué)的現(xiàn)狀與展望[J]. 張春霆.  世界科技研究與發(fā)展. 2000(06)

博士論文
[1]生物信息學(xué)中多序列比對等算法的研究[D]. 張敏.大連理工大學(xué) 2005
[2]生物信息學(xué)中的序列比對算法研究[D]. 唐玉榮.中國農(nóng)業(yè)大學(xué) 2004

碩士論文
[1]雙序列比對Needleman-Wunsch算法的分布式并行優(yōu)化研究[D]. 馮百龍.內(nèi)蒙古農(nóng)業(yè)大學(xué) 2015
[2]生物序列比對算法的并行優(yōu)化設(shè)計與實(shí)現(xiàn)[D]. 李研.哈爾濱工業(yè)大學(xué) 2015
[3]生物序列比較算法的研究[D]. 郭曉冬.杭州電子科技大學(xué) 2012
[4]雙序列比對算法研究與并行優(yōu)化[D]. 李川.西安電子科技大學(xué) 2011
[5]基于平衡分割的并行序列比對[D]. 劉淼.西安電子科技大學(xué) 2007
[6]并行遺傳算法在生物序列比對中的應(yīng)用研究[D]. 魏靜.天津大學(xué) 2004



本文編號：3218740