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.
| Previous | [ 1 ] | [ 2 ] | [ 3 ] | [ 4 ] | [ 5 ] | [ 6 ] | [ 7 ] | [ 8 ] | [ 9 ] | [ 10 ] | [ 11 ] |
¡@
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
Received January 31, 2003; accepted July 4, 2003.
Retrieve
PDF document (200401_10.pdf)
Communicated by Ming-Syan Chen.
* A preliminary version of
this paper was presented at the 2002 International Computer Symposium, 2002.