On the balance of unrooted trees

DOI10.7155/JGAA.00553zbMATH Open1457.05109arXiv1510.07882OpenAlexW3118235285MaRDI QIDQ5856665FDOQ5856665

Authors: Mareike Fischer, Volkmar Liebscher 

Publication date: 29 March 2021

Published in: Journal of Graph Algorithms and Applications (Search for Journal in Brave)

Abstract: We solve a class of optimization problems for (phylogenetic) $X$-trees or their shapes. These problems have recently appeared in different contexts, e.g. in the context of the impact of tree shapes on the size of TBR neighborhoods, but so far these problems have not been characterized and solved in a systematic way. In this work we generalize the concept and also present several applications. Moreover, our results give rise to a nice notion of balance for trees. Unsurprisingly, so-called caterpillars are the most unbalanced tree shapes, but it turns out that balanced tree shapes cannot be described so easily as they need not even be unique.

Full work available at URL: https://arxiv.org/abs/1510.07882

Recommendations

• On the combinatorics of rooted binary phylogenetic trees
• A new balance index for phylogenetic trees
• A balance index for phylogenetic trees based on rooted quartets
• The balanced minimum evolution problem
• Split sizes and extremal tree shapes

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85)

Cites Work

• The on-line encyclopedia of integer sequences
• A new balance index for phylogenetic trees
• A balance index for phylogenetic trees based on rooted quartets
• A parsimony-based metric for phylogenetic trees
• On statistical tests of phylogenetic tree imbalance: The Sackin and other indices revisited
• Comparison of phylogenetic trees
• Phylogeny. Discrete and random processes in evolution
• On the maximum parsimony distance between phylogenetic trees
• The sum of the distances between the leaves of a tree and the `semi-regular' property
• New Gromov-inspired metrics on phylogenetic tree space
• On the complexity of computing MP distance between binary phylogenetic trees
• Distribution of the Symmetric Difference Metric on Phylogenetic Trees
• On the minimum value of the Colless index and the bifurcating trees that achieve it

Cited In (7)

• On the Shapley value of unrooted phylogenetic trees
• On the minimum value of the Colless index and the bifurcating trees that achieve it
• Ancestral sequence reconstruction with maximum parsimony
• On the strength of some trees
• Defining binary phylogenetic trees using parsimony
• Split sizes and extremal tree shapes
• Measuring tree balance using symmetry nodes -- a new balance index and its extremal properties

Uses Software

• OEIS
• SackinMinimizer

This page was built for publication: On the balance of unrooted trees

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