An Omega(n2/ log n) speed-up of TBR heuristics for the gene-duplication problem.
The gene-duplication problem is to infer a species supertree from gene trees that are confounded by complex histories of gene duplications. This problem is NP-hard 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. We improve on the time complexity of the local search problem by a factor of n2= log n, where n is the size of the resulting species supertree. Typically, several thousand instances of the local search problem are solved throughout a stepwise heuristic search. Hence, our improvement makes the gene-duplication problem much more tractable for large-scale phylogenetic analyses.
Bansal
Mukul S
MS
Department of Computer Science, Iowa State University, Ames, IA 50011, USA.
Eulenstein
Oliver
O
D000465:Algorithms; D001483:Base Sequence; D002874:Chromosome Mapping / Q000379:methods*; D020440:Gene Duplication; D008969:Molecular Sequence Data; D017422:Sequence Analysis, DNA / Q000379:methods*