Please use this identifier to cite or link to this item:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/10642
Title: | 在基因複製模型下之多重基因複製與親緣樹建立相關的最佳化問題 Some Optimization Problems Related to Multiple Gene Duplications and Phylogenetic Tree Construction under the Gene Duplication Model |
Authors: | Cheng-Wei Luo 羅正偉 |
Advisor: | 趙坤茂(Kun-Mao Chao) |
Keyword: | 基因複製,親緣樹,基因複製模型, Gene duplication,phylogenetic tree,gene duplication model, |
Publication Year : | 2010 |
Degree: | 博士 |
Abstract: | 本論文探討在基因演化模型下之多重基因複製與親緣樹建立相關的最佳化問題。針對多重基因複製,我們探討了事件叢集問題 (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 |
Fulltext Rights: | 同意授權(全球公開) |
Appears in Collections: | 資訊工程學系 |
Files in This Item:
File | Size | Format | |
---|---|---|---|
ntu-99-1.pdf | 584.98 kB | Adobe PDF | View/Open |
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.