Speeding up iterative applications of the BUILD supertree algorithm

Benjamin D Redelings; Mark T Holder

doi:10.7717/peerj.16624

Speeding up iterative applications of the BUILD supertree algorithm

PeerJ. 2024 Jan 2:12:e16624. doi: 10.7717/peerj.16624. eCollection 2024.

Authors

Benjamin D Redelings^{1

2

3}, Mark T Holder^{3

4}

Affiliations

¹ Biology Department, Duke University, Durham, NC, United States of America.
² Ronin Institute, Durham, NC, United States of America.
³ Ecology and Evolutionary Biology, University of Kansas, Lawrence, KS, United States of America.
⁴ Biodiversity Institute, University of Kansas, Lawrence, KS, United States of America.

Abstract

The Open Tree of Life (OToL) project produces a supertree that summarizes phylogenetic knowledge from tree estimates published in the primary literature. The supertree construction algorithm iteratively calls Aho's Build algorithm thousands of times in order to assess the compatability of different phylogenetic groupings. We describe an incrementalized version of the Build algorithm that is able to share work between successive calls to Build. We provide details that allow a programmer to implement the incremental algorithm BuildInc, including pseudo-code and a description of data structures. We assess the effect of BuildInc on our supertree algorithm by analyzing simulated data and by analyzing a supertree problem taken from the OpenTree 13.4 synthesis tree. We find that BuildInc provides up to 550-fold speedup for our supertree algorithm.

Keywords: Build algorithm; Optimization; Phylogenetics; Supertree.

2024 Redelings and Holder.

MeSH terms

Algorithms*
Knowledge*
Phylogeny

Grants and funding

This work was supported by the National Science Foundation of the United States of America (Division of Biological Infrastructure Award No. 1759838). The funders had no role in study design, data collection and analysis, decision to publish, or preparation of the manuscript.