一個解決基因複製問題的線性時間啟發式演算法

Abstract

在種系發生學(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.