Phylogenetic flexibility via Hall-type inequalities and submodularity

Huber, Katharina T., Moulton, Vincent ORCID: and Steel, Mike (2019) Phylogenetic flexibility via Hall-type inequalities and submodularity. Journal of Mathematical Biology, 81 (2). 598–617. ISSN 0303-6812

[thumbnail of Published manuscript]
PDF (Published manuscript) - Published Version
Available under License Creative Commons Attribution.

Download (606kB) | Preview


Given a collection τ of subsets of a finite set X, we say that τ is phylogenetically flexible if, for any collection R of rooted phylogenetic trees whose leaf sets comprise the collection τ , R is compatible (i.e. there is a rooted phylogenetic X-tree that displays each tree in R). We show that τ is phylogenetically flexible if and only if it satisfies a Hall-type inequality condition of being ‘slim’. Using submodularity arguments, we show that there is a polynomial-time algorithm for determining whether or not τ is slim. This ‘slim’ condition reduces to a simpler inequality in the case where all of the sets in τ have size 3, a property we call ‘thin’. Thin sets were recently shown to be equivalent to the existence of an (unrooted) tree for which the median function provides an injective mapping to its vertex set; we show here that the unrooted tree in this representation can always be chosen to be a caterpillar tree. We also characterise when a collection τ of subsets of size 2 is thin (in terms of the flexibility of total orders rather than phylogenies) and show that this holds if and only if an associated bipartite graph is a forest. The significance of our results for phylogenetics is in providing precise and efficiently verifiable conditions under which supertree methods that require consistent inputs of trees can be applied to any input trees on given subsets of species.

Item Type: Article
Additional Information: Special Issue: Algebraic Methods in Phylogenetics
Uncontrolled Keywords: phylogenetic tree,set systems,partial taxon coverage,bipartite graph,hall’s marriage theorem,submodularity
Faculty \ School: Faculty of Science > School of Computing Sciences
Related URLs:
Depositing User: Pure Connector
Date Deposited: 28 Mar 2018 12:30
Last Modified: 22 Oct 2022 03:40
DOI: 10.1007/s11538-018-0419-1

Actions (login required)

View Item View Item