Previous [ 1 ] [ 2 ] [ 3 ] [ 4 ] [ 5 ] [ 6 ] [ 7 ] [ 8 ] [ 9 ] [ 10 ] [ 11 ]

@

Journal of Information Science and Engineering, Vol. 20 No. 1, pp. 181-190 (January 2004)

Constructing Evolutionary Trees From Rooted Triples*

Bang Ye Wu
Department of Computer Science and Information Engineering
Shu-Te University
Kaohsiung, 824 Taiwan

In this paper, we propose a new heuristic algorithm for the maximum consensus tree of rooted triples. By means of the experimental results, we show that the algorithm is better than the three previous heuristics and runs in a reasonable amount of time. Furthermore, using the algorithm, it is possible to achieve a trade-off between the running time and the quality of the solution. We also investigate the computational complexity of the maximum compatible set problem. We show that it is NP-hard to find the maximum vertex set compatible with given rooted triples.  

Keywords:  computational biology, evolutionary tree, heuristic algorithm, NP-hard, consensus tree

Full Text () Retrieve PDF document (200401_10.pdf)

Received January 31, 2003; accepted July 4, 2003.
Communicated by Ming-Syan Chen.
* A preliminary version of this paper was presented at the 2002 International Computer Symposium, 2002.