On the balance of unrooted trees

DOI10.7155/JGAA.00553MaRDI QIDQ5856665zbMATH OpenOpenAlexFDO

Authors Mareike Fischer, Volkmar Liebscher

Publication date 29 March 2021

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

Copyright license Creative Commons Attribution 4.0 International

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

Mathematics Subject Classification ID

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

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.

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

Cites work

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

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

Describes a project that uses

Uses Software

• SackinMinimizer
• OEIS

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)