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

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

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

【學位級別】：碩士

【文章目錄】：
摘要
Abstract
1 緒論
    1.1 論文研究背景和意義
        1.1.1 研究背景
        1.1.2 研究意義
    1.2 雙序列比對算法的國內(nèi)外研究現(xiàn)狀
    1.3 論文的研究內(nèi)容
    1.4 論文的組織結構
    1.5 本章小結
2 雙序列比對問題概況
    2.1 雙序列比對問題
        2.1.1 雙序列比對問題的描述
        2.1.2 雙序列比對問題的數(shù)學定義
        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算法實現(xiàn)流程及步驟
        2.2.3 Needleman-Wunsch算法的優(yōu)缺點
            2.2.3.1 Needleman-Wunsch算法的優(yōu)點
            2.2.3.2 Needleman-Wunsch算法的缺點
    2.3 本章小結
3 Needleman-Wunsch算法的改進算法
    3.1 Needleman-Wunsch算法改進思路
    3.2 改進后Needleman-Wunsch算法的實現(xiàn)流程及步驟
    3.3 本章小結
4 實驗與分析
    4.1 實驗環(huán)境
    4.2 改進前后Needleman-Wunsch算法的實現(xiàn)代碼分析
    4.3 改進前后Needleman-Wunsch算法實驗與分析
        4.3.1 基于動物基因的實驗結果分析
        4.3.2 基于植物基因的實驗結果分析
    4.4 實驗小結
5 總結與展望
    5.1 總結
    5.2 展望
致謝
參考文獻
作者簡介


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

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

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



本文編號：3218740