Phylogenetic flexibility via Hall-type inequalities and submodularity

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

Preview

PDF (Published manuscript) - Published Version Available under License Creative Commons Attribution. Download (606kB) | Preview

Abstract

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
UEA Research Groups:	Faculty of Science > Research Groups > Computational Biology Faculty of Science > Research Groups > Norwich Epidemiology Centre Faculty of Medicine and Health Sciences > Research Groups > Norwich Epidemiology Centre
Related URLs:	http://www.scopus.com/inward/record.url?...
Depositing User:	Pure Connector
Date Deposited:	28 Mar 2018 12:30
Last Modified:	20 Apr 2023 23:43
URI:	https://ueaeprints.uea.ac.uk/id/eprint/66633
DOI:	10.1007/s11538-018-0419-1

Downloads

Actions (login required)

View Item