The Largest Compatible Subset Problem for Phylogenetic Data

Simple item page
dc.creatorAuyeung, Andy
dc.creatorAbraham, Ajith
dc.date2004-05-06
dc.date.accessioned2026-07-07T03:21:13Z
dc.date.available2026-07-07T03:21:13Z
dc.descriptionThe 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.
dc.identifierhttps://arxiv.org/abs/cs/0405025
dc.identifierhttp://arxiv.org/abs/cs/0405025
dc.identifierGenetic and Evolutionary Computation 2004 Conference (GECCO-2004), Bird-of-a-feather Workshop On Application of Hybrid Evolutionary Algorithms to Complex Optimization Problems, Springer Verlag Germany, 2004 (forth coming)
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/32113
dc.subjectArtificial Intelligence
dc.subjectI.2.0
dc.titleThe Largest Compatible Subset Problem for Phylogenetic Data
dc.typetext

Files

Collections

arXiv