Counting phylogenetic networks
We give approximate counting formulae for the numbers of labelled general, treechild, and normal (binary) phylogenetic networks on n vertices. These formulae are of the form 2γnlogn+O(n), where the constant γ is 3/2 for general networks, and 5/4 for tree-child and normal networks. We also show that...
| Main Authors: | , , |
|---|---|
| Format: | Journal article |
| Published: |
Springer Verlag
2015
|
| _version_ | 1797097944423333888 |
|---|---|
| author | McDiarmid, C Semple, C Welsh, D |
| author_facet | McDiarmid, C Semple, C Welsh, D |
| author_sort | McDiarmid, C |
| collection | OXFORD |
| description | We give approximate counting formulae for the numbers of labelled general, treechild, and normal (binary) phylogenetic networks on n vertices. These formulae are of the form 2γnlogn+O(n), where the constant γ is 3/2 for general networks, and 5/4 for tree-child and normal networks. We also show that the number of leaf-labelled tree-child and normal networks with ℓ leaves are both 22ℓlogℓ+O(ℓ). Further we determine the typical numbers of leaves, tree vertices, and reticulation vertices for each of these classes of networks. |
| first_indexed | 2024-03-07T05:02:34Z |
| format | Journal article |
| id | oxford-uuid:d8ca5b2a-bbf9-4720-a7dd-1844fc2c776d |
| institution | University of Oxford |
| last_indexed | 2024-03-07T05:02:34Z |
| publishDate | 2015 |
| publisher | Springer Verlag |
| record_format | dspace |
| spelling | oxford-uuid:d8ca5b2a-bbf9-4720-a7dd-1844fc2c776d2022-03-27T08:51:20ZCounting phylogenetic networksJournal articlehttp://purl.org/coar/resource_type/c_dcae04bcuuid:d8ca5b2a-bbf9-4720-a7dd-1844fc2c776dSymplectic Elements at OxfordSpringer Verlag2015McDiarmid, CSemple, CWelsh, DWe give approximate counting formulae for the numbers of labelled general, treechild, and normal (binary) phylogenetic networks on n vertices. These formulae are of the form 2γnlogn+O(n), where the constant γ is 3/2 for general networks, and 5/4 for tree-child and normal networks. We also show that the number of leaf-labelled tree-child and normal networks with ℓ leaves are both 22ℓlogℓ+O(ℓ). Further we determine the typical numbers of leaves, tree vertices, and reticulation vertices for each of these classes of networks. |
| spellingShingle | McDiarmid, C Semple, C Welsh, D Counting phylogenetic networks |
| title | Counting phylogenetic networks |
| title_full | Counting phylogenetic networks |
| title_fullStr | Counting phylogenetic networks |
| title_full_unstemmed | Counting phylogenetic networks |
| title_short | Counting phylogenetic networks |
| title_sort | counting phylogenetic networks |
| work_keys_str_mv | AT mcdiarmidc countingphylogeneticnetworks AT semplec countingphylogeneticnetworks AT welshd countingphylogeneticnetworks |