The gene-duplication problem is to infer a species supertree from acollection of gene trees that are confounded by complex histories of gene duplicationevents. This problem is NP-complete and thus requires efficient and effectiveheuristics. Existing heuristics perform a stepwise search of the tree space, whereeach step is guided by an exact solution to an instance of a local search problem.A classical local search problem is the NNI search problem, which is based onthe nearest neighbor interchange operation. In this work we (i) provide a novelnear-linear time algorithm for the NNI search problem, (ii) introduce extensionsthat significantly enlarge the search space of the NNI search problem, and (iii)present algorithms for these extended versions that are asymptotically just as efficientas our algorithm for the NNI search problem. The substantially extendedNNI search problem, along with the exceptional speed-up achieved, make thegene-duplication problem more tractable for large-scale phylogenetic analyses.
['Mukul S. Bansal', 'Oliver Eulenstein']
The gene-duplication problem: near-linear time algorithms for NNI based local searches