Name
Abstract | ||
|---|---|---|
Synthesizing large-scale phylogenetic trees is a fundamental problem in evolutionary biology. Median tree problems have evolved as a powerful tool to reconstruct such trees. Given a tree collection, these problems seek a median tree under some problem-specific tree distance. Here, we introduce the median tree problem for the classical path-difference distance. We prove that this problem is NP-hard, and describe a fast local search heuristic that is based on solving a local search problem exactly. For an effective heuristic we devise a time efficient algorithm for this problem that improves on the best-know (naive) solution by a factor of n, where n is the size of the input trees. Finally, we demonstrate the performance of our heuristic in a comparative study with other commonly used methods that synthesize species trees using published empirical data sets. |
Year | DOI | Venue |
|---|---|---|
2016 | 10.1007/978-3-319-38782-6_18 | BIOINFORMATICS RESEARCH AND APPLICATIONS, ISBRA 2016 |
Keywords | DocType | Volume |
Phylogenetic trees,Median trees,Supertrees,Path-difference distance,Local search | Conference | 9683 |
ISSN | Citations | PageRank |
0302-9743 | 0 | 0.34 |
References | Authors | |
12 | 2 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Alexey Markin | 1 | 0 | 3.38 |
| Oliver Eulenstein | 2 | 505 | 52.71 |