DOI: 10.5176/978-08-8227-3_BICB2011-24
Authors: Soheil Jahangiri Tazehkand, Seyed Naser Hashemi and Hadi Poormohammadi
Abstract:
An evolutionary tree (phylogenetic tree) is a rooted tree, that models the evolutionary process history of currently living species, in which, leaves are labeled by species. The problem is to find the maximum consensus evolutionary tree from a set of given rooted triplets. A rooted triplet is a rooted binary tree on three leaves and shows the evolutionary relationship of the corresponding three species. The mentioned
problem is known to be APX-hard. In this paper, we present two new heuristic algorithms. For a given set of m triplets on n species, the first algorithm runs in O(mn2) which is faster than any other previously known algorithm, although, the outcome is less satisfactory. The second algorithm runs in O(mn3) and in average performs better than any other previously known approximation algorithm.
Keywords: component; phylogenetics; evolutionary tree; rooted triplet; consensus tree; hueristic algorithm
Updating...