NCHB: A method for constructing rooted phylogenetic networks from rooted triplets based on height function and binarization

Information content of trees: three-taxon statements, inference rules and dependency

The three-taxon statement is the fundamental unit of rooted trees in cladistics, stating that for three terminal taxa, two are more related to each other than to a third. Because of their fundamental role in phylogenetics, three-taxon statements are present in methodological research of various disciplines in evolutionary biology; for example consensus methods, supertree methods, species-tree methods, distance metrics and even phylogenetic reconstruction. However, three-taxon statement methods are subject to important flaws related to information redundancy. Here we aim to study the behaviour of three-taxon statements and the interactions among them in order to enhance their performance in evolutionary studies. We show how specific interactions between three-taxon statements are responsible for the emergence of redundancy and dependency within trees, and how they can be used for the improvement of weighting procedures. Our proposal is subsequently tested empirically in the supertree framework using simulations. We show that three-taxon statements using fractional weights perform much better than classical methods such as MRP (matrix representation with parsimony) or methods using unweighted statements. Our study shows that appropriate fractional weighting of three-taxon statements is of critical importance for removing redundancy in any method using them, such as in consensus, supertrees, distance metrics, and phylogenetic or biogeographical analyses.

CBTH: A New Algorithm for Maximum Rooted Triplets Consistency Problem

Background:

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

Objectives:

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.

Materials and Methods:

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.

Results:

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

Conclusion:

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

Netcombin: An algorithm for constructing optimal phylogenetic network from rooted triplets

Phylogenetic networks construction is one the most important challenge in phylogenetics. These networks can present complex non-treelike events such as gene flow, horizontal gene transfers, recombination or hybridizations. Among phylogenetic networks, rooted structures are commonly used to represent the evolutionary history of a species set, explicitly. Triplets are well known input for constructing the rooted networks. Obtaining an optimal rooted network that contains all given triplets is main problem in network construction. The optimality criteria include minimizing the level or the number of reticulation nodes. The complexity of this problem is known to be NP-hard. In this research, a new algorithm called Netcombin is introduced to construct approximately an optimal network which is consistent with input triplets. The innovation of this algorithm is based on binarization and expanding processes. The binarization process innovatively uses a measure to construct a binary rooted tree T consistent with the approximately maximum number of input triplets. Then T is expanded using a heuristic function by adding minimum number of edges to obtain final network with the approximately minimum number of reticulation nodes. In order to evaluate the proposed algorithm, Netcombin is compared with four state of the art algorithms, RPNCH, NCHB, TripNet, and SIMPLISTIC. The experimental results on simulated data obtained from biologically generated sequences data indicate that by considering the trade-off between speed and precision, the Netcombin outperforms the others.