Encoding and ordering \(X\)-cactuses. (English) Zbl 1500.92063
Summary: Phylogenetic networks are a generalization of evolutionary or phylogenetic trees that are commonly used to represent the evolution of species which cross with one another. A special type of phylogenetic network is an \(X\)-cactus, which is essentially a cactus graph in which all vertices with degree less than three are labelled by at least one element from a set \(X\) of species. In this paper, we present a way to encode \(X\)-cactuses in terms of certain collections of partitions of \(X\) that naturally arise from \(X\)-cactuses. Using this encoding, we also introduce a partial order on the set of \(X\)-cactuses (up to isomorphism), and derive some structural properties of the resulting partially ordered set. This includes an analysis of some properties of its least upper and greatest lower bounds. Our results not only extend some fundamental properties of phylogenetic trees to \(X\)-cactuses, but also provide a new approach to solving topical problems in phylogenetic network theory such as deriving consensus networks.
References:
| [1] | Ardila, Federico; Klivans, Caroline J., The Bergman complex of a matroid and phylogenetic trees, J. Comb. Theory, Ser. B, 96, 1, 38-49 (2006) · Zbl 1082.05021 |
| [2] | Birkhoff, Garrett, Lattice Theory, Vol. 25 (1940), American Mathematical Soc. · Zbl 0063.00402 |
| [3] | Bryant, David, A classification of consensus methods for phylogenetics, DIMACS Ser. Discret. Math. Theor. Comput. Sci., 61, 163-184 (2003) · Zbl 1029.05032 |
| [4] | Buneman, Peter, The recovery of trees from measures of dissimilarity, (Mathematics in the Archaeological and Historical Sciences (1971)) |
| [5] | Devadoss, Satyan; Durell, Cassandra; Forcey, Stefan, Split network polytopes and network spaces (2019), arXiv preprint · Zbl 1435.05050 |
| [6] | Dress, Andreas; Moulton, Vincent; Steel, Michael, Trees, taxonomy, and strongly compatible multi-state characters, Adv. Appl. Math., 19, 1, 1-30 (1997) · Zbl 0879.92003 |
| [7] | Dress, Andreas; Moulton, Vincent; Wu, Taoyang, A topological approach to tree (re-)construction, (Dress, A.; Biebler, K-E.; Cieslik, D.; Spillner, A., The Maths of Flu (2010), Shaker Verlag: Shaker Verlag Aachen, Germany), 59-75 |
| [8] | Gambette, Philippe; Huber, Katharina T., On encodings of phylogenetic networks of bounded level, J. Math. Biol., 65, 1, 157-180 (2012) · Zbl 1303.92080 |
| [9] | Gambette, Philippe; Huber, Katharina T.; Scholz, Guillaume E., Uprooted phylogenetic networks, Bull. Math. Biol., 79, 9, 2022-2048 (2017) · Zbl 1372.92071 |
| [10] | Gill, Jonna; Linusson, Svante; Moulton, Vincent; Steel, Mike, A regular decomposition of the edge-product space of phylogenetic trees, Adv. Appl. Math., 41, 2, 158-176 (2008) · Zbl 1149.05305 |
| [11] | Hayamizu, Momoko; Huber, Katharina T.; Moulton, Vincent; Murakami, Yukihiro, Recognizing and realizing cactus metrics, Inf. Process. Lett., 157, Article 105916 pp. (2020) · Zbl 1447.05186 |
| [12] | Huber, Katharina T.; Linz, Simone; Moulton, Vincent; Wu, Taoyang, Spaces of phylogenetic networks from generalized nearest-neighbor interchange operations, J. Math. Biol., 72, 3, 699-725 (2016) · Zbl 1330.05150 |
| [13] | Huber, Katharina T.; Moulton, Vincent; Wu, Taoyang, Transforming phylogenetic networks: moving beyond tree space, J. Theor. Biol., 404, 30-39 (2016) · Zbl 1343.92348 |
| [14] | Huson, Daniel H.; Rupp, Regula; Scornavacca, Celine, Phylogenetic Networks: Concepts, Algorithms and Applications (2010), Cambridge University Press |
| [15] | Semple, Charles; Steel, Mike A., Phylogenetics, vol. 24 (2003), Oxford University Press: Oxford University Press Oxford · Zbl 1043.92026 |
| [16] | Stanley, Richard P., Enumerative Combinatorics, Volume I (1997), Cambridge University Press · Zbl 0889.05001 |
| [17] | Steel, Mike, Phylogeny: Discrete and Random Processes in Evolution (2016), SIAM · Zbl 1361.92001 |
| [18] | Trappmann, Henryk; Ziegler, Günter M., Shellability of complexes of trees, J. Comb. Theory, Ser. A, 82, 2, 168-178 (1998) · Zbl 0916.06004 |
| [19] | Trotter, William T., Partially ordered sets, (Handbook of Combinatorics, vol. 1 (1995)), 433-480 · Zbl 0841.06001 |
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.
