Modified EO-based evolutionary algorithm for reducing crossovers of reconciliation graph

To solve the mechanism of molecular evolution, molecular biologists need reconciliation work for comparing relations between two heterogeneous trees. In reconciliation work, a reconciliation graph is made from two heterogeneous trees which are considered to be ordered trees. In order to efficiently achieve reconciliation work, it is necessary to find the state with the minimum crossovers of edges, if two leaf nodes with same label name in a reconciliation graph are connected each other. Reducing crossovers in a reconciliation graph is defined as a combinatorial optimization problem, because the number of crossovers is determined by combination of orders of leaf nodes. This paper proposes a novel modified EO(Extremal Optimization)-based evolutionary algorithm (MEOEA) for reducing crossovers in a reconciliation graph. The proposed evolutionary algorithm is a population-based evolutionary algorithm based on MEO. We evaluated MEOEA using actual data sets. The experiment results show that MEOEA is good performance compared with MEO.