A Novel Algorithm for Duplication-Loss Problem Based on NNI Local Search
Hui Wang, Daming Zhu
Available Online December 2013.
- https://doi.org/10.2991/wiet-13.2013.1How to use a DOI?
- Computational phylogenetics; Duplication-Loss; NNI; Local search; Computational complexity; Algorithm
- The duplication-loss problem is to infer a species supertree from a collection of gene trees that are confounded by complex histories of gene duplication and loss events. The decision variant of this problem is NP-complete. The utility of this NP-hard problem for large-scale phylogenetic analyses has been largely limited by the high time complexity of existing heuristics. These heuristics aimed at solving it perform a stepwise search of all possible supertrees, where each step is guided by an exact solution to an instance of a local search problem. A classical local search problem is the NNI local search problem, which is based on the nearest neighbor interchange operation. In this paper, we extend the NNI neighborhood to the k-NNI neighborhood, and provide a novel algorithm for the k-NNI search problem. The algorithm not only significantly enlarges the search space of the NNI search problem but also improves the running time of the solution to the NNI local search problem. Hence, our improvement makes the duplication-loss problem much more tractable for large-scale phylogenetic analyses.
- Open Access
- This is an open access article distributed under the CC BY-NC license.
Cite this article
TY - CONF AU - Hui Wang AU - Daming Zhu PY - 2013/12 DA - 2013/12 TI - A Novel Algorithm for Duplication-Loss Problem Based on NNI Local Search BT - AASRI Winter International Conference on Engineering and Technology (AASRI-WIET 2013) PB - Atlantis Press SN - 1951-6851 UR - https://doi.org/10.2991/wiet-13.2013.1 DO - https://doi.org/10.2991/wiet-13.2013.1 ID - Wang2013/12 ER -