Speeding up iterative applications of the BUILD supertree algorithm

Abstract

The Open Tree of Life (OToL) project produces a supertree that summarizes phylogenetic knowledge from tree estimates published in the primary literature. The supetree construction algorithm iteratively calls Ahos 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 BO_SCPLOWUILDC_SCPLOWIO_SCPLOWNCC_SCPLOW, including pseudo-code and a description of data structures. We assess the effect of BO_SCPLOWUILDC_SCPLOWIO_SCPLOWNCC_SCPLOW on our supertree algorithm by analyzing simulated data and by analyzing a supertree problem taken from the OToL 13.4 synthesis tree. We find that BO_SCPLOWUILDC_SCPLOWIO_SCPLOWNCC_SCPLOW provides up to 550-fold speedup for our supertree algorithm.