New characterisations of tree-based networks and proximity measures (2017)
Phylogenetic networks are a type of directed acyclic graph that represent how a set X of present-day species are descended from a common ancestor by processes of speciation and reticulate evolution. In the absence of reticulate evolution, such networks are simply phylogenetic (evolutionary) trees. Moreover, phylogenetic networks that are not trees can sometimes be represented as phylogenetic trees with additional directed edges placed between their edges. Such networks are called tree-based, and the class of phylogenetic networks that are tree-based has recently been characterised. In this paper, we establish a number of new characterisations of tree-based networks in terms of path partitions and antichains (in the spirit of Dilworth’s theorem), as well as via matchings in a bipartite graph. We also show that a temporal network is treebased if and only if it satisfies an antichain-to-leaf condition. In the second part of the paper, we define three indices that measure the extent to which an arbitrary phylogenetic network deviates from being tree-based. We describe how these three indices can be computed efficiently using classical results concerning maximum-sized matchings in bipartite graphs.
CitationFrancis A, Semple C, Steel M (2017). New characterisations of tree-based networks and proximity measures. Advances in Applied Mathematics.
This citation is automatically generated and may be unreliable. Use as a guide only.
Keywordsphylogenetic network; tree-based network; antichain; path partition; Dilworth’s theorem
ANZSRC Fields of Research49 - Mathematical sciences::4904 - Pure mathematics::490407 - Mathematical logic, set theory, lattices and universal algebra
49 - Mathematical sciences::4904 - Pure mathematics::490404 - Combinatorics and discrete mathematics (excl. physical combinatorics)
31 - Biological sciences::3104 - Evolutionary biology::310410 - Phylogeny and comparative analysis
49 - Mathematical sciences::4901 - Applied mathematics::490102 - Biological mathematics
Showing items related by title, author, creator and subject.
Huber, Katharina T.; Moulton, Vincent; Steel, Mike (University of Canterbury, 2002)It was recently shown that just five characters (functions on a finite set X) suffice to convexly define a trivalent tree with leaf set X. Here we show that four characters suffice which, since three characters is not ...
Bryant, David James; Waddell, Peter J. (University of Canterbury. Dept. of Mathematics, 1997)We present fast new algorithms for evaluating trees with respect to least squares and minimum evolution (ME), the most commonly used criteria for inferring phylogenetic trees from distance data. These include: an ...
Lightfoot, Ash (University of Canterbury. Mathematics and Statistics, 2007)Wallpaper patterns are categorised into lattices. A case-by-case analysis of each group of orthogonal transformations which preserve a lattice is used to develop the seventeen wallpaper groups. All the elements of each ...