Combinatorial characterization of a certain class of words and a conjectured connection with general subclasses of phylogenetic tree-child networks
Abstract The combinatorial study of phylogenetic networks has attracted much attention in recent times. In particular, one class of them, the so-called tree-child networks, are becoming the most prominent ones. However, their combinatorial properties are largely unknown. In this paper we address the...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Nature Portfolio
2021-11-01
|
| Series: | Scientific Reports |
| Online Access: | https://doi.org/10.1038/s41598-021-01166-w |
| _version_ | 1830284392621146112 |
|---|---|
| author | Miquel Pons Josep Batle |
| author_facet | Miquel Pons Josep Batle |
| author_sort | Miquel Pons |
| collection | DOAJ |
| description | Abstract The combinatorial study of phylogenetic networks has attracted much attention in recent times. In particular, one class of them, the so-called tree-child networks, are becoming the most prominent ones. However, their combinatorial properties are largely unknown. In this paper we address the problem of exactly counting them. We conjecture a relationship with the cardinality of a certain class of words. By solving the counting problem for the words, and on the basis of the conjecture, several simple recurrence formulas for general cases arise. Moreover, a precise asymptotic analysis is provided. Our results coincide with all current formulas in the literature for particular subclasses of tree-child networks, as well as with numerical results obtained for small networks. We expect that the study of the relationship between the newly defined words and the networks will lead to further combinatoric characterizations of this class of phylogenetic networks. |
| first_indexed | 2024-12-19T03:18:59Z |
| format | Article |
| id | doaj.art-367bafac32804daeac8c8a08b43b1e69 |
| institution | Directory Open Access Journal |
| issn | 2045-2322 |
| language | English |
| last_indexed | 2024-12-19T03:18:59Z |
| publishDate | 2021-11-01 |
| publisher | Nature Portfolio |
| record_format | Article |
| series | Scientific Reports |
| spelling | doaj.art-367bafac32804daeac8c8a08b43b1e692022-12-21T20:37:49ZengNature PortfolioScientific Reports2045-23222021-11-0111111410.1038/s41598-021-01166-wCombinatorial characterization of a certain class of words and a conjectured connection with general subclasses of phylogenetic tree-child networksMiquel Pons0Josep Batle1Departament de Física, Universitat de les Illes BalearsDepartament de Física, Universitat de les Illes BalearsAbstract The combinatorial study of phylogenetic networks has attracted much attention in recent times. In particular, one class of them, the so-called tree-child networks, are becoming the most prominent ones. However, their combinatorial properties are largely unknown. In this paper we address the problem of exactly counting them. We conjecture a relationship with the cardinality of a certain class of words. By solving the counting problem for the words, and on the basis of the conjecture, several simple recurrence formulas for general cases arise. Moreover, a precise asymptotic analysis is provided. Our results coincide with all current formulas in the literature for particular subclasses of tree-child networks, as well as with numerical results obtained for small networks. We expect that the study of the relationship between the newly defined words and the networks will lead to further combinatoric characterizations of this class of phylogenetic networks.https://doi.org/10.1038/s41598-021-01166-w |
| spellingShingle | Miquel Pons Josep Batle Combinatorial characterization of a certain class of words and a conjectured connection with general subclasses of phylogenetic tree-child networks Scientific Reports |
| title | Combinatorial characterization of a certain class of words and a conjectured connection with general subclasses of phylogenetic tree-child networks |
| title_full | Combinatorial characterization of a certain class of words and a conjectured connection with general subclasses of phylogenetic tree-child networks |
| title_fullStr | Combinatorial characterization of a certain class of words and a conjectured connection with general subclasses of phylogenetic tree-child networks |
| title_full_unstemmed | Combinatorial characterization of a certain class of words and a conjectured connection with general subclasses of phylogenetic tree-child networks |
| title_short | Combinatorial characterization of a certain class of words and a conjectured connection with general subclasses of phylogenetic tree-child networks |
| title_sort | combinatorial characterization of a certain class of words and a conjectured connection with general subclasses of phylogenetic tree child networks |
| url | https://doi.org/10.1038/s41598-021-01166-w |
| work_keys_str_mv | AT miquelpons combinatorialcharacterizationofacertainclassofwordsandaconjecturedconnectionwithgeneralsubclassesofphylogenetictreechildnetworks AT josepbatle combinatorialcharacterizationofacertainclassofwordsandaconjecturedconnectionwithgeneralsubclassesofphylogenetictreechildnetworks |