Galois connections for phylogenetic networks and their polytopes
- PDF / 1,341,137 Bytes
- 31 Pages / 439.37 x 666.142 pts Page_size
- 53 Downloads / 243 Views
Galois connections for phylogenetic networks and their polytopes Stefan Forcey1
· Drew Scalzo1
Received: 6 April 2020 / Accepted: 13 August 2020 © Springer Science+Business Media, LLC, part of Springer Nature 2020
Abstract We describe Galois connections which arise between two kinds of combinatorial structures, both of which generalize trees with labeled leaves, and then apply those connections to a family of polytopes. The graphs we study can be imbued with metric properties or associated with vectors. Famous examples are the Billera– Holmes–Vogtmann metric space of phylogenetic trees, and the Balanced Minimal Evolution polytopes of phylogenetic trees described by Eickmeyer, Huggins, Pachter and Yoshida. Recently, the space of trees has been expanded to split networks by Devadoss and Petti, while the definition of phylogenetic polytopes has been generalized to encompass 1-nested phylogenetic networks, by Durell and Forcey. The first Galois connection we describe is a reflection between the (unweighted) circular split networks and the 1-nested phylogenetic networks. Another Galois connection exists between certain metric versions of these structures. Reflection between the purely combinatorial posets becomes a coreflection in the geometric case. Our chief contributions here, beyond the discovery of the Galois connections, are: a translation between approaches using PC-trees and networks, a new way to look at weightings on networks, and a fuller characterization of faces of the phylogenetic polytopes. Keywords Polytopes · Phylogenetics · Trees · Metric spaces
1 Introduction The simplest structure we consider here is a partition of a finite set into two parts. A tree with labeled leaves represents a collection of such bipartitions, also known as splits, since removing any edge of the tree partitions the leaves via separating the tree into two components. A collection of splits that can be thus displayed by a tree is
B 1
Stefan Forcey [email protected] Department of Mathematics, The University of Akron, Akron, OH 44325-4002, USA
123
Journal of Algebraic Combinatorics
8 6
7
1
7 5
2 4 3
8
6 5
1 2
3
4
Fig. 1 A weighted 1-nested phylogenetic network, unrooted on the left, and with a root node (the only source) on the right. On the right leaf 7 is the outgroup, and edges are given compatible directions (Not all those directions are completely determined by the choice of root)
called pairwise compatible. In this paper we study two generalizations of labeled trees which display larger, more general sets of splits. The motivation for many of our definitions and results comes from phylogenomics. The goal is to recreate ancestral relationships using genetic data from individuals or species available today (extant taxa). The process begins with models of gene mutation, which allow the measurement of genetic distance between taxa. Euclidean embeddings of simple graphs, called circular split networks, allow such metrics to be visualized in terms of discrete amounts of genetic distance assigned to splits betwe
Data Loading...
