×

Sharp upper and lower bounds on a restricted class of convex characters. (English) Zbl 1486.05043

Summary: Let \(\mathcal{T}\) be an unrooted binary tree with \(n\) distinctly labelled leaves. Deriving its name from the field of phylogenetics, a convex character on \(\mathcal{T}\) is simply a partition of the leaves such that the minimal spanning subtrees induced by the blocks of the partition are mutually disjoint. In earlier work S. Kelk and G. Stamoulis [Adv. Appl. Math. 84, 34–46 (2017; Zbl 1431.05084)] defined \(g_k(\mathcal{T})\) as the number of convex characters where each block has at least \(k\) leaves. Exact expressions were given for \(g_1\) and \(g_2\), where the topology of \(\mathcal{T}\) turns out to be irrelevant, and it was noted that for \(k \geq 3\) topological neutrality no longer holds. In this article, for every \(k \geq 3\) we describe tree topologies achieving the maximum and minimum values of \(g_k\) and determine corresponding expressions and exponential bounds for \(g_k\). Finally, we reflect briefly on possible algorithmic applications of these results.

MSC:

05C05 Trees
05A18 Partitions of sets
92B10 Taxonomy, cladistics, statistics in mathematical biology

Citations:

Zbl 1431.05084

References:

[1] N. Alexeev and M. Alekseyev.Combinatorial scoring of phylogenetic trees and networks based on homoplasy-free characters.Journal of Computational Biology, 25(11):1203-1219, 2018.
[2] B. Allen and M. Steel. Subtree transfer operations and their induced metrics on evolutionary trees.Annals of Combinatorics, 5:1-15, 2001. · Zbl 0978.05023
[3] E. Bachoore and H. Bodlaender. Convex recoloring of leaf-colored trees.Utrecht University technical report, 2006.
[4] D. Bryant. The splits in the neighborhood of a tree.Annals of Combinatorics, 8(1):1-11, 2004. · Zbl 1094.68071
[5] J. Felsenstein.Inferring Phylogenies. Sinauer Associates, Incorporated, 2004.
[6] M. Fischer and S. Kelk. On the maximum parsimony distance between phylogenetic trees.Annals of Combinatorics, 20(1):87-113, 2016. · Zbl 1332.05043
[7] W. Fitch. Toward defining the course of evolution: minimum change for a specific tree topology.Systematic Zoology, 20(4):406-416, 1971.
[8] R. Graham, D. Knuth, and O. Patashnik.Concrete Mathematics: A Foundation for Computer Science. Addison-Wesley, 1989. · Zbl 0668.00003
[9] J. Hartigan. Minimum mutation fits to a given tree.Biometrics, pages 53-65, 1973.
[10] K. St John. The shape of phylogenetic treespace.Systematic Biology, 66(1):e83, 2017.
[11] S. Kannan and T. Warnow. A fast algorithm for the computation and enumeration of perfect phylogenies.SIAM Journal on Computing, 26(6):1749-1763, 1997. · Zbl 0885.68073
[12] S. Kelk and G. Stamoulis. A note on convex characters, fibonacci numbers and exponential-time algorithms.Advances in Applied Mathematics, 84:34-46, 2017. · Zbl 1431.05084
[13] S. Moran and S. Snir. Efficient approximation of convex recolorings.Journal of Computer and System Sciences, 73(7):1078-1089, 2007. · Zbl 1123.68095
[14] C. Semple and M. Steel.Phylogenetics.Oxford University Press, 2003. · Zbl 1043.92026
[15] M. Steel.Phylogeny: Discrete and Random Processes in Evolution. SIAM, 2016. · Zbl 1361.92001
[16] R. van Wersch, S. Kelk, S. Linz, and G. Stamoulis. Reflections on kernelizing and computing unrooted agreement forests.Annals of Operations Research, 309(1):425- 451, 2022 · Zbl 1480.92156
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.