title: The gene-duplication problem: near-linear time algorithms for NNI-based local searches.
abstract: The gene-duplication problem is to infer a species supertree from a collection of gene trees that are confounded by complex histories of gene-duplication events. This problem is NP-complete and thus requires efficient and effective heuristics. Existing heuristics perform a stepwise search of the tree space, where each step is guided by an exact solution to an instance of a local search problem. A classical local search problem is the {\tt NNI} search problem, which is based on the nearest neighbor interchange operation. In this work, we 1) provide a novel near-linear time algorithm for the {\tt NNI} search problem, 2) introduce extensions that significantly enlarge the search space of the {\tt NNI} search problem, and 3) present algorithms for these extended versions that are asymptotically just as efficient as our algorithm for the {\tt NNI} search problem. The exceptional speedup achieved in the extended {\tt NNI} search problems makes the gene-duplication problem more tractable for large-scale phylogenetic analyses. We verify the performance of our algorithms in a comparison study using sets of large randomly generated gene trees.
authors.affiliation: Department of Computer Science, Iowa StateUniversity, Ames, IA 50011, USA. bansal@cs.iastate.edu
authors.forename: Mukul S
authors.initials: MS
authors.lastname: Bansal
authors.forename: Oliver
authors.initials: O
authors.lastname: Eulenstein
authors.forename: André
authors.initials: A
authors.lastname: Wehe
mesh_terms: D000465:Algorithms; D000818:Animals; D019295:Computational Biology; D020440:Gene Duplication; D008957:Models, Genetic; D010802:Phylogeny; D017422:Sequence Analysis, DNA