Distributed Modified Extremal Optimization using Island Model for Reducing Crossovers in Reconciliation Graph

摘要

To determine the mechanism of molecular evolution, molecular biologists need to carry out reconciliation work.In reconciliation work, they compare the relation between twoheterogeneous phylogenetic trees and the relation between aphylogenetic tree and a taxonomic tree are compared. Phylogenetic trees and taxonomic trees are referred to as ordered treesand a reconciliation graph is constructed from two orderedtrees. In the reconciliation graph, the leaf nodes of the twoordered trees face each other. Furthermore, leaf nodes with thesame label name are connected to each other by an edge. Tocarry out reconciliation work efficiently, it is necessary to findthe state with the minimum number of crossovers of edgesbetween leaf nodes. Reducing crossovers in a reconciliationgraph is the combinatorial optimization problem that finds thestate with the minimum number of crossovers. In this paper,we propose a novel bio-inspired heuristic called distributedmodified extremal optimization (DMEO) using the island model.This heuristic is a hybrid of population-based modified extremaloptimization (PMEO) and the distributed genetic algorithmusing the island model that is used for reducing crossovers ina reconciliation graph. We have evaluated DMEO using actualdata sets. DMEO shows better performance compared withPMEO.