本文關(guān)鍵詞：序列及序列二級(jí)結(jié)構(gòu)聯(lián)配問(wèn)題的若干算法研究，，由筆耕文化傳播整理發(fā)布。

【摘要】：序列聯(lián)配以及序列二級(jí)結(jié)構(gòu)聯(lián)配是生物信息處理中最基本最重要的問(wèn)題。自1970年Needleman和Wunsch提出的經(jīng)典的動(dòng)態(tài)規(guī)劃算法以來(lái),如何獲得結(jié)果準(zhǔn)確,時(shí)間空間效率更高的序列聯(lián)配算法和軟件一直是生物信息學(xué)研究中的一項(xiàng)重要課題�？紤]實(shí)際序列聯(lián)配問(wèn)題中的序列具有較高的相識(shí)度,也就是說(shuō)在最佳聯(lián)配中各個(gè)序列中插入的空格數(shù)將不會(huì)太大,本文將待插入的空格數(shù)上限作為限制來(lái)設(shè)計(jì)序列聯(lián)配算法,從而降低算法的運(yùn)行時(shí)間和空間的復(fù)雜度。Needleman和Wunsch給出的運(yùn)行時(shí)間和空間為O(m?n)的動(dòng)態(tài)規(guī)劃算法至今仍然是最為實(shí)用和有效的雙序列聯(lián)配算法之一,其中m,n為兩條序列的長(zhǎng)度。本文在Needleman和Wunsch的動(dòng)態(tài)規(guī)劃算法的基礎(chǔ)上提出了一種在k插缺數(shù)限制下雙序列聯(lián)配的算法,其運(yùn)行時(shí)間和空間復(fù)雜度都為O k?min?,(m n?)。同時(shí),文中將該思想引入Hirschberg線(xiàn)性空間算法中,給出了一種在k插缺數(shù)限制下的雙序列聯(lián)配線(xiàn)性空間算法,其運(yùn)行時(shí)間仍然為O k?min?,(m n?),但只使用線(xiàn)性的內(nèi)存空間。大量實(shí)際數(shù)據(jù)說(shuō)明一般最佳聯(lián)配下插入空格數(shù)在序列長(zhǎng)度的20%以?xún)?nèi),因此在實(shí)驗(yàn)中,大部分序列將k規(guī)定在序列長(zhǎng)度的20%,新算法可以將運(yùn)行時(shí)間直接減少近50%的情況下仍然保證找到最優(yōu)解,對(duì)于部分相似度高的序列,甚至可以將運(yùn)行時(shí)間直接減少近85%的情況下仍然保證找到最優(yōu)解。接下來(lái),文中將參數(shù)k的思想應(yīng)用到三條序列聯(lián)配算法中,設(shè)計(jì)了在k插缺數(shù)限制下三條序列聯(lián)配的算法,時(shí)間復(fù)雜度和空間復(fù)雜度都為2O(k?n),其中k為參數(shù)表示允許插入的最大空格數(shù),三條序列長(zhǎng)度均為n。在多序列聯(lián)配問(wèn)題中由于序列數(shù)量增加而導(dǎo)致計(jì)算難度陡增,引入?yún)?shù)k的概念也不能獲得實(shí)際有效的算法。因此本文給出一種基于雙序列聯(lián)配的快速多序列聯(lián)配啟發(fā)式算法。然后以BAliBASE數(shù)據(jù)庫(kù)來(lái)測(cè)試與其他算法比較,實(shí)驗(yàn)也驗(yàn)證我們的算法明顯比之前的算法的準(zhǔn)確性更好。對(duì)序列二級(jí)結(jié)構(gòu)聯(lián)配問(wèn)題,文中同樣經(jīng)典的Bafna算法中引入?yún)?shù)k的概念。將原本時(shí)間和空間復(fù)雜度都為3 2 2O(mn?m n)的算法改進(jìn)為時(shí)間和空間復(fù)雜度都為2 2 21 1O(k mn?k n)的算法,其中m、n為兩條序列長(zhǎng)度,1k是序列中允許插入的最大空格數(shù)。最后本文總結(jié)了引入?yún)?shù)k的概念的序列聯(lián)配及序列二級(jí)結(jié)構(gòu)聯(lián)配問(wèn)題的研究結(jié)果,并對(duì)相關(guān)工作的未來(lái)的研究方向做了展望及提出了一些問(wèn)題可能的解決方法。
【關(guān)鍵詞】：序列聯(lián)配 多序列聯(lián)配 動(dòng)態(tài)規(guī)劃 分治算法
【學(xué)位授予單位】：電子科技大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2015
【分類(lèi)號(hào)】：Q811.4;O221.3
【目錄】：

• 摘要5-6
• Abstract6-10
• 第一章 緒論10-16
• 1.1 背景10-12
• 1.2 研究現(xiàn)狀及發(fā)展態(tài)勢(shì)12-15
• 1.3 結(jié)論15
• 1.4 論文組織結(jié)構(gòu)15-16
• 第二章 雙序列聯(lián)配16-34
• 2.1 雙序列聯(lián)研究現(xiàn)狀、定義及基本問(wèn)題16-18
• 2.1.1 雙序列聯(lián)研究現(xiàn)狀16-17
• 2.1.2 雙序列聯(lián)配定義17
• 2.1.3 雙序列聯(lián)配基本問(wèn)題17-18
• 2.2 Needleman和Wunsch的全局聯(lián)配算法18-19
• 2.3 Hirschberg的線(xiàn)性空間算法19-23
• 2.3.1 Hirschberg算法基本思想19-21
• 2.3.2 Hirschberg算法21-23
• 2.4 雙序列仿射空位罰分聯(lián)配算法23-24
• 2.5 在插入空格數(shù)k約束條件下的動(dòng)態(tài)規(guī)劃算法24-26
• 2.5.1 算法思想24-25
• 2.5.2 算法25-26
• 2.6 在插入空格數(shù)k約束條件下的線(xiàn)性空間算法26-28
• 2.7 在插缺數(shù)k限制下的雙序列仿射空位罰分聯(lián)配算法28-29
• 2.8 實(shí)驗(yàn)結(jié)果29-32
• 2.9 本章小結(jié)32-34
• 第三章 三條序列聯(lián)配34-49
• 3.1 三條序列聯(lián)研究現(xiàn)狀、定義及基本問(wèn)題34-36
• 3.1.1 三條序列聯(lián)研究現(xiàn)狀34-35
• 3.1.2 三條序列聯(lián)配定義35
• 3.1.3 三條序列聯(lián)配基本問(wèn)題35-36
• 3.2 三條序列聯(lián)配經(jīng)典動(dòng)態(tài)規(guī)劃算法36-37
• 3.3 三條序列仿射罰分聯(lián)配動(dòng)態(tài)規(guī)劃算法37-39
• 3.4 在插入空格數(shù)k約束條件下的三條序列聯(lián)配動(dòng)態(tài)規(guī)劃算法39-44
• 3.4.1 算法思想39-42
• 3.4.2 算法42-44
• 3.5 在插入空格數(shù)k約束條件下三條序列仿射空位罰分聯(lián)配算法44-47
• 3.6 本章小結(jié)47-49
• 第四章 基于雙序列聯(lián)配的快速多序列聯(lián)配算法研究49-61
• 4.1 多序列聯(lián)配問(wèn)題啟發(fā)式算法研究現(xiàn)狀49-50
• 4.2 基于雙序列聯(lián)配的算法思想50-52
• 4.3 隨機(jī)聯(lián)配算法及結(jié)果52-54
• 4.3.1 隨機(jī)聯(lián)配算法52-53
• 4.3.2 隨機(jī)聯(lián)配結(jié)果53-54
• 4.4 星聯(lián)配算法54-55
• 4.5 一種貪心策略的多序列聯(lián)配算法55-58
• 4.5.1 一種貪心策略的多序列聯(lián)配算法思想56-57
• 4.5.2 一種貪心策略的多序列聯(lián)配算法57-58
• 4.6 實(shí)驗(yàn)結(jié)果58-59
• 4.7 本章小結(jié)59-61
• 第五章 序列二級(jí)結(jié)構(gòu)聯(lián)配61-71
• 5.1 序列二級(jí)結(jié)構(gòu)聯(lián)配研究現(xiàn)狀、定義及基本問(wèn)題61-65
• 5.1.1 序列二級(jí)結(jié)構(gòu)聯(lián)配研究現(xiàn)狀61
• 5.1.2 序列二級(jí)結(jié)構(gòu)聯(lián)配定義61-64
• 5.1.3 序列二級(jí)結(jié)構(gòu)聯(lián)配基本問(wèn)題64-65
• 5.2 序列二級(jí)結(jié)構(gòu)聯(lián)配算法65-67
• 5.3 在約束條件下的序列二級(jí)結(jié)構(gòu)聯(lián)配算法67-70
• 5.4 本章小結(jié)70-71
• 第六章 全文總結(jié)與展望71-74
• 6.1 全文總結(jié)71-73
• 6.2 后續(xù)工作展望73-74
• 致謝74-75
• 參考文獻(xiàn)75-79

【參考文獻(xiàn)】

中國(guó)博士學(xué)位論文全文數(shù)據(jù)庫(kù) 前1條

1 李昭;生物序列相似性比較算法的研究[D];中國(guó)科學(xué)院研究生院（計(jì)算技術(shù)研究所）;2002年

  本文關(guān)鍵詞：序列及序列二級(jí)結(jié)構(gòu)聯(lián)配問(wèn)題的若干算法研究，由筆耕文化傳播整理發(fā)布。

本文編號(hào)：314055