趙坤茂Chao, Kun-Mao臺灣大學:資訊工程學研究所李孟韓Li, Meng-HanMeng-HanLi2010-06-092018-07-052010-06-092018-07-052009U0001-1008200914484300http://ntur.lib.ntu.edu.tw//handle/246246/185382在種系發生學(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 beenroved 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 duplicationroblem. 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 vasthylogenetic data analysis.1 Introduction 1.1 Gene Tree and Species Tree 3.2 Contribution of This Research 4 Preliminaries 6.1 Basic Definitions and Notation 6.2 The Gene Duplication Problem 7.3 The Local Search Problem 8 Structure Properties 10 The Main Algorithm 15.1 Solving the 1-NNI Local Search Problem in Linear Time 15.2 Heuristic Based on 1-NNI 20 Concluding Remarks 24ibliography 25548449 bytesapplication/pdfen-US演化樹基因樹最近鄰居交換基因複製架構基因流失Phylogenetic TreeGene TreeNearest Neighbor InterchangeGene Duplication ModelGene Lossthesishttp://ntur.lib.ntu.edu.tw/bitstream/246246/185382/1/ntu-98-R95922036-1.pdf