隨著新一代測序技術(shù)的發(fā)展,DNA/RNA測序數(shù)據(jù)已經(jīng)成為遺傳學(xué)、生物信息、細(xì)胞生物學(xué)、系統(tǒng)生物學(xué)中最豐富的數(shù)據(jù)。DNA/RNA測序已經(jīng)成為研究生命科學(xué)的基本手段,然而如何有效利用這些測序數(shù)據(jù)是一個(gè)很大的課題。本文主要研究面向DNA/RNA大數(shù)據(jù)的序列比對。序列比對領(lǐng)域已有一些廣為人知算法,譬如在序列數(shù)據(jù)庫中搜索的BLAST算法,或是用于成對比對的Smith-Waterman算法。但這些標(biāo)準(zhǔn)的算法未必適用于新的測序數(shù)據(jù)。譬如Smith-Waterman算法受制于內(nèi)存的限制,無法用于超長序列之間的比對;同時(shí)Smith-Waterman算法也無法展示一對序列之間多個(gè)匹配段之間的協(xié)同關(guān)系。為此,本論文研究了如下兩方面內(nèi)容:（1）超長序列之間的比對問題。本文提出了 PAAVLS算法來解決Smith-Waterman算法面臨的內(nèi)存不足問題。PAAVLS算法提出了矩陣骨架的概念,減少了需要保存的信息,降低了對內(nèi)存的需求,可適用于超長序列之間的比對。（2）包含超長gap的序列比對問題。本文提出了SLGAA算法來研究序列之間的復(fù)雜關(guān)系。傳統(tǒng)的Smith-Waterman算法不能容忍較長的gap,因此只能... 

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

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

【文章目錄】：
摘要
Abstract
第一章 緒論
    1.1 背景
    1.2 生物序列及序列比對基本知識(shí)
        1.2.1 生物序列
        1.2.2 序列比對
        1.2.3 序列比對分類
    1.3 測序技術(shù)革新產(chǎn)生DNA/RNA大數(shù)據(jù)
    1.4 序列比對的重要性
    1.5 本文的結(jié)構(gòu)
第二章 相關(guān)知識(shí)
    2.1 字符串比對的動(dòng)態(tài)規(guī)劃算法
        2.1.1 動(dòng)態(tài)規(guī)劃算法思想
        2.1.2 動(dòng)態(tài)規(guī)劃算法
    2.2 BLAST算法
        2.2.1 BLAST軟件包介紹
        2.2.2 BLAST算法思想
    2.3 Needleman-Wunsch算法
        2.3.1 Needleman-Wunsch算法思想
    2.4 Simith-Waterman算法
    2.5 相關(guān)算法分析討論
        2.5.1 相關(guān)比對算法的特點(diǎn)分析
        2.5.2 比對中現(xiàn)存的其它問題
第三章 面向超長序列的比對算法
    3.1 超長序列比對問題的背景
        3.1.1 序列比對中存在的問題
        3.1.2 PAAVLS算法的提出
    3.2 超長序列的比對算法
        3.2.1 算法思路
        3.2.2 算法流程
    3.3 回溯函數(shù)Trace(Hxy,x,y)
        3.3.1 基本思路
        3.3.2 算法流程和偽代碼
    3.4 實(shí)驗(yàn)與結(jié)果分析
        3.4.1 PAAVLS算法實(shí)驗(yàn)結(jié)果分析
        3.4.2 PAAVLS算法的時(shí)間復(fù)雜度分析
第四章 針對超長Gap的序列比對算法
    4.1 序列比對中的超長gap
        4.1.1 問題背景
        4.1.2 SLGAA算法的提出
    4.2 超長gap序列比對算法
        4.2.1 基本思路
        4.2.2 算法偽代碼
    4.3 實(shí)驗(yàn)與結(jié)果分析
        4.3.1 SLGAA算法的實(shí)驗(yàn)設(shè)置
        4.3.2 比對中沒有超長gap的結(jié)果分析
        4.3.3 比對中存在超長gap的結(jié)果分析
        4.3.4 算法的時(shí)間復(fù)雜度分析
第五章 總結(jié)
    5.1 主要工作與創(chuàng)新點(diǎn)
    5.2 展望
參考文獻(xiàn)
發(fā)表論文和參加科研情況說明
致謝


【參考文獻(xiàn)】：
期刊論文
[1]生物信息學(xué)序列比對算法分析[J]. 黃佳琪.  生物技術(shù)世界. 2015(11)
[2]字符串匹配算法在DNA序列比對中的應(yīng)用[J]. 陳建平.  數(shù)學(xué)建模及其應(yīng)用. 2015(03)
[3]生物信息學(xué)中序列比對技術(shù)和算法研究進(jìn)展[J]. 李美滿.  現(xiàn)代計(jì)算機(jī)(專業(yè)版). 2012(26)
[4]基于動(dòng)態(tài)規(guī)劃的序列比對的并行算法研究[J]. 李大衛(wèi).  井岡山大學(xué)學(xué)報(bào)(自然科學(xué)版). 2011(03)
[5]生物序列比對算法的研究現(xiàn)狀[J]. 楊潔,劉海.  中國科技信息. 2011(09)
[6]多序列比對算法的研究進(jìn)展[J]. 鄒權(quán),郭茂祖,韓英鵬,李文濱.  生物信息學(xué). 2010(04)
[7]生物序列比對算法的研究現(xiàn)狀[J]. 文鳳春,王邦菊,肖枝洪.  生物信息學(xué). 2010(01)
[8]DNA序列比對數(shù)目的算法研究[J]. 徐琛梅,劉曉杰.  大學(xué)數(shù)學(xué). 2008(01)
[9]生物信息學(xué)中的序列比對算法[J]. 張永,王瑞.  電腦知識(shí)與技術(shù). 2008(01)
[10]生物信息學(xué)中的雙序列比對算法[J]. 劉超,馬志強(qiáng),劉帥.  長春工程學(xué)院學(xué)報(bào)(自然科學(xué)版). 2006(03)



本文編號(hào)：3676735