New characterisations of tree-based networks and proximity measures

Simple item page
dc.contributor.authorFrancis A
dc.contributor.authorSemple C
dc.contributor.authorSteel M
dc.date.accessioned2018-04-24T03:06:21Z
dc.date.available2018-04-24T03:06:21Z
dc.date.issued2017en
dc.date.updated2017-10-03T07:26:31Z
dc.description.abstractPhylogenetic 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.en
dc.identifier.citationFrancis A, Semple C, Steel M (2017). New characterisations of tree-based networks and proximity measures. Advances in Applied Mathematics.en
dc.identifier.doihttps://doi.org/10.1016/j.aam.2017.08.003
dc.identifier.issn0196-8858
dc.identifier.urihttp://hdl.handle.net/10092/15217
dc.language.isoen
dc.subjectphylogenetic networken
dc.subjecttree-based networken
dc.subjectantichainen
dc.subjectpath partitionen
dc.subjectDilworth’s theoremen
dc.subject.anzsrcFields of Research::49 - Mathematical sciences::4904 - Pure mathematics::490407 - Mathematical logic, set theory, lattices and universal algebraen
dc.subject.anzsrcFields of Research::49 - Mathematical sciences::4904 - Pure mathematics::490404 - Combinatorics and discrete mathematics (excl. physical combinatorics)en
dc.subject.anzsrcFields of Research::31 - Biological sciences::3104 - Evolutionary biology::310410 - Phylogeny and comparative analysisen
dc.subject.anzsrcFields of Research::49 - Mathematical sciences::4901 - Applied mathematics::490102 - Biological mathematicsen
dc.titleNew characterisations of tree-based networks and proximity measuresen
dc.typeJournal Articleen
Files
Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
tree-based_2017.pdf
Size:
755.45 KB
Format:
Adobe Portable Document Format
Description:
Accepted version
Download
Collections
Science: Journal Articles