Cost estimation heuristics for phylogenetic network construction and refinement
As has been long known, searching for phylogenetic graphs generates a myriad of computationally hard problems. These include the familiar tree search, sum-of-pairs sequence alignment and tree-alignment. When network graphs are added as an option, additional complexities present themselves. Given that, then basic operations (e.g. determining single graph optimality values) are NP-hard (or even uncomputable depending on the optimality criterion), heuristics for these procedures are employed. When the problem is to identify a heuristically optimal network, higher-level cost estimation is required to allow for the efficient evaluation of the large number of candidate graphs encountered in a phylogenetic search. Initial estimators for network construction and refinement are presented and their performance illustrated with real data sets as a potential path towards further research analysis.
Authors
- Ward C. Wheeler (ORCID: https://orcid.org/0000-0001-6977-984X)
Institutions
- American Museum of Natural History (US)
Publication Details
- Journal
- Cladistics
- Published
- 2026-11-20
- DOI
- https://doi.org/10.1111/cla.70079
- Primary Topic
- Genomics and Phylogenetic Studies
- Type
- article
- Field-Weighted Citation Impact
- 0.00