Proceedings of the AASRI Winter International Conference on Engineering and Technology (AASRI-WIET 2013)

A Novel Algorithm for Duplication-Loss Problem Based on NNI Local Search

Authors
Hui Wang, Daming Zhu
Corresponding Author
Hui Wang
Available Online December 2013.
DOI
10.2991/wiet-13.2013.1How to use a DOI?
Keywords
Computational phylogenetics; Duplication-Loss; NNI; Local search; Computational complexity; Algorithm
Abstract

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.

Copyright
© 2013, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

Download article (PDF)

Volume Title
Proceedings of the AASRI Winter International Conference on Engineering and Technology (AASRI-WIET 2013)
Series
Advances in Intelligent Systems Research
Publication Date
December 2013
ISBN
978-90786-77-95-6
ISSN
1951-6851
DOI
10.2991/wiet-13.2013.1How to use a DOI?
Copyright
© 2013, the Authors. Published by Atlantis Press.
Open Access
This is an open access article distributed under the CC BY-NC license (http://creativecommons.org/licenses/by-nc/4.0/).

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  - Proceedings of the AASRI Winter International Conference on Engineering and Technology (AASRI-WIET 2013)
PB  - Atlantis Press
SP  - 1
EP  - 4
SN  - 1951-6851
UR  - https://doi.org/10.2991/wiet-13.2013.1
DO  - 10.2991/wiet-13.2013.1
ID  - Wang2013/12
ER  -