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 NNI search problem, which is based on the nearest neighbor interchange operation. In this work we (i) provide a novel near-linear time algorithm for the NNI search problem, (ii) introduce extensions that significantly enlarge the search space of the NNI search problem, and (iii) present algorithms for these extended versions that are asymptotically just as efficient as our algorithm for the NNI search problem. The substantially extended NNI search problem, along with the exceptional speed-up achieved, make the gene-duplication problem more tractable for large-scale phylogenetic analyses. |
Year | Venue | DocType |
---|---|---|
2008 | BIOINFORMATICS RESEARCH AND APPLICATIONS | Conference |
Volume | ISSN | Citations |
4983 | 0302-9743 | 0 |
PageRank | References | Authors |
0.34 | 0 | 2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mukul S. Bansal | 1 | 294 | 23.97 |
Oliver Eulenstein | 2 | 505 | 52.71 |