CBTH: A New Algorithm for Maximum Rooted Triplets Consistency Problem

Phylogenetics is a branch of bioinformatics that studies and models the evolutionary relationships between currently living species. A phylogenetic tree is the simplest possible model in which leaves are distinctly labeled by species. Rooted triplets are one of the most important inputs for constructing rooted phylogenetic trees. A rooted triplet is the simplest possible rooted tree that contains information and explains the biological relation between three species.

The problem of constructing a rooted phylogenetic tree that contains the maximum number of input triplets is a maximization problem and is known as the maximum rooted triplets consistency (MRTC) problem. MRTC problem is an NP-hard problem, so there is no any polynomial exact solution for it. The goal is to introduce a new efficient method to solve MRTC.

In this research, a new algorithm called CBTH, is introduced innovatively for MRTC problem with the goal to improve the consistency of input rooted triplets with the final rooted phylogenetic tree.

In order to show the efficiency of CBTH, the CBTH is compared with TRH on biological data. According to our knowledge, TRH is one of the best methods for MRTC problem on rooted triplets that are obtained from biological data. The Experimental results show that CBTH outperforms TRH based on rooted triplet consistency parameter in the same time order.

The introduced method (CBTH) solve MRTC problem with high performance without increasing time complexity compared to the other state of the art algorithms.