本文關(guān)鍵詞：基于模擬退火算法的兩物種小系統(tǒng)發(fā)育問題算法研究

  更多相關(guān)文章： 兩物種小系統(tǒng)發(fā)育問題 復(fù)制 丟失 倒位 模擬退火算法 鄰域函數(shù)

【摘要】：隨著分子生物學(xué)和高通量基因測(cè)序技術(shù)的飛速發(fā)展,大量的DNA序列數(shù)據(jù)已被測(cè)定,這為研究基因家族分子進(jìn)化提供了必要的前提條件。根據(jù)現(xiàn)有生物基因重建基因家族進(jìn)化史可以推斷出一個(gè)可靠的系統(tǒng)發(fā)生,這對(duì)揭示有關(guān)基因家族進(jìn)化過程具有重要意義。重建基因家族進(jìn)化史不僅有助于我們更好的研究生物進(jìn)化的進(jìn)化機(jī)制和歷史,而且還可以幫助我們揭示顯性的基因組學(xué)基礎(chǔ)、研究基因的功能。近年來,重建基因家族進(jìn)化史受到國(guó)內(nèi)外眾多學(xué)者的關(guān)注和研究,已經(jīng)成為了比較基因組學(xué)中一個(gè)重要的研究方向。本文主要針對(duì)兩物種小系統(tǒng)發(fā)育問題進(jìn)行研究,并基于模擬退火算法提出求解該問題的SA2SP算法和multiSA2SP算法。具體工作如下：針對(duì)復(fù)制-丟失比對(duì)問題模型,對(duì)兩物種小系統(tǒng)發(fā)育問題的算法進(jìn)行研究,并提出解決該問題的模擬退火算法SA2SP。首先,算法SA2SP包含比對(duì)算法ALING,該算法通過對(duì)給定的兩條基因序列有針對(duì)性的插入一定數(shù)量的字符‘-’,以獲得使兩條基因序列上基因最大匹配的一個(gè)序列比對(duì)。其次,對(duì)于給定的一個(gè)序列比對(duì),算法SA2SP包括一種標(biāo)記算法LABLE,該算法利用復(fù)制-丟失操作序列標(biāo)記給定的序列比對(duì),其最終問題解為對(duì)應(yīng)標(biāo)記代價(jià)最小的比對(duì)基因組。算法SA2SP利用ALIGN算法產(chǎn)生問題初始解,利用LABLE算法來衡量解的優(yōu)劣,并在保持鄰域解多樣性的前提下,引入基因塊智能移動(dòng)、相鄰基因塊位置互換和重新匹配基因塊3種智能鄰域算子,以產(chǎn)生當(dāng)前解較好的鄰域解,提高算法尋找問題最優(yōu)解的能力。通過對(duì)算法SA2SP與算法PBLP用4種菌屬的真實(shí)RNA基因數(shù)據(jù)對(duì)進(jìn)化代價(jià)與時(shí)間性能測(cè)試,實(shí)驗(yàn)結(jié)果表明,算法SA2SP能夠獲得較PBLP算法更小的進(jìn)化代價(jià),且其運(yùn)行時(shí)間在實(shí)際應(yīng)用中是可行的,是求解兩物種小系統(tǒng)發(fā)育問題的一種有效方法。進(jìn)一步,對(duì)僅考慮復(fù)制、丟失操作的復(fù)制-丟失比對(duì)問題模型進(jìn)行研究,新添加倒位(Inversion)操作,提出復(fù)制-丟失-倒位比對(duì)問題模型,并提出求解該模型下兩物種小系統(tǒng)發(fā)育問題的求解算法multiSA2SP。首先,提出基于動(dòng)態(tài)規(guī)劃求解最長(zhǎng)公共子串問題的比對(duì)算法multiALING,通過在兩條基因序列中不匹配位置插入字符‘-’,以得到兩條基因序列的一個(gè)序列比對(duì)。其次,對(duì)于給定的一個(gè)序列比對(duì),本文提出一種標(biāo)記算法multiLABLE,該算法利用復(fù)制-丟失-倒位操作序列標(biāo)記給定的序列比對(duì),并獲得對(duì)應(yīng)標(biāo)記進(jìn)化代價(jià)較小的操作序列。論文基于提出的multiALING算法和multiLABLE算法,設(shè)計(jì)了一種求解復(fù)制-丟失-倒位演化模型下兩物種小系統(tǒng)發(fā)育問題的模擬退火算法multiSA2SP。算法multiSA2SP通過multiALIGN產(chǎn)生初始解,利用multiLABLE來衡量產(chǎn)生鄰域解的優(yōu)劣,根據(jù)鄰域解進(jìn)化代價(jià)作為是否替換當(dāng)前解為新解的重要依據(jù)。同時(shí)還引入基因塊智能移動(dòng)、相鄰基因塊位置互換、重新匹配基因塊和倒位基因塊智能組合4種智能鄰域算子,以產(chǎn)生當(dāng)前解較好的鄰域解,提高算法尋找問題最優(yōu)解的能力。算法multiSA2SP在僅考慮復(fù)制、丟失操作的前提下,利用4種真實(shí)菌屬的RNA基因數(shù)據(jù)對(duì)算法進(jìn)化代價(jià)和運(yùn)行時(shí)間性能進(jìn)行測(cè)試,實(shí)驗(yàn)結(jié)果表明,算法multiSA2SP在僅考慮考慮復(fù)制、丟失操作的情況下,能夠獲得較PBLP算法更小的進(jìn)化代價(jià),是求解復(fù)制-丟失-倒位模型下兩物種小系統(tǒng)發(fā)育問題的一種有效方法。綜上所述,針對(duì)兩物種小系統(tǒng)發(fā)育問題,本文提出了求解復(fù)制-丟失比對(duì)問題模型下該問題的模擬退火算法SA2SP,并獲得了較好的優(yōu)化效果。此外,本文對(duì)復(fù)制-丟失比對(duì)問題模型進(jìn)行擴(kuò)展,不僅提出了復(fù)制-丟失-倒位比對(duì)問題模型,而且還提出了求解該問題的模擬退火算法multiSA2SP,同樣獲得了較好的優(yōu)化效果。由此可見,本文為解決小系統(tǒng)發(fā)育問題提供了兩種較優(yōu)的求解方法。
【關(guān)鍵詞】：兩物種小系統(tǒng)發(fā)育問題 復(fù)制 丟失 倒位 模擬退火算法 鄰域函數(shù)
【學(xué)位授予單位】：廣西師范大學(xué)
【學(xué)位級(jí)別】：碩士
【學(xué)位授予年份】：2016
【分類號(hào)】：Q811.4;TP18
【目錄】：

• 中文摘要3-5
• ABSTRACT5-9
• 第1章 緒論9-16
• 1.1 研究背景及意義9
• 1.2 遺傳學(xué)的相關(guān)概念9-12
• 1.2.1 染色體10
• 1.2.2 DNA和RNA10-11
• 1.2.3 遺傳物質(zhì)11-12
• 1.3 系統(tǒng)發(fā)育問題12-14
• 1.3.1 系統(tǒng)發(fā)育問題概述12
• 1.3.2 系統(tǒng)發(fā)育問題分類12
• 1.3.3 研究現(xiàn)狀12-14
• 1.4 論文主要研究?jī)?nèi)容14-15
• 1.5 論文結(jié)構(gòu)安排15-16
• 第2章 模擬退火算法基本原理16-19
• 2.1 模擬退火算法基本原理16-17
• 2.1.1 模擬退火算法的思想16
• 2.1.2 模擬退火算法的描述16
• 2.1.3 模擬退算法的核心技術(shù)16-17
• 2.2 模擬退火算法的結(jié)構(gòu)17-19
• 第3章 SA2SP：求解DLA模型的模擬退火算法19-34
• 3.1 問題以及符號(hào)定義19-20
• 3.2 復(fù)制-丟失進(jìn)化模型：DLA20-21
• 3.3 問題求解方法21-28
• 3.3.1 ALIGN算法21-23
• 3.3.2 LABLE算法23-25
• 3.3.3 模擬退火算法SA2SP25-28
• 3.4 實(shí)驗(yàn)結(jié)果28-33
• 3.4.1 實(shí)驗(yàn)數(shù)據(jù)29-30
• 3.4.2 性能評(píng)價(jià)30-33
• 3.5 本章小結(jié)33-34
• 第4章 MULTISA2SP：求解DLIA模型的模擬退火算法34-46
• 4.1 復(fù)制-丟失-倒位進(jìn)化模型：DLIA34-35
• 4.2 問題求解方法35-41
• 4.2.1 multiALIGN比對(duì)算法35-38
• 4.2.2 multiLABLE算法38-40
• 4.2.3 模擬退火算法multiSA2SP40-41
• 4.3 實(shí)驗(yàn)結(jié)果41-45
• 4.3.1 性能評(píng)價(jià)42-45
• 4.4 本章小結(jié)45-46
• 第5章 結(jié)束語46-47
• 5.1 總結(jié)46
• 5.2 展望46-47
• 參考文獻(xiàn)47-49
• 攻讀碩士期間發(fā)表論文49-50
• 致謝50-51

【相似文獻(xiàn)】

中國(guó)期刊全文數(shù)據(jù)庫(kù) 前10條

1 王曉東;解非線性0-1規(guī)劃的一個(gè)算法及其在結(jié)構(gòu)優(yōu)化中的應(yīng)用[J];數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用;1988年01期

2 張曉;;基于密度聚類算法的異常檢測(cè)[J];伊犁師范學(xué)院學(xué)報(bào)(自然科學(xué)版);2010年04期

3 陳沐天;找周期子字的算法[J];應(yīng)用數(shù)學(xué)學(xué)報(bào);1991年01期

4 丁才昌;方勃;魯小平;;分布估計(jì)算法及其性能研究[J];武漢大學(xué)學(xué)報(bào)(理學(xué)版);2005年S2期

5 石明蘭;楊暉;葉東毅;;面向目標(biāo)的關(guān)聯(lián)規(guī)則挖掘的一個(gè)FP增長(zhǎng)算法[J];集美大學(xué)學(xué)報(bào)(自然科學(xué)版);2006年02期

6 張維群;;基于海量數(shù)據(jù)關(guān)聯(lián)效應(yīng)測(cè)度算法的設(shè)計(jì)[J];統(tǒng)計(jì)與信息論壇;2012年07期

7 羅蕾,徐洪利;構(gòu)造Dn-最優(yōu)確切設(shè)計(jì)的優(yōu)化方法──離散算法[J];遼寧大學(xué)學(xué)報(bào)(自然科學(xué)版);1999年02期

8 賀永恒;王斌;;基于蟻群算法的候選標(biāo)簽子集構(gòu)造方法研究[J];中國(guó)科技信息;2014年06期

9 武小悅,沙基昌;構(gòu)造網(wǎng)絡(luò)不交化最小路集的一種新算法[J];系統(tǒng)工程理論與實(shí)踐;2000年01期

10 姜建國(guó);劉永青;劉夢(mèng)楠;王國(guó)林;李f ;;類電磁機(jī)制算法研究與改進(jìn)[J];計(jì)算力學(xué)學(xué)報(bào);2014年01期

中國(guó)重要會(huì)議論文全文數(shù)據(jù)庫(kù) 前2條

1 潘志明;鄭駿;錢衛(wèi)寧;周傲英;;構(gòu)造XML相似相關(guān)結(jié)構(gòu)庫(kù)的一種有效方法[A];第二十屆全國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集（技術(shù)報(bào)告篇）[C];2003年

2 林景亮;董槐林;姜青山;吳書;;一種基于新增閾值的頻繁模式挖掘算法[A];第二十三屆中國(guó)數(shù)據(jù)庫(kù)學(xué)術(shù)會(huì)議論文集（研究報(bào)告篇）[C];2006年

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

1 張磊;基于概念格的角色工程相關(guān)算法研究[D];哈爾濱工業(yè)大學(xué);2015年

2 孟靜;新型Krylov子空間算法及其應(yīng)用研究[D];電子科技大學(xué);2015年

3 胡芳;復(fù)雜網(wǎng)絡(luò)節(jié)點(diǎn)中心性多元評(píng)估與社團(tuán)探測(cè)新算法研究[D];華中師范大學(xué);2015年

4 唐益明;（1，，2，2）型異蘊(yùn)涵泛三I算法及其應(yīng)用研究[D];合肥工業(yè)大學(xué);2011年

5 牛云云;求解計(jì)算困難問題的膜計(jì)算模型與算法研究[D];華中科技大學(xué);2012年

6 李冬冬;基因組序列標(biāo)注的算法與理論研究[D];國(guó)防科學(xué)技術(shù)大學(xué);2004年

7 周琨;航空公司航班運(yùn)行調(diào)度模型與算法研究[D];南京航空航天大學(xué);2012年

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

1 彭輝輝;基于壓縮感知的心電信號(hào)壓縮算法研究[D];東南大學(xué);2015年

2 葛娜;高效用項(xiàng)集動(dòng)態(tài)挖掘算法的研究[D];中北大學(xué);2016年

3 葉馨;閉項(xiàng)集挖掘算法在醫(yī)保目錄制定問題上的研究與應(yīng)用[D];中國(guó)科學(xué)技術(shù)大學(xué);2016年

4 張靚云;面向微博的事件摘要生成算法研究與實(shí)現(xiàn)[D];西南交通大學(xué);2016年

5 朱睿;連續(xù)變量量子密鑰分發(fā)誤碼協(xié)商算法研究[D];哈爾濱工業(yè)大學(xué);2016年

6 徐猛;基于關(guān)聯(lián)性挖掘的流形對(duì)齊算法研究[D];華僑大學(xué);2016年

7 李昊;基于改進(jìn)蟻群算法的無線傳感器網(wǎng)絡(luò)路由的研究[D];東北林業(yè)大學(xué);2016年

8 李先成;基于模擬退火算法的兩物種小系統(tǒng)發(fā)育問題算法研究[D];廣西師范大學(xué);2016年

9 陳紅強(qiáng);大規(guī)模并行排序?qū)W習(xí)算法研究[D];西安電子科技大學(xué);2014年

10 白鷺;基于自適應(yīng)人工免疫進(jìn)化的網(wǎng)格聚類算法研究[D];沈陽大學(xué);2010年

本文編號(hào)：1004893