New heuristics for rooted triplet consistency (Q1736566)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | New heuristics for rooted triplet consistency |
scientific article |
Statements
New heuristics for rooted triplet consistency (English)
0 references
26 March 2019
0 references
Summary: 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 \textit{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(m n^3)\) time and, on average, performs better than any other previously known algorithms for this problem.
0 references
phylogenetic tree
0 references
rooted triplet
0 references
consensus tree
0 references
approximation algorithm
0 references
0 references
0 references
0 references