CBTH: a New Algorithm for MRTC Problem

Phylogenetics is a branch of bioinformatics that studies and models the evolutionary relationships between currently living species [1]. A phylogenetic tree is the simplest possible model in which leaves are disticnctly labeled by species. Rooted triplets are one of the most important inputs for constructing rooted phylogenetic trees [2]. A rooted triplet is a rooted binary tree with tree leaves. A rooted triplet is the simplest possible rooted tree that contains information and explains the bilogical relation between three species. The problem of constructing a rooted phylogenetic tree that contains the maximum number of given rooted triplets is a maximization problem and is known as MRTC problem [3]. The main challenge in phylogenetics is that MRTC is NP-hard [3]. Therefore, 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 improvement of CBTH, the CBTH is compared with TRH [4] 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 without changing time complexity performance.

کلیدواژه ها:

Biological sequence ، MRTC problem ، Rooted phylogenetic tree ، Rooted triplet ، Height function