DIGITAL.CSIC. Repositorio Institucional del CSIC
Publicación
Contribución de congreso (ConferenceOutput)
A hybrid evolutionary algorithm based on solution merging for the longest arc-preserving common subsequence problem
The longest arc-preserving common subsequence problem is an NP-hard combinatorial optimization problem from the field of computational biology. This problem finds applications, in particular, in the comparison of art-annotated ribonucleic acid (RNA) sequences. In this work we propose a simple, hybrid evolutionary algorithm to tackle this problem. The most important feature of this algorithm concerns a crossover operator based on solution merging. In solution merging, two or more solutions to the problem are merged, and an exact technique is used to find the best solution within this union. It is experimentally shown that the proposed algorithm outperforms a heuristic from the literature. © 2017 IEEE., This work was funded by project TIN2012-37930-C02-02 (Spanish Ministry for Economy and Competitiveness, FEDER funds from the European Union) and project SGR 2014-1034 (AGAUR, Generalitat de Catalunya). Our experiments have been executed in the High Performance Computing environment managed by the RDlab at the Technical University of Barcelona (http://rdlab.cs.upc.edu) and we would like to thank them for their support., Peer Reviewed