Cost estimation heuristics for phylogenetic network construction and refinement
Cladistics · 2026-11-20
DOI: 10.1111/cla.70079 ↗At a glance
Journal article in Cladistics, published online on 2026-11-20. Written by Ward C Wheeler. Institution: Division of Invertebrate Zoology, American Museum of Natural History, New York, NY, USA. 51 references. Funded by: DARPA, American Museum of Natural History, Defense Advanced Research Projects Agency.
Abstract (original language)
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 and institutions
- Division of Invertebrate Zoology, American Museum of Natural History, New York, NY, USA.
ORCID profiles: Ward C Wheeler
Funding
- DARPA
- American Museum of Natural History
- Defense Advanced Research Projects Agency
Cite
APA
Wheeler, W. C. (2026). Cost estimation heuristics for phylogenetic network construction and refinement. Cladistics. https://doi.org/10.1111/cla.70079
Vancouver
Wheeler WC. Cost estimation heuristics for phylogenetic network construction and refinement. Cladistics. 2026. doi:10.1111/cla.70079
BibTeX
@article{Wheeler2026,
author = {Wheeler, Ward C},
title = {Cost estimation heuristics for phylogenetic network construction and refinement},
journal = {Cladistics},
year = {2026},
doi = {10.1111/cla.70079}
}
EUVIMED