Subtree transfer operations and their induced metrics on evolutionary trees

DOI10.1007/s00026-001-8006-8zbMath0978.05023OpenAlexW2044789562WikidataQ62472309 ScholiaQ62472309MaRDI QIDQ5939205

Benjamin L. Allen, Mike A. Steel

Publication date: 21 January 2002

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

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

zbMATH Keywords

phylogenycombinatorial complexityevolutionary treessubtree rearrangements

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Trees (05C05) Problems related to evolution (92D15) Graph theory (including graph drawing) in computer science (68R10)

Related Items (84)

Robust classifying of prokaryotic genomes ⋮ Sharp upper and lower bounds on a restricted class of convex characters ⋮ Fixed-parameter and approximation algorithms for maximum agreement forests of multifurcating trees ⋮ Dimension reduction in principal component analysis for trees ⋮ Approximating the maximum agreement forest on \(k\) trees ⋮ Reduction rules for the maximum parsimony distance on phylogenetic trees ⋮ Transforming phylogenetic networks: moving beyond tree space ⋮ Treewidth distance on phylogenetic trees ⋮ Characterizing local optima for maximum parsimony ⋮ Neighborhoods of Phylogenetic Trees: Exact and Asymptotic Counts ⋮ Spaces of phylogenetic networks from generalized nearest-neighbor interchange operations ⋮ Approximating geodesic tree distance ⋮ On the minimum number of topologies explaining a sample of DNA sequences ⋮ Improved approximation algorithm for maximum agreement forest of two rooted binary phylogenetic trees ⋮ Bounding the number of hybridisation events for a consistent evolutionary history ⋮ Distance metrics for ranked evolutionary trees ⋮ On the enumeration of tanglegrams and tangled chains ⋮ Distributions of topological tree metrics between a species tree and a gene tree ⋮ Phylogenetic network dissimilarity measures that take branch lengths into account ⋮ Information geometry for phylogenetic trees ⋮ Lost in space? Generalising subtree prune and regraft to spaces of phylogenetic networks ⋮ Tropical geometric variation of tree shapes ⋮ A parameterized algorithm for the maximum agreement forest problem on multiple rooted multifurcating trees ⋮ Nodal distances for rooted phylogenetic trees ⋮ The SNPR neighbourhood of tree-child networks ⋮ Hypercubes and Hamilton cycles of display sets of rooted phylogenetic networks ⋮ Exploring spaces of semi-directed level-1 networks ⋮ The space of tree-based phylogenetic networks ⋮ The agreement distance of unrooted phylogenetic networks ⋮ Extremal distances for subtree transfer operations in binary trees ⋮ The asymmetric cluster affinity cost ⋮ Cyclic generators and an improved linear kernel for the rooted subtree prune and regraft distance ⋮ A massively parallel branch-\&-bound algorithm for the balanced minimum evolution problem ⋮ Gene tree reconciliation including transfers with replacement is NP-hard and FPT ⋮ An extended model for phylogenetic maximum likelihood based on discrete morphological characters ⋮ Convex Characters, Algorithms, and Matchings ⋮ A near-linear kernel for bounded-state parsimony distance ⋮ Deep kernelization for the tree bisection and reconnection (TBR) distance in phylogenetics ⋮ Parsimony and the rank of a flattening matrix ⋮ A duality based 2-approximation algorithm for maximum agreement forest ⋮ Properties for the Fréchet mean in Billera-Holmes-Vogtmann treespace ⋮ Walks in phylogenetic treespace ⋮ Distribution of distances between topologies and its effect on detection of phylogenetic recombination ⋮ Ranked subtree prune and regraft ⋮ New reduction rules for the tree bisection and reconnection distance ⋮ The Aldous chain on cladograms in the diffusion limit ⋮ Comparing and aggregating partially resolved trees ⋮ Maximum parsimony distance on phylogenetic trees: a linear kernel and constant factor approximation algorithm ⋮ Bayesian modelling of compositional heterogeneity in molecular phylogenetics ⋮ Bounds on the size of the TBR unit-neighbourhood ⋮ A cluster reduction for computing the subtree distance between phylogenies ⋮ Parameterized and approximation algorithms for maximum agreement forest in multifurcating trees ⋮ Principal components analysis in the space of phylogenetic trees ⋮ A scalable parallelization of the gene duplication problem ⋮ On the subnet prune and regraft distance ⋮ Bounds for phylogenetic network space metrics ⋮ On the fixed parameter tractability of agreement-based phylogenetic distances ⋮ Comparing and simplifying distinct-cluster phylogenetic networks ⋮ New Gromov-inspired metrics on phylogenetic tree space ⋮ Phase transition in the sample complexity of likelihood-based phylogeny inference ⋮ Discriminative measures for comparison of phylogenetic trees ⋮ On unrooted and root-uncertain variants of several well-known phylogenetic network problems ⋮ The sum of the distances between the leaves of a tree and the `semi-regular' property ⋮ On agreement forests ⋮ Computing nearest neighbour interchange distances between ranked phylogenetic trees ⋮ Subtree prune and regraft: a reversible real tree-valued Markov process ⋮ The mean value of the squared path-difference distance for rooted phylogenetic trees ⋮ Unnamed Item ⋮ Rotation distance is fixed-parameter tractable ⋮ Approximating maximum agreement forest on multiple binary trees ⋮ A note on convex characters, Fibonacci numbers and exponential-time algorithms ⋮ Comparing and Aggregating Partially Resolved Trees ⋮ Unnamed Item ⋮ Algorithms for parameterized maximum agreement forest problem on multiple trees ⋮ Efficiently Calculating Evolutionary Tree Measures Using SAT ⋮ The maximum agreement forest problem: Approximation algorithms and computational experiments ⋮ Treewidth of display graphs: bounds, brambles and applications ⋮ Reflections on kernelizing and computing unrooted agreement forests ⋮ A Tight Kernel for Computing the Tree Bisection and Reconnection Distance between Two Phylogenetic Trees ⋮ A parsimony-based metric for phylogenetic trees ⋮ Neighborhoods of trees in circular orderings ⋮ On the maximum parsimony distance between phylogenetic trees ⋮ Information metrics for phylogenetic trees via distributions of discrete and continuous characters ⋮ TreeOfTrees method to evaluate the congruence between gene trees

This page was built for publication: Subtree transfer operations and their induced metrics on evolutionary trees