title: On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters.
abstract: Phylogenetic networks have gained prominence over the years due to their ability to represent complex non-treelike evolutionary events such as recombination or hybridization. Popular combinatorial objects used to construct them are triplet systems and cluster systems, the motivation being that any network N induces a triplet system [Formula: see text] and a softwired cluster system [Formula: see text]. Since in real-world studies it cannot be guaranteed that all triplets/softwired clusters induced by a network are available, it is of particular interest to understand whether subsets of [Formula: see text] or [Formula: see text] allow one to uniquely reconstruct the underlying network N. Here we show that even within the highly restricted yet biologically interesting space of level-1 phylogenetic networks it is not always possible to uniquely reconstruct a level-1 network N, even when all triplets in [Formula: see text] or all clusters in [Formula: see text] are available. On the positive side, we introduce a reasonably large subclass of level-1 networks the members of which are uniquely determined by their induced triplet/softwired cluster systems. Along the way, we also establish various enumerative results, both positive and negative, including results which show that certain special subclasses of level-1 networks N can be uniquely reconstructed from proper subsets of [Formula: see text] and [Formula: see text]. We anticipate these results to be of use in the design of algorithms for phylogenetic network inference.
authors: LIGM (UMR 8049), CNRS, ENPC, ESIEE Paris, Université Paris-Est, Marne-la-Vallée, 77454, Paris, France. philippe.gambette@u-pem.fr.
authors: Philippe
authors: 0000-0001-7062-0262
authors: P
authors: Gambette
authors: School of Computing Sciences, University of East Anglia, Norwich Research Park, Norwich, NR4 7TJ, UK.
authors: K T
authors: KT
authors: Huber
authors: Department of Knowledge Engineering (DKE), Maastricht University, Maastricht, The Netherlands.
authors: S
authors: S
authors: Kelk
mesh_terms: D000465:Algorithms; D002965:Classification / Q000379:methods*; D008954:Models, Biological; D010802:Phylogeny
keywords: 92D15; O5C05