A Hybrid Evolutionary Algorithm Based on Solution Merging for the\n Longest Arc-Preserving Common Subsequence Problem

2017/02/01 by Christian Blum, Blum, Christian, María J. Blesa +1
Biochemistry, Genetics and Molecular Biology · #Artificial Intelligence (cs.AI) #FOS: Computer and information sciences #Genomics and Phylogenetic Studies #Machine Learning in Bioinformatics #RNA and protein synthesis mechanisms

paper · pdf · doi:10.48550/arxiv.1702.00318

openalex publication_date 2017/02/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

The longest arc-preserving common subsequence problem is an NP-hard\ncombinatorial optimization problem from the field of computational biology.\nThis problem finds applications, in particular, in the comparison of\narc-annotated Ribonucleic acid (RNA) sequences. In this work we propose a\nsimple, hybrid evolutionary algorithm to tackle this problem. The most\nimportant feature of this algorithm concerns a crossover operator based on\nsolution merging. In solution merging, two or more solutions to the problem are\nmerged, and an exact technique is used to find the best solution within this\nunion. It is experimentally shown that the proposed algorithm outperforms a\nheuristic from the literature.\n

Related

• A Learning Search Algorithm for the Restricted Longest Common Subsequence Problem
• A Biased Random Key Genetic Algorithm for Solving the Longest Run Subsequence Problem
• Fast Arc-Annotated Subsequence Matching in Linear Space
• Algorithms for the uniqueness of the longest common subsequence
• Efficient algorithms for the longest common subsequence in k-length substrings