A cluster reduction for computing the subtree distance between phylogenies

DOI10.1007/S00026-011-0108-3MaRDI QIDQ659644zbMATH OpenOpenAlexFDO

Authors Simone Linz, Charles Semple

Publication date 24 January 2012

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL http://hdl.handle.net/10092/12531

zbMATH Keywords

phylogenetic treecluster reductiondivide-and-conquer approachrooted subtree prune and regraftrSPR

Mathematics Subject Classification ID

Problems related to evolution (92D15) Trees (05C05)

Recommendations

• Faster exact computation of rSPR distance
• Faster exact computation of rSPR distance
• On the computational complexity of the rooted subtree prune and regraft distance
• On the fixed parameter tractability of agreement-based phylogenetic distances
• On the combinatorics of rooted binary phylogenetic trees

Cites work

• A framework for representing reticulate evolution
• Bounding the number of hybridisation events for a consistent evolutionary history
• On the computational complexity of the rooted subtree prune and regraft distance
• Subtree transfer operations and their induced metrics on evolutionary trees

Cited in

(14)

• On the maximum parsimony distance between phylogenetic trees
• Faster exact computation of rSPR distance
• A 3-approximation algorithm for the subtree distance between phylogenies
• Treewidth distance on phylogenetic trees
• A practical fixed-parameter algorithm for constructing tree-child networks from multiple binary trees
• New FPT algorithms for finding the temporal hybridization number for sets of phylogenetic trees
• Better practical algorithms for rSPR distance and hybridization number
• Note on the hybridization number and subtree distance in phylogenetics
• Ranked subtree prune and regraft
• Faster exact computation of rSPR distance
• Gene tree reconciliation including transfers with replacement is NP-hard and FPT
• Computing maximum agreement forests without cluster partitioning is folly
• Reflections on kernelizing and computing unrooted agreement forests
• On the fixed parameter tractability of agreement-based phylogenetic distances

This page was built for publication: A cluster reduction for computing the subtree distance between phylogenies

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