本文關鍵詞：樣本斷點距離問題的算法與復雜性研究，由筆耕文化傳播整理發(fā)布。

【摘要】：隨著生物技術的發(fā)展和計算機科技的進步,生物信息學這個生物和計算機的交叉學科越來越引起人們的注意。生物信息學可以理解成計算機技術在生物上的應用。比較基因組學是生物信息學中的一個重要研究領域。自從九十年代末期,比較基因組學開始逐步興起,迄今已經走過將近二十年的歷程。比較基因組學傳統(tǒng)的研究假設是兩條基因組不包含重復基因,這種假設在部分病毒和線粒體的基因組中是成立的,但是對于哺乳動物和植物等,這種假設是不滿足的。據估計人類的基因組中有15%的基因是含有重復的[49]。樣本斷點距離問題的研究就是在基因組包含重復的假設下進行的。尋找兩條基因組之間的保留基因集合是基因組比較中的一個基本問題。在基因組中以相同順序保存的一組基因暗示它們參與相同的生物過程。為了尋找基因組中保留基因集合,人們提出許多相似性度量,例如,斷點數目,鄰接數目,保留區(qū)間數目和公共區(qū)間數目。當基因組不包含重復基因時,所有這些距離都能很好定義。然而,基因復制是基因組進化的主要驅動力之一,并且頻繁發(fā)生(Dennis等,2012)。當復制發(fā)生時,一個基因可能出現在一條基因組中的幾個不同地方。樣本斷點距離問題是受尋找兩條基因組之間保留基因集合啟發(fā)提出的一個問題。它詢問尋找兩條基因組各自的樣本,以滿足樣本之間的斷點距離最小。如果一條基因組沒有重復基因(稱為平凡基因組)并且另一條基因組的每個基因至多出現兩次,它被稱為(1,2)-樣本斷點距離問題,簡稱為EBD(1,2)。雖然EBD(1,2),作為最基本的樣本斷點距離問題,已知為APX-Hard多年,但在算法設計方面卻做得很少。事實上,EBD(1,2)是否存在固定參數算法直到現在都是未知的。Zhu(2009)指出如果參數是樣本斷點距離,EBD(2,2)不存在任何固定參數算法[34]。這讓EBD(1,2)是否存在基于某個參數的固定參數算法變得更加有趣。針對EBD(1,2)的固定參數算法,本文重點進行了以下研究工作：(1)我們利用非平凡基因組的跨度(span),記為s,作為參數,設計EBD(1,2)的第一個固定參數算法,其中引入基因組的跨度(span)這個概念來表示基因組中同一基因家族的兩個基因橫跨的最多基因數目。這取決于一個實際觀察,這個觀察是在一條基因組中同一基因家族的兩個基因通常被少量基因所分隔(Shi等,2010)[31]。對于一個每條基因組包含n個基因家族的EBD(1,2)實例,我們的算法可以在O(4Sn2)時間內和O(4Sn)空間內運行。這在之前是未見的。(2)我們用C++語言實現了上述算法。在隨機產生數據上的仿真表明,當基因組的跨度為10,我們的算法總是可以在1000秒內處理包含5000個基因家族的基因組,并且當基因組的跨度為15,我們的算法可以在1600秒內處理包含1000個基因家族的基因組。我們算法的軟件包可以在如下網址獲取：http://www.cs.sdu.edu.cn/dmzhu/exemplar-distance/software.html基于串聯質譜的肽從頭測序問題是本文作者的早期研究問題。基于串聯質譜的肽從頭測序問題是蛋白質組學領域中蛋白質識別最常用的方法之一,它在沒有蛋白質數據庫輔助的情況下,直接由未知肽P的串聯質譜識別出其氨基酸序列。肽從頭測序一般將未知肽P的串聯質譜轉換為一個質譜圖G,通過在圖G中尋找合適路徑的方法來識別出未知肽P的氨基酸序列。圖G中的一條路徑代表一條可能的肽,我們希望找出與未知肽P盡可能相似的一條或多條肽。在質譜圖G的構造過程中,由于不知道串聯質譜中的每個峰值p對應的是未知肽P的前端子序列,還是后端子序列,因此在質譜圖G中,每個峰值p用兩個頂點v和v表示。其中、,表示峰值p對應的是前端子序列,v表示峰值p對應的是后端子序列,但用未知肽P減去后端子序列,我們得到前端子序列。這樣,對于每個峰值p,不管它是前端子序列,還是后端子序列,我們總是可以在質譜圖G中用一個頂點來表示這個峰值p對應的未知肽P的前端子序列。因為圖中的每個頂點表示未知肽P的某個前端子序列,如果任意兩個頂點對應質量值相減等于一個或幾個氨基酸的質量值,表示這兩個前端子序列相差一個或幾個氨基酸。Dancik等[39]為質譜圖G設計了一種加權算法,并通過在加權質譜圖中尋找最長路徑的方法來得到與未知肽P最相似的肽。但他們注意到同時經過v和v的最長路徑是毫無意義的。因為一個峰值p不可能既是未知肽P的前端子序列又是后端子序列。這樣問題轉化為尋找不能同時經過一些頂點對的最長路徑問題。稱不能同時經過的頂點對為禁止頂點對。因為避免禁止頂點對的路徑問題是NP-Hard的,所以避免禁止頂點對的最長路徑問題也是NP-Hard的。Dancik等和Chen等又注意到因為每個頂點都對應一個質量值,實際上頂點是有序的,可以將它們從左向右畫在數軸上,對于任意兩對禁止頂點對(v1,v1)和(v,v2),(v1,v1)對應的區(qū)間段和(v2,v2)對應的區(qū)間段是嵌套的。針對基于串聯質譜的肽從頭測序問題,本文重點進行了以下研究工作：(1)基于串聯質譜的肽從頭測序問題可以轉化為避免禁止頂點對的最長路徑問題(PAFP)。一般的PAFP問題是NP-Hard的。但是從肽從頭測序到PAFP問題的轉化過程中,禁止頂點對具有嵌套結構�；诮鬼旤c對的嵌套結構,我們給出求解肽從頭測序問題的一種頂點收縮算法。頂點收縮算法是一種多項式時間算法,其時間復雜度為D(|V|3)。
【關鍵詞】：樣本 斷點 基因組 跨度 肽從頭測序 禁止頂點對 嵌套結構 頂點收縮 算法
【學位授予單位】：山東大學
【學位級別】：博士
【學位授予年份】：2015
【分類號】：Q78;TP301.6
【目錄】：

• 摘要11-14
• ABSTRACT14-17
• 第1章 緒論17-30
• 1.1 研究背景及意義17-20
• 1.1.1 研究背景18-19
• 1.1.2 研究意義19-20
• 1.2 研究現狀20-24
• 1.2.1 樣本斷點距離問題20-22
• 1.2.2 肽從頭測序問題22-24
• 1.3 算法基本知識24-27
• 1.3.1 算法與計算復雜性24-26
• 1.3.2 動態(tài)規(guī)劃算法26-27
• 1.3.3 參數化算法27
• 1.4 本文主要工作和創(chuàng)新點27-28
• 1.5 各章節(jié)安排28-30
• 第2章 樣本斷點距離的復雜性30-43
• 2.1 引言30
• 2.2 (1,2)-樣本斷點距離是NP-Hard的30-34
• 2.2.1 預備知識31-32
• 2.2.2 樣本斷點距離是NP-Hard的32-34
• 2.3 (1,2)-樣本斷點距離是APX-Hard的34-40
• 2.3.1 預備知識34-36
• 2.3.2 樣本斷點距離是APX-Hard的36-40
• 2.4 樣本斷點距離不存在近似算法和參數算法40-42
• 2.4.1 樣本斷點距離不存在近似算法40-41
• 2.4.2 樣本斷點距離不存在參數算法41-42
• 2.5 本章小結42-43
• 第3章 (1,2)-樣本斷點距離的動態(tài)規(guī)劃算法43-59
• 3.1 引言43-45
• 3.2 預備知識45-47
• 3.3 動態(tài)規(guī)劃算法47-54
• 3.3.1 尋找最小樣本的動態(tài)規(guī)劃算法47-51
• 3.3.2 算法的復雜性51-54
• 3.4 仿真實驗54-58
• 3.4.1 產生隨機數據54-55
• 3.4.2 仿真55-58
• 3.5 本章小結58-59
• 第4章 基于串聯質譜的肽從頭測序59-68
• 4.1 引言59-63
• 4.2 質譜圖的構造63-65
• 4.2.1 頂點的構造63-64
• 4.2.2 邊的構造64-65
• 4.2.3 加權函數的構造65
• 4.3 禁止頂點對的結構65-67
• 4.3.1 分半結構66
• 4.3.2 層次結構66-67
• 4.3.3 嵌套結構67
• 4.4 本章小結67-68
• 第5章 肽從頭測序的頂點收縮算法68-81
• 5.1 引言68-71
• 5.2 層次結構的頂點收縮算法71-75
• 5.2.1 層次結構的收縮算法71-72
• 5.2.2 層次結構的算法示例72-75
• 5.3 嵌套結構的頂點收縮算法75-79
• 5.3.1 嵌套結構的收縮算法75-77
• 5.3.2 嵌套結構的算法示例77-79
• 5.4 本章小結79-81
• 第6章 總結與展望81-83
• 6.1 本文總結81
• 6.2 研究展望81-83
• 參考文獻83-88
• 致謝88-89
• 攻讀學位期間發(fā)表的學術論文89-90
• 在讀期間參與科研項目情況90-91
• 外文論文91-117
• 學位論文評閱及答辨情況表117

【相似文獻】

中國期刊全文數據庫 前10條

1 胡洪林;;截斷思想在算法分析中的應用[J];科技風;2012年12期

2 陳際平;算法分析與優(yōu)化程序的研究[J];西北大學學報(自然科學版);1994年05期

3 梁彥杰;徐堅;;算法分析中概率變化與圖形生成[J];云南大學學報(自然科學版);2009年S2期

4 劉寧;邵曉艷;;算法分析與設計課程中多媒體技術的應用[J];科技風;2009年18期

5 海亞;張永平;;算法對學生解決問題能力的培養(yǎng)[J];黑龍江科技信息;2008年10期

6 李冰穎,夏利民,舒遠仲;學分制模式下網上選課系統(tǒng)的算法探析[J];江西科學;2004年05期

7 Anany Levitin;Maria Levitin;;算法謎題[J];中國科技信息;2014年08期

8 杜剛;陸黎明;;一修路問題的算法解決分析[J];太原師范學院學報(自然科學版);2006年02期

9 許之民;;砝碼稱重問題的多種算法分析與探究[J];合肥學院學報(自然科學版);2011年01期

10 李亞楠;;菌群優(yōu)化算法分析[J];貴州大學學報(自然科學版);2011年02期

中國重要會議論文全文數據庫 前10條

1 俞洋;田亞菲;;一種新的變步長LMS算法及其仿真[A];通信理論與信號處理新進展——2005年通信理論與信號處理年會論文集[C];2005年

2 周顥;劉振華;趙保華;;構造型的D~2FA生成算法[A];中國通信學會通信軟件技術委員會2009年學術會議論文集[C];2009年

3 賴桃桃;馮少榮;張東站;;一種基于劃分和密度的快速聚類算法[A];第二十五屆中國數據庫學術會議論文集（一）[C];2008年

4 劉遠新;鄧飛其;羅艷輝;舒添慧;;ERP柔性平臺下物流運輸配送系統(tǒng)算法分析[A];第二十六屆中國控制會議論文集[C];2007年

5 王樹西;白碩;姜吉發(fā);;模式合一的“減首去尾”算法[A];第二屆全國學生計算語言學研討會論文集[C];2004年

6 王萬青;張曉輝;;改進的A~*算法的高效實現[A];2009全國測繪科技信息交流會暨首屆測繪博客征文頒獎論文集[C];2009年

7 孫煥良;邱菲;劉俊嶺;朱葉麗;;IncSNN——一種基于密度的增量聚類算法[A];第二十三屆中國數據庫學術會議論文集（研究報告篇）[C];2006年

8 韓建民;岑婷婷;于娟;;實現敏感屬性l-多樣性的l-MDAV算法[A];第二十七屆中國控制會議論文集[C];2008年

9 張悅;尤楓;趙瑞蓮;;利用蟻群算法實現基于程序結構的主變元分析[A];第五屆中國測試學術會議論文集[C];2008年

10 王旭東;劉渝;鄧振淼;;正弦波頻率估計的修正Rife算法及其FPGA實現[A];全國第十屆信號與信息處理、第四屆DSP應用技術聯合學術會議論文集[C];2006年

中國重要報紙全文數據庫 前1條

1 科文;VIXD算法分析Web異常[N];中國計算機報;2008年

中國博士學位論文全文數據庫 前10條

1 魏哲學;樣本斷點距離問題的算法與復雜性研究[D];山東大學;2015年

2 劉春明;基于增強學習和車輛動力學的高速公路自主駕駛研究[D];國防科學技術大學;2014年

3 劉新旺;多核學習算法研究[D];國防科學技術大學;2013年

4 于濱;城市公交系統(tǒng)模型與算法研究[D];大連理工大學;2006年

5 曾國強;改進的極值優(yōu)化算法及其在組合優(yōu)化問題中的應用研究[D];浙江大學;2011年

6 肖永豪;蜂群算法及在圖像處理中的應用研究[D];華南理工大學;2011年

7 陳耿;面向中觀審計的規(guī)則發(fā)現算法研究[D];東南大學;2005年

8 王維博;粒子群優(yōu)化算法研究及其應用[D];西南交通大學;2012年

9 魚亮;蛋白質網絡模塊結構識別算法研究[D];西安電子科技大學;2011年

10 李玉英;混沌螞蟻群優(yōu)化算法及其應用研究[D];北京郵電大學;2009年

中國碩士學位論文全文數據庫 前10條

1 黃廈;基于改進蟻群算法的柔性作業(yè)車間調度問題研究[D];昆明理工大學;2015年

2 李平;基于Hadoop的信息爬取與輿情檢測算法研究[D];昆明理工大學;2015年

3 趙官寶;基于位表的關聯規(guī)則挖掘算法研究[D];昆明理工大學;2015年

4 殷文華;移動容遲網絡中基于社會感知的多播分發(fā)算法研究[D];內蒙古大學;2015年

5 徐翔燕;人工魚群優(yōu)化算法及其應用研究[D];西南交通大學;2015年

6 李德福;基于小世界模型的啟發(fā)式尋路算法研究[D];華中師范大學;2015年

7 鄭海彬;一種面向MAPREDUCE的DATASHUFFLE的優(yōu)化方法[D];蘇州大學;2015年

8 趙曉寒;輪換步長PSO算法及SMVSC參數優(yōu)化[D];沈陽理工大學;2015年

9 安豐洋;基于無線網絡的廣播算法研究[D];曲阜師范大學;2015年

10 李智明;基于改進FastICA算法的混合語音盲分離[D];上海交通大學;2015年

  本文關鍵詞：樣本斷點距離問題的算法與復雜性研究，，由筆耕文化傳播整理發(fā)布。

本文編號：399348