A Linear-time Heuristic for The Gene Duplication Problem Based on NNI Local Searches
Date Issued
2009
Date
2009
Author(s)
Li, Meng-Han
Abstract
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.
Subjects
Phylogenetic Tree
Gene Tree
Nearest Neighbor Interchange
Gene Duplication Model
Gene Loss
Type
thesis
File(s)![Thumbnail Image]()
Loading...
Name
ntu-98-R95922036-1.pdf
Size
23.32 KB
Format
Adobe PDF
Checksum
(MD5):6bb62e1f6cbf0a9889107e6d2f2feb3f