finding consensus trees by evolutionary, variable neighborhood search, and hybrid algorithms
The consensus tree problem arises in the domain of phylogenetics and seeks to find for a given collection of trees a single tree best representing it. Usually, such a tree collection is obtained by biologists for a given taxa set either via different phylogenetic inference methods or multiple applications of a non-deterministic procedure. There exist various consensus methods which often have the drawback of being very strict, limiting the resulting consensus tree in terms of its resolution and/or precision. A reason for this typically is the coarse granularity of the tree metric used. To find fully resolved (binary) consensus trees of high quality, we consider the fine-grained TreeRank similarity measure and extend a previously presented evolutionary algorithm (EA) to a memetic algorithm (MA) by including different variants of local search using neighborhoods based on moves of single taxa as well as subtrees. Furthermore, we propose a variable neighborhood search (VNS) with an embedded variable neighborhood descent (VND) based on the same neighborhood structures. Finally sequential and intertwined combinations of the EA and MA with the VNS/VND are investigated. We give results on real and artificially generated data indicating in particular the benefits of the hybrid methods.
variable neighborhood search consensus tree problem phylogenetics memetic algorithm hybrid methods