Speeding up iterative applications of the BUILD supertree algorithm

Area of Science:

• Computational Biology
• Phylogenetics
• Bioinformatics

Background:

• The Open Tree of Life (OToL) project aims to synthesize global phylogenetic knowledge.
• Supertree construction involves iteratively assessing the compatibility of phylogenetic groupings using algorithms like Aho's Build.
• Existing methods require thousands of Build algorithm calls, leading to significant computational time.

Purpose of the Study:

• To describe and implement an incremental version of the Build algorithm (BuildInc).
• To improve the efficiency of supertree construction for the Open Tree of Life project.
• To provide practical details for implementing BuildInc in software.

Main Methods:

• Development of an incrementalized Build algorithm (BuildInc) that reuses computations.
• Implementation details including pseudo-code and data structure descriptions.
• Assessment of BuildInc's performance using simulated data and a real-world OToL synthesis tree.

Main Results:

• BuildInc significantly reduces computational time by sharing work between successive Build calls.
• Performance analysis demonstrated up to a 550-fold speedup for the supertree algorithm.
• The incremental approach is effective for large-scale phylogenetic synthesis.

Conclusions:

• The incremental Build algorithm (BuildInc) offers a substantial performance improvement for phylogenetic supertree construction.
• BuildInc enhances the scalability and efficiency of projects like the Open Tree of Life.
• This work provides a valuable optimization for computational phylogenetics.