Abstract | ||
---|---|---|
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 n(2)/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. |
Year | Venue | DocType |
---|---|---|
2007 | ALGORITHMS IN BIOINFORMATICS, PROCEEDINGS | Conference |
Volume | ISSN | Citations |
4645 | 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 |