請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/10642
標題: | 在基因複製模型下之多重基因複製與親緣樹建立相關的最佳化問題 Some Optimization Problems Related to Multiple Gene Duplications and Phylogenetic Tree Construction under the Gene Duplication Model |
作者: | Cheng-Wei Luo 羅正偉 |
指導教授: | 趙坤茂(Kun-Mao Chao) |
關鍵字: | 基因複製,親緣樹,基因複製模型, Gene duplication,phylogenetic tree,gene duplication model, |
出版年 : | 2010 |
學位: | 博士 |
摘要: | 本論文探討在基因演化模型下之多重基因複製與親緣樹建立相關的最佳化問題。針對多重基因複製,我們探討了事件叢集問題 (Episode-Clustering Problem)與最小事件問題 (Minimum Episodes Problem)。對於事件叢集問題,我們將Burleigh等人的結果改進到最佳的線性時間演算法;而對於最小事件問題,以Bansal與Eulenstein所提出的演算法為基礎下,我們也提出了最佳的線性時間演算法。針對親緣樹的建立,我們探討了複製–遺失問題 (Duplication-Loss Problem)。由於複製–遺失問題是NP困難,因此在實際應用上都使用啟發式方法來解此問題。標準的啟發式方法是在樹狀空間上反覆執行局部搜尋直到局部最小值被算出。以最近鄰居交換 (NNI) 的局部搜尋為基礎下,本論文探討了複製–遺失問題的啟發式方法,同時也對相應的局部搜尋問題提出了一個線性演算法。 This dissertation studies several optimization problems related to multiple gene duplications and phylogenetic tree construction under the Gene Duplication model. For multiple gene duplications, we study the Episode-Clustering (EC) problem and the Minimum Episodes (ME) problem. For the EC problem, we improve the results of Burleigh et al. with an optimal linear-time algorithm. For the ME problem, on the basis of the algorithm presented by Bansal and Eulenstein, we propose an optimal linear-time algorithm. For the phylogenetic tree construction, we study the Duplication-Loss problem. Since the Duplication-Loss problem is NP-hard, heuristics are developed to solve it in practice. A standard heuristic is to perform the stepwise local search on the tree space until a local minimum is reached. In this dissertation, we study the heuristic for the Duplication-Loss problem based on NNI local searches and propose a linear-time algorithm for the corresponding Local Search problem. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/10642 |
全文授權: | 同意授權(全球公開) |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-99-1.pdf | 584.98 kB | Adobe PDF | 檢視/開啟 |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。