All galls are divided into three or more parts: recursive enumeration of labeled histories for galled trees
Abstract Objective In mathematical phylogenetics, a labeled rooted binary tree topology can possess any of a number of labeled histories, each of which represents a possible temporal ordering of its coalescences. Labeled histories appear frequently in calculations that describe the combinatorics of...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
BMC
2023-02-01
|
| Series: | Algorithms for Molecular Biology |
| Subjects: | |
| Online Access: | https://doi.org/10.1186/s13015-023-00224-4 |
| _version_ | 1827985169561157632 |
|---|---|
| author | Shaili Mathur Noah A. Rosenberg |
| author_facet | Shaili Mathur Noah A. Rosenberg |
| author_sort | Shaili Mathur |
| collection | DOAJ |
| description | Abstract Objective In mathematical phylogenetics, a labeled rooted binary tree topology can possess any of a number of labeled histories, each of which represents a possible temporal ordering of its coalescences. Labeled histories appear frequently in calculations that describe the combinatorics of phylogenetic trees. Here, we generalize the concept of labeled histories from rooted phylogenetic trees to rooted phylogenetic networks, specifically for the class of rooted phylogenetic networks known as rooted galled trees. Results Extending a recursive algorithm for enumerating the labeled histories of a labeled tree topology, we present a method to enumerate the labeled histories associated with a labeled rooted galled tree. The method relies on a recursive decomposition by which each gall in a galled tree possesses three or more descendant subtrees. We exhaustively provide the numbers of labeled histories for all small galled trees, finding that each gall reduces the number of labeled histories relative to a specified galled tree that does not contain it. Conclusion The results expand the set of structures for which labeled histories can be enumerated, extending a well-known calculation for phylogenetic trees to a class of phylogenetic networks. |
| first_indexed | 2024-04-09T23:10:36Z |
| format | Article |
| id | doaj.art-3adcc71a49c140fb802cf74db2d66850 |
| institution | Directory Open Access Journal |
| issn | 1748-7188 |
| language | English |
| last_indexed | 2024-04-09T23:10:36Z |
| publishDate | 2023-02-01 |
| publisher | BMC |
| record_format | Article |
| series | Algorithms for Molecular Biology |
| spelling | doaj.art-3adcc71a49c140fb802cf74db2d668502023-03-22T10:25:24ZengBMCAlgorithms for Molecular Biology1748-71882023-02-0118111310.1186/s13015-023-00224-4All galls are divided into three or more parts: recursive enumeration of labeled histories for galled treesShaili Mathur0Noah A. Rosenberg1Department of Biology, Stanford UniversityDepartment of Biology, Stanford UniversityAbstract Objective In mathematical phylogenetics, a labeled rooted binary tree topology can possess any of a number of labeled histories, each of which represents a possible temporal ordering of its coalescences. Labeled histories appear frequently in calculations that describe the combinatorics of phylogenetic trees. Here, we generalize the concept of labeled histories from rooted phylogenetic trees to rooted phylogenetic networks, specifically for the class of rooted phylogenetic networks known as rooted galled trees. Results Extending a recursive algorithm for enumerating the labeled histories of a labeled tree topology, we present a method to enumerate the labeled histories associated with a labeled rooted galled tree. The method relies on a recursive decomposition by which each gall in a galled tree possesses three or more descendant subtrees. We exhaustively provide the numbers of labeled histories for all small galled trees, finding that each gall reduces the number of labeled histories relative to a specified galled tree that does not contain it. Conclusion The results expand the set of structures for which labeled histories can be enumerated, extending a well-known calculation for phylogenetic trees to a class of phylogenetic networks.https://doi.org/10.1186/s13015-023-00224-4Galled treesLabeled historiesMathematical phylogeneticsPhylogenetic networks |
| spellingShingle | Shaili Mathur Noah A. Rosenberg All galls are divided into three or more parts: recursive enumeration of labeled histories for galled trees Algorithms for Molecular Biology Galled trees Labeled histories Mathematical phylogenetics Phylogenetic networks |
| title | All galls are divided into three or more parts: recursive enumeration of labeled histories for galled trees |
| title_full | All galls are divided into three or more parts: recursive enumeration of labeled histories for galled trees |
| title_fullStr | All galls are divided into three or more parts: recursive enumeration of labeled histories for galled trees |
| title_full_unstemmed | All galls are divided into three or more parts: recursive enumeration of labeled histories for galled trees |
| title_short | All galls are divided into three or more parts: recursive enumeration of labeled histories for galled trees |
| title_sort | all galls are divided into three or more parts recursive enumeration of labeled histories for galled trees |
| topic | Galled trees Labeled histories Mathematical phylogenetics Phylogenetic networks |
| url | https://doi.org/10.1186/s13015-023-00224-4 |
| work_keys_str_mv | AT shailimathur allgallsaredividedintothreeormorepartsrecursiveenumerationoflabeledhistoriesforgalledtrees AT noaharosenberg allgallsaredividedintothreeormorepartsrecursiveenumerationoflabeledhistoriesforgalledtrees |