BCD Beam Search: considering suboptimal partial solutions in Bad Clade Deletion supertrees

Area of Science:

• Computational Biology
• Phylogenetics
• Bioinformatics

Background:

• Supertree methods reconstruct large phylogenies but struggle with contradictory input data.
• Existing methods include matrix-based approaches and graph-based minimum cut computations.
• The Bad Clade Deletion (BCD) supertree method previously combined graph cuts with matrix optimization, offering polynomial time but variable biological data quality.

Purpose of the Study:

• To enhance the Bad Clade Deletion (BCD) supertree algorithm for improved phylogenetic reconstruction accuracy.
• To address limitations in BCD supertree quality, particularly on biological datasets.
• To develop a polynomial-time supertree algorithm with superior performance.

Main Methods:

• Introduced a beam search extension to the BCD algorithm, maintaining a constant number of partial solutions.
• Implemented exact and randomized subroutines for generating suboptimal partial solutions within the beam search.
• Evaluated the enhanced algorithm's performance on simulated and biological datasets.

Main Results:

• The BCD Beam Search algorithm maintains guaranteed polynomial running time.
• Beam search consistently improved supertree quality across all datasets when retaining 25 suboptimal solutions.
• The BCD Beam Search algorithm achieved supertree quality comparable to Matrix Representation with Parsimony (MRP) and SuperFine, even for biological data.

Conclusions:

• The beam search extension significantly enhances the quality of BCD supertrees, especially for biological data.
• BCD Beam Search represents a state-of-the-art polynomial-time supertree algorithm.
• This method offers a robust and accurate solution for reconstructing large phylogenies from complex datasets.