New characterisations of treebased networks and proximity measures (2017)
Abstract
Phylogenetic networks are a type of directed acyclic graph that represent how a set X of presentday 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 treebased, and the class of phylogenetic networks that are treebased has recently been characterised. In this paper, we establish a number of new characterisations of treebased 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 antichaintoleaf 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 treebased. We describe how these three indices can be computed efficiently using classical results concerning maximumsized matchings in bipartite graphs.
Citation
Francis A, Semple C, Steel M (2017). New characterisations of treebased networks and proximity measures. Advances in Applied Mathematics.This citation is automatically generated and may be unreliable. Use as a guide only.
Keywords
phylogenetic network; treebased network; antichain; path partition; Dilworth’s theoremANZSRC Fields of Research
49  Mathematical sciences::4904  Pure mathematics::490407  Mathematical logic, set theory, lattices and universal algebra49  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
Related items
Showing items related by title, author, creator and subject.

The seventeen wallpaper groups
Lightfoot, Ash (University of Canterbury. Mathematics and Statistics, 2007)Wallpaper patterns are categorised into lattices. A casebycase analysis of each group of orthogonal transformations which preserve a lattice is used to develop the seventeen wallpaper groups. All the elements of each ... 
Classifying Material Implications over Minimal Logic
Diener H; McKubreJordens M (2018)The socalled paradoxes of material implication have motivated the development of many nonclassical logics over the years [2–5, 11]. In this note, we investigate some of these paradoxes and classify them, over minimal ... 
Quantifying the extent of lateral gene transfer required to avert a 'genome of eden'
Van Iersel, L.; Semple, C.; Steel, M. (University of Canterbury. Dept. of Mathematics and Statistics, 2009)The complex pattern of presence and absence of many genes across different species provides tantalising clues as to how genes evolved through the processes of gene genesis, gene loss and lateral gene transfer (LGT). The ...