Cladistics Экология, эволюция, поведение и систематика

Cost estimation heuristics for phylogenetic network construction and refinement

Ward C. Wheeler
Wiley · 2026-11-20 · DOI 10.1111/cla.70079

Аннотация

Abstract 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.

Читать у издателя →