On the Application of Evolutionary Algorithms to the Consensus Tree Problem

C. Cotta

Evolutionary Computation in Combinatorial Optimization, J. Gottlieb, G. Raidl (eds.), Lecture Notes in Computer Science 3448, pp. 58-67, Springer-Verlag Berlin, 2005
(EvoCOP'05 best paper award)

© Springer-Verlag Berlin Heidelberg 2005. All rights reserved.


Computing consensus trees amounts to finding a single tree that summarizes a collection of trees. Three evolutionary algorithms are defined for this problem, featuring characteristics of genetic programming (GP), evolution strategies (ES) and evolutionary programming (EP) respectively. These algorithms are evaluated on a benchmark composed of phylogenetic trees computed from genomic data. The GP-like algorithm is shown to provide better results than the other evolutionary algorithms, and than two greedy heuristics defined ad hoc for this problem.

Download BibTEX entry
Download PDF version (177K)
[Back to publications page].