Notice of RetractionAn algorithm for gene-loss problem based on rNNI local search

Notice of Retraction

After careful and considered review of the content of this paper by a duly constituted expert committee, this paper has been found to be in violation of IEEE´s Publication Principles.

We hereby retract the content of this paper. Reasonable effort should be made to remove all past references to this paper.

The presenting author of this paper has the option to appeal this decision by contacting TPII@ieee.org.

In this paper, we consider the gene-loss problem which is to infer a species supertree from a collection of gene trees. These gene trees are confounded by complex histories of gene loss and gene duplication events. This problem has been proved to be NP-complete by B. Ma et al. Existing heuristics aimed at solving the gene-loss problem search the space of all possible supertrees guided by a series of exact solutions to instances of a local search problem. The local search problem is to find an optimal phylogenetic tree in the tree space. We give an effective parsimony heuristics which perform the rooted nearest neighbor interchange operation (rNNI) on an original supertree. Each rooted nearest neighbor interchange operation can obtain a new supertree. The time complexity of the naive heuristics for gene-loss problem on 2-rNNI-local-search is O(kmn²). We provide a new algorithm which can solve the problem in O(kmn).