A Sub-quadratic Time and Space Complexity Solution for the Dated Tree Reconciliation Problem for Select Tree Topologies

DOI10.1007/978-3-662-48221-6_7zbMATH Open1367.92081OpenAlexW2238253283MaRDI QIDQ5283825FDOQ5283825

Authors: Benjamin Drinkwater, M. A. Charleston 

Publication date: 25 July 2017

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-662-48221-6_7

Recommendations

• Constructing the R* consensus tree of two trees in subcubic time
• Constructing the R* consensus tree of two trees in subcubic time
• Some problems related to the space of optimal tree reconciliations (invited talk)
• Algorithms and Computation
• An \(O(n\log n)\)-time algorithm for the maximum constrained agreement subtree problem for binary trees
• An optimal algorithm for computing all subtree repeats in trees
• An optimal algorithm for computing all subtree repeats in trees
• Time-space tradeoffs for dynamic programming algorithms in trees and bounded treewidth graphs
• Reconstructing a binary tree from its traversals in doubly logarithmic CREW time
• An efficient algorithm for some tree matching problems

zbMATH Keywords

phylogenycoevolutionNP-hardnesstree reconciliationtree shape

Mathematics Subject Classification ID

Problems related to evolution (92D15) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational methods for problems pertaining to biology (92-08)

Cites Work

• Stochastic models and descriptive statistics for phylogenetic trees, from Yule to today.
• The probabilities of rooted tree-shapes generated by random bifurcation
• Properties of phylogenetic trees generated by Yule-type speciation models

Cited In (2)

• Co-divergence and tree topology
• Deep coalescence reconciliation with unrooted gene trees: linear time algorithms

This page was built for publication: A Sub-quadratic Time and Space Complexity Solution for the Dated Tree Reconciliation Problem for Select Tree Topologies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5283825)