New Heuristics for Rooted Triplet Consistency

Algorithms

Soheil Jahangiri¹  Seyed Naser Hashemi¹ 

[1] ¹Amirkabir University of Technology (Tehran Polytechnic), 424 Hafez Ave, Tehran, Iran

关键词: phylogenetic tree;    rooted triplet;    consensus tree;    approximation algorithm;   

DOI  :  10.3390/a6030396

来源: mdpi

【 摘 要 】

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 + α(n)n²) time, where α(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³) time and, on average, performs better than any other previously known algorithms for this problem.

【 授权许可】

CC BY   
This is an open access article distributed under the Creative Commons Attribution License (CC BY) which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.