One small step for a man
One Giant leap for the mankind

There is no wealth like Knowledge
                            No Poverty like Ignorance
Journal of Emerging Trends in Computing and Information Sciences Logo

Journal of Emerging Trends in Computing and Information Sciences >> Call for Papers Vol. 8 No. 3, March 2017

Journal of Emerging Trends in Computing and Information Sciences

A New Heuristic Algorithm for MRTC Problem

Full Text Pdf Pdf
Author Hadi Poormohammadi
ISSN 2079-8407
On Pages 1037-1041
Volume No. 3
Issue No. 7
Issue Date July 01, 2012
Publishing Date July 01, 2012
Keywords Rooted phylogenetic tree, Rooted triplet, Heuristic algorithm, Height function, Consistency


Abstract

A rooted phylogenetic tree is a rooted tree which represents the evolutionary history of currently living species. A rooted binary tree on three leaves is a rooted triplet. The problem of determining whether there exists a rooted phylogenetic tree that contains all of the rooted triplets is polynomial solvable, while the problem of finding a rooted phylogenetic tree that contains the maximum number of rooted triplets is known to be NP-hard. This maximization problem is known as the Maximum Rooted Triplets Consistency (MRTC) problem. In this paper we present a new heuristic algorithm for this problem based on the concept of the height function of a tree. We study the performance of our algorithm from both simulation and theoretical viewpoints.  

Back

Seperator
    Journal of Computing | Call for Papers (CFP) | Journal Blog | Journal of Systems and Software | ARPN Journal of Science and Technology | International Journal of Health and Medical Sciences | International Journal of Economics, Finance and Management     
Copyrights
© 2015 Journal of Computing