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

DOI

https://doi.org/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.

Open Access

This is an open access article distributed under the CC BY-NC license.