Caterpillars on three and four leaves are sufficient to reconstruct binary normal networks
- PDF / 580,748 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 33 Downloads / 170 Views
Mathematical Biology
Caterpillars on three and four leaves are sufficient to reconstruct binary normal networks Simone Linz1
· Charles Semple2
Received: 3 February 2020 / Revised: 15 July 2020 © Springer-Verlag GmbH Germany, part of Springer Nature 2020
Abstract While every rooted binary phylogenetic tree is determined by its set of displayed rooted triples, such a result does not hold for an arbitrary rooted binary phylogenetic network. In particular, there exist two non-isomorphic rooted binary temporal normal networks that display the same set of rooted triples. Moreover, without any structural constraint on the rooted phylogenetic networks under consideration, similarly negative results have also been established for binets and trinets which are rooted subnetworks on two and three leaves, respectively. Hence, in general, piecing together a rooted phylogenetic network from such a set of small building blocks appears insurmountable. In contrast to these results, in this paper, we show that a rooted binary normal network is determined by its sets of displayed caterpillars (particular type of subtrees) on three and four leaves. The proof is constructive and realises a polynomial-time algorithm that takes the sets of caterpillars on three and four leaves displayed by a rooted binary normal network and, up to isomorphism, reconstructs this network. Keywords Normal networks · Rooted triples · Quads Mathematics Subject Classification 05C85 · 68R10
The authors were supported by the New Zealand Marsden Fund.
B
Charles Semple [email protected] Simone Linz [email protected]
1
School of Computer Science, University of Auckland, Auckland, New Zealand
2
School of Mathematics and Statistics, University of Canterbury, Christchurch, New Zealand
123
S. Linz, C. Semple
1 Introduction Rooted phylogenetic networks are a generalisation of rooted phylogenetic trees that allow for the representation of non-treelike processes such as hybridisation and lateral gene transfer. Recently many structural properties of rooted phylogenetic networks have been described that have led to a classification of such networks into several well-studied network classes [e.g. normal (Willson 2010), tree-child (Cardona et al. 2009), and tree-based (Francis and Steel 2015)]. Furthermore, the development of algorithms to reconstruct rooted phylogenetic networks from smaller building blocks remains an active area of research for the last 15 years. While historically rooted triples were most prominent as building blocks [see, for example Habib and To (2012), van Iersel and Kelk (2011), Jansson et al. (2006), Jansson and Sung (2006)], the focus has become broader and now also includes rooted phylogenetic trees and clusters. In turn, this has led to many algorithmic advances (for a recent overview, see Bulteau and Weller (2019, Section 5.2.3) and references therein). However, when reconstructing a rooted phylogenetic network from a given set of building blocks, most approaches infer new building blocks, i.e. the resulting network
Data Loading...
