The Largest Compatible Subset Problem for Phylogenetic Data

Details The Largest Compatible Subset Problem for Phylogenetic Data The Largest Compatible Subset Problem for Phylogenetic Data

2004-05-06

arxiv.org/abs/cs/0405025v1

Genetic and Evolutionary Computation 2004 Conference (GECCO-2004), Bird-of-a-feather Workshop On Application of Hybrid Evoluti

Computer Science

Artificial Intelligence

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

The Largest Compatible Subset Problem for Phylogenetic Data does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with The Largest Compatible Subset Problem for Phylogenetic Data, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and The Largest Compatible Subset Problem for Phylogenetic Data will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-711919