Faster exact computation of rSPR distance

DOI10.1007/s10878-013-9695-8zbMath1322.90103OpenAlexW1991847723MaRDI QIDQ2343983

Ying Fan, Zhi-Zhong Chen, Lusheng Wang

Publication date: 11 May 2015

Published in: Journal of Combinatorial Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10878-013-9695-8

zbMATH Keywords

phylogenetic treefixed-parameter algorithmrSPR distance

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Applications of mathematical programming (90C90)

Related Items

A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees, Gene tree reconciliation including transfers with replacement is NP-hard and FPT, On the fixed parameter tractability of agreement-based phylogenetic distances, An Improved Approximation Algorithm for rSPR Distance, Better Practical Algorithms for rSPR Distance and Hybridization Number

Uses Software

• FastHN
• rSPR
• PhyloNet

Cites Work

• Efficient estimation of the accuracy of the maximum likelihood method for ancestral state reconstruction
• A 3-approximation algorithm for the subtree distance between phylogenies
• The maximum agreement forest problem: Approximation algorithms and computational experiments
• On the complexity of constructing evolutionary trees
• Fitting distances by tree metrics with increment error
• On the computational complexity of the rooted subtree prune and regraft distance
• On the complexity of comparing evolutionary trees