發(fā)布時(shí)間：2022-08-13 09:02

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

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

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

【文章目錄】：
摘要
Abstract
第一章 緒論
    1.1 背景
    1.2 生物序列及序列比對(duì)基本知識(shí)
        1.2.1 生物序列
        1.2.2 序列比對(duì)
        1.2.3 序列比對(duì)分類(lèi)
    1.3 測(cè)序技術(shù)革新產(chǎn)生DNA/RNA大數(shù)據(jù)
    1.4 序列比對(duì)的重要性
    1.5 本文的結(jié)構(gòu)
第二章 相關(guān)知識(shí)
    2.1 字符串比對(duì)的動(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)比對(duì)算法的特點(diǎn)分析
        2.5.2 比對(duì)中現(xiàn)存的其它問(wèn)題
第三章 面向超長(zhǎng)序列的比對(duì)算法
    3.1 超長(zhǎng)序列比對(duì)問(wèn)題的背景
        3.1.1 序列比對(duì)中存在的問(wèn)題
        3.1.2 PAAVLS算法的提出
    3.2 超長(zhǎng)序列的比對(duì)算法
        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ù)雜度分析
第四章 針對(duì)超長(zhǎng)Gap的序列比對(duì)算法
    4.1 序列比對(duì)中的超長(zhǎng)gap
        4.1.1 問(wèn)題背景
        4.1.2 SLGAA算法的提出
    4.2 超長(zhǎng)gap序列比對(duì)算法
        4.2.1 基本思路
        4.2.2 算法偽代碼
    4.3 實(shí)驗(yàn)與結(jié)果分析
        4.3.1 SLGAA算法的實(shí)驗(yàn)設(shè)置
        4.3.2 比對(duì)中沒(méi)有超長(zhǎng)gap的結(jié)果分析
        4.3.3 比對(duì)中存在超長(zhǎng)gap的結(jié)果分析
        4.3.4 算法的時(shí)間復(fù)雜度分析
第五章 總結(jié)
    5.1 主要工作與創(chuàng)新點(diǎn)
    5.2 展望
參考文獻(xiàn)
發(fā)表論文和參加科研情況說(shuō)明
致謝


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



本文編號(hào)：3676735