_Algorithms_**2013**, \(6\), 396-406; doi:10.3390/a6030396  
_algorithms_  
**ISSN 1999-4893**  
www.mdpi.com/journal/algorithms  
**New Heuristics for Rooted Triplet Consistency \(\dagger\)**  
**[PERSON] \({}^{1,2,*}\), [PERSON] \({}^{1}\) and [PERSON] \({}^{3}\)**  
\({}^{1}\) Amirkabir University of Technology (Tehran Polytechnic), 424 Hafez Ave, Tehran, Iran; E-Mail: [EMAIL_ADDRESS]  
\({}^{2}\) Bioinformatics Group, School of Computer Science, Institute for Research in Fundamental Sciences (IPM), Niavaran, Tehran, Iran  
\({}^{3}\) Shahid Beheshti University, Evin, Tehran 19839-63113, Iran; E-Mail: [EMAIL_ADDRESS]  
\(\dagger\) An extended abstract of this article has appeared in the proceedings of the Annual International Conference on Bioinformatics and Computational Biology (BICB 2011) in Singapore. * Author to whom correspondence should be addressed; E-Mail: [EMAIL_ADDRESS]; Tel. : +98-936-9220139. _Received: 14 April 2013; in revised form: 26 June 2013 / Accepted: 26 June 2013 / Published: 11 July 2013_  
**Abstract:** Rooted triplets are becoming one of the most important types of input for reconstructing rooted phylogenies. A rooted triplet is a phylogenetic tree on three leaves and shows the evolutionary relationship of the corresponding three species. In this paper, we investigate the problem of inferring the maximum consensus evolutionary tree from a set of rooted triplets. This problem is known to be APX-hard. We present two new heuristic algorithms. For a given set of \(m\) triplets on \(n\) species, the _FastTree_ algorithm runs in \(O(m+\alpha(n)n^{2})\) time, where \(\alpha(n)\) is the functional inverse of Ackermann's function. This is faster than any other previously known algorithms, although the outcome is less satisfactory. The Best Pair Merge with Total Reconstruction (BPMTR) algorithm runs in \(O(mn^{3})\) time and, on average, performs better than any other previously known algorithms for this problem. **Keywords:** phylogenetic tree; rooted triplet; consensus tree; approximation algorithm
After the publication of [PERSON]'s book _On the Origin of Species by Means of Natural Selection_, the theory of evolution was widely accepted. Since then, remarkable developments in evolutionary studies brought scientists to phylogenetics, a field that studies the biological or morphological data of species to output a mathematical model, such as a tree or a network, representing the evolutionary interrelationship of species and the process of their evolution. Interestingly, phylogenetics is not only limited to biology, but may also arise anywhere that the concept of evolution appears. For example, a recent study in evolutionary linguistics employs a phylogeny inference to clarify the origin of the Indo-European language family [1]. Several approaches have been introduced to infer evolutionary relationships [2]. Among those, well-known approaches are character-based methods (e.g., maximum parsimony), distance-based methods (e.g., neighbor joining and UPGMA) and quartet-based methods (e.g., QNet). Recently, rather new approaches, namely, triplet-based methods, have been introduced. Triplet-based methods output rooted trees and networks, due to the rooted nature of triplets. A rooted triplet is a rooted unordered leaf-labeled binary tree on three leaves and shows the evolutionary relationship of the corresponding three species. Triplets can be obtained accurately using a maximum likelihood method, such as the one introduced by [PERSON] _et al._[3], or the Sibley-Ahlquist-style DNA-DNA hybridization experiments [4]. Indeed, we expect highly accurate results from triplet-based methods. However, sometimes, due to experimental errors or some biological events, such as hybridization (recombination) or horizontal gene transfer, it is not possible to reconstruct a tree that satisfies all of the input constraints (triplets). There are two ways to overcome this problem.