CBTH: A New Algorithm for Maximum Rooted Triplets Consistency Problem

Area of Science:

• Bioinformatics
• Computational Biology
• Evolutionary Biology

Background:

• Phylogenetics models evolutionary relationships between species using phylogenetic trees.
• Rooted triplets are crucial inputs for constructing rooted phylogenetic trees, representing relationships among three species.
• The maximum rooted triplets consistency (MRTC) problem aims to build trees maximizing input triplet compatibility.

Purpose of the Study:

• Introduce an efficient algorithm, CBTH, to address the NP-hard MRTC problem.
• Improve the consistency between input rooted triplets and the final phylogenetic tree.
• Provide a high-performance solution for constructing rooted phylogenetic trees.

Main Methods:

• Developed a novel algorithm named CBTH specifically for the MRTC problem.
• Implemented CBTH to enhance the consistency of rooted triplets within phylogenetic tree construction.
• Evaluated CBTH's performance against existing methods using biological data.

Main Results:

• CBTH demonstrates superior performance compared to the TRH algorithm in terms of rooted triplet consistency.
• The new CBTH algorithm achieves this improved consistency within a similar time complexity.
• Experimental results validate CBTH's effectiveness on biological datasets.

Conclusions:

• The CBTH algorithm offers a high-performance solution for the MRTC problem.
• CBTH effectively improves rooted phylogenetic tree construction without compromising computational efficiency.
• This method represents a significant advancement in handling rooted triplet consistency in phylogenetics.