A New Distributed Modified Extremal Optimization using Tabu Search Mechanism for Reducing Crossovers in Reconciliation Graph and Its Performance Evaluation

摘要

To determine the mechanism of molecular evolution, identifying the differences between two heterogeneous phylogenetic trees and the between a phylogenetic tree and a taxonomic tree is an important task for molecular biologists. Phylogenetic trees and taxonomic trees are referred to as ordered trees. In the process of comparing ordered trees, a graph, which is called a reconciliation graph, is created using the ordered trees. In the reconciliation graph, the leaf nodes of the two ordered trees face each other. Furthermore, leaf nodes with the same label name are connected to each other by an edge. It is difficult to compare two heterogeneous ordered trees, if there are many crossed edges between leaf nodes in the reconciliation graph. Therefore the number of crossovers in the reconciliation graph should be decreased; then reducing crossovers in a reconciliation graph is the combinatorial optimization problem that finds the state with the minimum number of crossovers. Several heuristics have been proposed for reducing crossovers in a reconciliation graph. One of the most successful heuristics is the modified extremal-optimizationbased heuristics (the MEO-based heuristics). In this paper, we propose a novel MEO-based heuristic called distributed modified extremal optimization with tabu lists (DMEOTL). This heuristic is a hybrid of distributed modified extremal optimization (DMEO) and the tabu search mechanism. We have evaluated DMEOTL using actual data sets. DMEOTL shows better performance compared with DMEO.