跳到主要內容

臺灣博碩士論文加值系統

(18.97.14.86) 您好!臺灣時間:2025/02/12 22:33
字體大小: 字級放大   字級縮小   預設字形  
回查詢結果 :::

詳目顯示

: 
twitterline
研究生:賴建銘
研究生(外文):Jian-Min Lai
論文名稱:以禁忌搜尋法搜尋最佳演化樹
論文名稱(外文):Tabu Search for Finding Optimal Evolutionary Trees
指導教授:尹邦嚴尹邦嚴引用關係徐熊健徐熊健引用關係
指導教授(外文):作者未提供作者未提供
學位類別:碩士
校院名稱:銘傳大學
系所名稱:資訊管理學系碩士班
學門:電算機學門
學類:電算機一般學類
論文種類:學術論文
論文出版年:2004
畢業學年度:92
語文別:中文
論文頁數:55
中文關鍵詞:最大概率條件禁忌搜尋演算法吝嗇法
外文關鍵詞:Tabu searchMaximum likelihoodParsimony
相關次數:
  • 被引用被引用:2
  • 點閱點閱:602
  • 評分評分:
  • 下載下載:75
  • 收藏至我的研究室書目清單書目收藏:1
  這篇論文當中提出一個以禁忌搜尋演算法(tabu search)來建構最大概率條件(maximum likelihood)的演化樹與吝嗇法(Parsimony)的演化樹。由於以最大概率條件和吝嗇法求取最佳演化樹是NP-hard的問題,因此目前已存在的方法,大都是利用經驗法則(heuristics)來求得區域最佳解。而眾所周知利用次經驗法則(meta-heuristics)所得到的結果,經常會比用經驗法則好很多;所以本篇論文應用次經驗法則中的禁忌搜尋演算法,來求得最大概率條件演化樹和吝嗇法演化樹的近似最佳解。實驗結果顯示,運用禁忌搜尋演算法所求得的演化樹最大概率比目前最廣為使用的演化樹計算程式Phylip,以內定參數所求得的演化樹最大概率還要高,同時也與Phylip用最佳參數所求得的最大概率演化樹和吝嗇法演化樹相差不多,證明我們設計的禁忌搜尋演算法的確可行。
This paper presents a tabu search algorithm for constructing evolutionary trees based on maximum likelihood and parsimony criterion. Since the problem of finding the optimum maximum likelihood and parsimony evolutionary tree has been found to be NP-hard, most existing methods seek for near optimal solution using heuristics. It is well known that the solutions obtained using meta-heuristics usually significantly outperform those obtained using heuristic methods; we therefore apply the tabu search, which is one of the instances of meta-heuristics, to approach the maximum likelihood and parsimony evolutionary tree. The experimental results manifest that the likelihood value of the evolutionary tree derived from the tabu search is higher than that of the tree yielded by default Phylip, which is the most popular freeware to compute evolutionary trees, and is also comparable to that of the tree yielded by Phylip using optimal parameter setting, showing that the proposed method is feasible.
摘    要 i
ABSTRACT ii
目   錄 iv
表目錄 vi
圖目錄 vii
第一章 緒  論 1
第一節  研究背景與動機 1
第二節  研究目的 3
第二章 文獻探討 4
第一節  演化分析(Phylogenetic Analysis) 4
一 何謂演化樹 4
二 演化模式 7
三 建樹演算法 9
第二節  禁忌搜尋法(Tabu search) 17
第參章 研究方法 21
第一節  Phylips建樹法則 21
一 區域重排 22
二 全區域重排 23
第二節  Tabu建樹法則 23
第一節  禁忌搜尋法最佳參數設定 27
一 建樹演算法策略的選用 27
二 禁忌名單大小 29
三 產生鄰居數量 30
四 禁忌移步的次數 31
第二節  禁忌搜尋法與DNAML比較 33
第三節  禁忌搜尋法與DNAPARS比較 36
第四節  各種建構演化樹與TreeBase演化樹比較 39
一 Maximum Likelihood Phylogeny 39
二 Maximum Parsimony Phylogeny 41
第伍章 結論 44


表目錄
表 1 物種與無根樹(Unrooted tree)和有根樹(rooted tree)的可能樹型量 6
表 2 距離矩陣 12
表 3 第一次更新距離矩陣 13
表 4第二次更新距離矩陣 13
表 5 各個版本之ML值與適合度函數計算次數 36
表 6各個版本之字元距離值與適合度函數計算次數 39


圖目錄
圖 1 GenBank資料量的成長曲線 1
圖 2 有根樹(rooted tree)與無根樹(unrooted tree) 5
圖 3 (a)序列相近不一定有共同祖先 (b)序列相近不一定分在同一群 7
圖 4 JC模式 8
圖 5 K2P模式 8
圖 6吝嗇法(Parsimony)範例 10
圖 7 最大概率法建構演化樹 11
圖 8 UPGMA計算出的演化樹 13
圖 9 星狀樹 15
圖 10 新增節點x1 16
圖 11 Neighbor joining計算出的演化樹 16
圖 12 禁忌搜尋法(Tabu search)流程圖 19
圖 13 DNAML執行過程 22
圖 14區域重排 23
圖 15全區域重排 23
圖 16 如何用文字呈現(a)有根樹、(b)無根樹 24
圖 17區域重排及全區域重排 25
圖 18禁忌搜尋法搜尋最大概率演化樹的流程 26
圖 19 建樹策略與ML值關係圖 28
圖 20策略與字元距離值關係圖 29
圖 21禁忌名單長度與ML值關係圖 29
圖 22 禁忌名單長度與字元距離值關係圖 30
圖 23鄰居個數與ML值關係圖 31
圖 24鄰居個數與字元距離值關係圖 31
圖 25 禁忌移步前 144次與ML折線圖 32
圖 26 禁忌移步前 1233次與ML折線圖 32
圖 27 禁忌移步與字元距離值折線圖 33
圖 28 禁忌搜尋法與DNAML兩版本ML值之比較(12物種) 33
圖 29禁忌搜尋法與DNAML兩版本ML值之比較(25物種) 34
圖 30禁忌搜尋法與DNAML兩版本ML值之比較(31物種) 34
圖 31禁忌搜尋法與DNAML兩版本ML值之比較(33物種) 34
圖 32禁忌搜尋法、DNAML初始版與DNAML最佳版之適合度函數計算次數曲線圖 35
圖 33禁忌搜尋法與DNPARS兩版本字元距離值之比較(12物種) 37
圖 34禁忌搜尋法與DNPARS兩版本字元距離值之比較(20物種) 37
圖 35禁忌搜尋法與DNPARS兩版本字元距離值之比較(29物種) 37
圖 36禁忌搜尋法與DNPARS兩版本字元距離值之比較(31物種) 38
圖 37 禁忌搜尋法、DNAPARS初始版與DNAPARS最佳版之適合度函數計算次數曲線圖 38
圖 38 Treebase、ML禁忌搜尋法、DNAML初始版與DNAML最佳版之演化樹(12物種) 40
圖 39 Treebase、ML禁忌搜尋法、DNAML初始版與DNAML最佳版之演化樹(31物種) 40
圖 40 Treebase、ML禁忌搜尋法、DNAML初始版與DNAML最佳版之演化樹(33物種) 41
圖 41 Treebase、Parsimony禁忌搜尋法、DNAPARS初始版與DNAPARS最佳版之演化樹(12物種) 42
圖 42 Treebase、Parsimony禁忌搜尋法、DNAPARS初始版與DNAPARS最佳版之演化樹(20物種) 42
圖 43 Treebase、Parsimony禁忌搜尋法、DNAPARS初始版與DNAPARS最佳版之演化樹(31物種) 43
1.Chia-Tung Lee “Computational Biology CHAPTER 5 The Evolution Trees,” May 31, 2001.
2.Fitch, W. M. “Toward defining the course of evolution: minimum change for a specified tree topology,” Sys. Zool, 20, 1971, 406-416.
3.Felsenstein, J. “Evolutionary trees from DNA sequences: a maximum likelihood approach.” J. Molec. Evolution 17, 1981, 368-376.
4.Fred Glover “Tabu Search: A Tutorial,” The Institute of Management Sciences, July-August 1990, 74-94.
5.Fred Glover, Laguna,Manuel, “Tabu Search”, Kluwer Academic Publishers, Boston, 1997.
6.Hasegawa, M., Kishino, H. & Yano T. “Dating of the human-ape splitting by a molecular clock of mitochondrial DNA,” Journal of Molecular Evolution 21, 1985, 160-174.
7.Hsin-Fu Liu “Phylogenetic Analysis Workshop,” National Health Research Institutes, October 17-18 2002.
8.Jukes, T. & Cantor, C.R., “Evolution of protein molecules. In: Mammaliam Protein Metabolism, ed. Munro, H.N., Academic Press, New Youk, 1969, 21-132.
9.Kimura, M., “A simple method ofr estimating evolutionary rates of base substitutions through comparative studies of nucleotide sequences,” Journal of Molecular Evolution 15, 1980, 111-120.
10.Korbinian Strimmer and David L. Robertson “Inference and Applications of Molecular Phylogenies: An Introductory Guide,” December 5, 2000.

11.Korbinian Sebastian Strimmer “Maximum Likelihood Methods in Molecular Phylogenetics,” Octorber 1997.
12.Korbinian Strimmer and arndt von Haeseler “Nucleotide Substitution Models,” The Phylogenetic Handbook, 2003
13.M. Bonet, M. Stell, T. Warnow and S. Yooseph, “Better Methods for solving Parsimony and Compatibility”, Second Annual International Conference on Computational Molecular Biology, pp.40-49 ,1998.
14.王政光、李慶孝、洪小芳、張弘志、張芸潔、賴志河 譯,Arthur M. Lesk著,生物資訊,九州圖書文物有限公司,民國91年。
15.林仲彥、李士傑、陳淑華、QSB-TW譯,Gynthia Gibas & per Jambeck著,生物資訊學電腦技術,歐萊禮,民國91年。
16.莊英群,應用禁忌搜尋法於混合送收貨之車輛途程問題,逢甲大學工業工程研究所碩士論文,民國92年。
QRCODE
 
 
 
 
 
                                                                                                                                                                                                                                                                                                                                                                                                               
第一頁 上一頁 下一頁 最後一頁 top