請用此 Handle URI 來引用此文件:
http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/44187
標題: | 一個解決基因複製問題的線性時間啟發式演算法 A Linear-time Heuristic for The Gene Duplication Problem Based on NNI Local Searches |
作者: | Meng-Han Li 李孟韓 |
指導教授: | 趙坤茂(Kun-Mao Chao) |
關鍵字: | 演化樹,基因樹,最近鄰居交換,基因複製架構,基因流失, Phylogenetic Tree,Gene Tree,Nearest Neighbor Interchange,Gene Duplication Model,Gene Loss, |
出版年 : | 2009 |
學位: | 碩士 |
摘要: | 在種系發生學(Phylogeny)上,我們發現基因樹(Gene Tree)和演化樹
(Phylogenetic Tree)上的不一致,是可能起源於基因流失(Gene Loss)、基因重組(Gene Recombination)、或基因複製(Gene Duplication)。在此情況下,我們希望利用基因複製架構(Gene Duplication Model),從一群基因樹和一棵演化樹中找出一棵超級樹(Supertree)來表示最有可能演化樹的真正構造。主要計算此超級樹的難處在於基因樹的資料量太大,電腦在計算能力上無法更有效率的找到最適合的超級樹。因此在此篇研究中,我們提出了一個利用最近鄰居交換(Nearest Neighbor Interchange)區域搜尋方法的線性時間啟發式演算法,在現性時間中找到這棵能表現基因樹和演化樹一致性的超級樹。 Contradictory phylogenies may result from several effects, such as gene loss, recombination, and duplication. The gene duplication problem is to deduce a most likely phylogenetic supertree from a large set of gene trees with gene duplication information. This problem has been proved to be NP-complete, and more efficient heuristics are required to deal with large-scale phylogenetic analysis. A naive heuristic which performs a step-by-step search on the tree and recalculate the reconciliation cost on each node is extremely time consuming and requiring enormous computational power. The k-NNI search problem, based on at most k times nearest neighbor interchange operations, has been largely put into use for solving the gene duplication problem. In this work, we provide a linear-time solution for the 1-NNI local search problem and an O(p(r + log n))-time heuristic based on 1-NNI local search problem, where p denotes the number of iterations. The result of this work provides a feasible approach for the vast phylogenetic data analysis. |
URI: | http://tdr.lib.ntu.edu.tw/jspui/handle/123456789/44187 |
全文授權: | 有償授權 |
顯示於系所單位: | 資訊工程學系 |
文件中的檔案:
檔案 | 大小 | 格式 | |
---|---|---|---|
ntu-98-1.pdf 目前未授權公開取用 | 535.59 kB | Adobe PDF |
系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。