Cargando…
On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters
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 n...
Autores principales: | , , |
---|---|
Formato: | Online Artículo Texto |
Lenguaje: | English |
Publicado: |
Springer Berlin Heidelberg
2016
|
Materias: | |
Acceso en línea: | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5420025/ https://www.ncbi.nlm.nih.gov/pubmed/27800561 http://dx.doi.org/10.1007/s00285-016-1068-3 |
_version_ | 1783234325410480128 |
---|---|
author | Gambette, Philippe Huber, K. T. Kelk, S. |
author_facet | Gambette, Philippe Huber, K. T. Kelk, S. |
author_sort | Gambette, Philippe |
collection | PubMed |
description | 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. |
format | Online Article Text |
id | pubmed-5420025 |
institution | National Center for Biotechnology Information |
language | English |
publishDate | 2016 |
publisher | Springer Berlin Heidelberg |
record_format | MEDLINE/PubMed |
spelling | pubmed-54200252017-05-22 On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters Gambette, Philippe Huber, K. T. Kelk, S. J Math Biol Article 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. Springer Berlin Heidelberg 2016-10-31 2017 /pmc/articles/PMC5420025/ /pubmed/27800561 http://dx.doi.org/10.1007/s00285-016-1068-3 Text en © The Author(s) 2016 Open AccessThis article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made. |
spellingShingle | Article Gambette, Philippe Huber, K. T. Kelk, S. On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters |
title | On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters |
title_full | On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters |
title_fullStr | On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters |
title_full_unstemmed | On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters |
title_short | On the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters |
title_sort | on the challenge of reconstructing level-1 phylogenetic networks from triplets and clusters |
topic | Article |
url | https://www.ncbi.nlm.nih.gov/pmc/articles/PMC5420025/ https://www.ncbi.nlm.nih.gov/pubmed/27800561 http://dx.doi.org/10.1007/s00285-016-1068-3 |
work_keys_str_mv | AT gambettephilippe onthechallengeofreconstructinglevel1phylogeneticnetworksfromtripletsandclusters AT huberkt onthechallengeofreconstructinglevel1phylogeneticnetworksfromtripletsandclusters AT kelks onthechallengeofreconstructinglevel1phylogeneticnetworksfromtripletsandclusters |