The Largest Compatible Subset Problem for Phylogenetic Data
  The phylogenetic tree construction is to infer the evolutionary relationship
between species from the experimental data. However, the experimental data are
often imperfect and conflicting each others. Therefore, it is important to
extract the motif from the imperfect data. The largest compatible subset
problem is that, given a set of experimental data, we want to discard the
minimum such that the remaining is compatible. The largest compatible subset
problem can be viewed as the vertex cover problem in the graph theory that has
been proven to be NP-hard. In this paper, we propose a hybrid Evolutionary
Computing (EC) method for this problem. The proposed method combines the EC
approach and the algorithmic approach for special structured graphs. As a
result, the complexity of the problem is dramatically reduced. Experiments were
performed on randomly generated graphs with different edge densities. The
vertex covers produced by the proposed method were then compared to the vertex
covers produced by a 2-approximation algorithm. The experimental results showed
that the proposed method consistently outperformed a classical 2- approximation
algorithm. Furthermore, a significant improvement was found when the graph
density was small.
