An Adaptive CMSA for Solving the Longest Filled Common Subsequence Problem with an Application in Audio Querying

Marko Djukanović, Christian Blum, Aleksandar Kartelj, Ana Nikolikj, Günther R. Raidl · 2025

Read An Adaptive CMSA for Solving the Longest Filled Common Subsequence Problem with an Application in Audio Querying by Marko Djukanović, Christian Blum, Aleksandar Kartelj, Ana Nikolikj, Günther R. Raidl (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-12261.txt.

Introduction

Matching a degraded song clip to its source is one face of a hard pattern problem called the longest filled common subsequence problem. Marko Djukanovic and four co-authors attack it in 2025 with an adaptive method that builds candidate solutions, merges the best parts, solves the merged piece exactly, and adapts.

Older test sets were too small to separate good algorithms from lucky ones, so the team built larger benchmarks. Their method matched the proven optimum on nearly all of the more than fifteen hundred instances where the optimum is known. A case study then applies the machinery to identifying songs from damaged audio energy profiles.

Catalog record

CREATORMarko Djukanović, Christian Blum, Aleksandar Kartelj, Ana Nikolikj, Günther R. Raidl
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE83 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2509-12261

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

An Adaptive CMSA for Solving the Longest Filled Common Subsequence Problem with an Application in Audio Querying Marko Djukanović, Christian Blum, Aleksandar Kartelj, Ana Nikolikj, Günther R. Raidl Abstract This paper addresses the Longest Filled Common Subsequence (LFCS) problem, a challenging NP-hard problem with applications in bioinformatics, including gene mutation prediction and genomic data reconstruction. Existing approaches, including exact, metaheuristic, and approximation algorithms, have primarily been evaluated on small-sized instances, which offer limited insights into their scalability. In this work, we introduce a new benchmark dataset with significantly larger instances and demonstrate that existing datasets lack the discriminative power needed to meaningfully assess algorithm performance at scale. To solve large instances efficiently, we utilize an adaptive Construct, Merge, Solve, Adapt (CMSA) framework that iteratively generates promising subproblems via component-based construction and refines them using feedback from prior iterations. Subproblems are solved using an external black-box solver. Extensive experiments on both standard and newly introduced benchmarks show that the proposed adaptive CMSA achieves state-of-the-art performance, outperforming five leading methods. Notably, on 1,510 problem instances with known optimal solutions, our approach solves 1,486 of them—achieving over 99.9% optimal solution quality and demonstrating exceptional scalability. We additionally propose a novel application of LFCS for song identification from degraded audio excerpts as an engineering contribution, which uses real-world energy-profile instances from popular music. Finally, we conducted an empirical explainability analysis to identify critical feature combinations influencing algorithm performance, i.e., the key problem features contributing to success or failure of the approaches across different instance types are revealed. 1 Introduction Strings are fundamental data structures in many programming languages, widely used to model sequences such as DNA, RNA, protein molecules, and even time series. A string s is defined as a finite sequence of characters drawn from a (typically finite) alphabet \Sigma . A key concept in analyzing similarities between strings is a subsequence —a sequence derived from a string by deleting zero or more characters without changing the order of remaining characters. Detecting structural similarities among multiple strings is central to both stringology and molecular biology. One of the most widely used tools for this purpose is the identification of common subsequences , which can help uncover relationships among sequences and reveal meaningful biological or structural patterns, such as mutations. Advances in genome sequencing have further enabled the analysis and reconstruction of genomic data using such techniques. A core optimization problem in this context is the Longest Common Subsequence (LCS) problem [ 1 ] , defined as follows: Given a set of input strings, find a longest sequence that is a subsequence of each of the input strings. The LCS problem has broad applications in computational biology [ 2 ] , file plagiarism detection, data compression [ 3 , 4 ] , text editing [ 5 ] , and spatial data analysis, such as identifying road intersections from GPS traces [ 6 ] . Practical applications include file comparison tools like the Unix diff command [ 7 ] and revision control systems such as Git . To solve the LCS problem when the number of input strings m is fixed, polynomial-time algorithms based on dynamic programming (DP) have been proposed [ 8 ] . However, their practical applicability remains limited due to the rapidly growing computational complexity in respect to the number of strings and the strings’ lengths. To address this, several advanced metaheuristics have been developed to solve LCS variants more efficiently in practice. State-of-the-art methods are based on effectively exploring the state space graph [ 9 , 10 , 11 ] , combined with carefully crafted, problem-specific search guidance strategies. These methods have been tested on both artificial and real benchmark datasets, revealing the strengths and drawbacks of these approaches on various instance distributions. In parallel, exact approaches have advanced through the use of best-first search frameworks and their extensions to hybrid anytime algorithms [ 12 ] . Over the past two decades, practical variants of the LCS problem have gained increasing attention in the research community. Notable examples include the longest common arc subsequence problem [ 13 ] , the repetition-free LCS problem [ 14 ] , and the constrained LCS problem [ 15 ] , among many others. More recently, research efforts have turned toward understanding gene mutations and reconstructing genomic data, aiming to uncover the evolutionary history of molecular sequences. This goal is formalized by the Longest Filled Common Subsequence (LFCS) problem, which is inspired by another real-world application, the scaffold filling problem [ 16 , 17 ] from genomic data reconstruction. The LFCS problem (LFCSP) was introduced by Castelli et al. [ 18 ] . Briefly, the problem involves two sequences: the original sequence and one that requires repair. Additionally, a multiset of symbols is provided, which can be used for the repair. The goal is to insert some (or all) of these symbols into the second, shorter, sequence to maximize its similarity to the original sequence. The application of LFCSP can clearly extend towards a broader range of research areas involving sequential data that may suffer from information loss, such as audio querying or corrupted text recovery [ 19 ] . Concerning the methodological appraoches to solve the LFCSP from the literature, in [ 18 ] the authors proposed two \frac{3}{5} -approximation algorithms and gave a formal proof on the APX-hardness of the LFCSP, even when the first input string contains at most two occurrences of each symbol from the alphabet \Sigma . This result was established via a reduction from the maximum independent set problem on cubic graphs. The second notable work by Mincu and Popa [ 20 ] presented diverse solving approaches including an Integer Linear Programming (ILP) formulation, a randomized sampling-based method, and a local search (LS) strategy based on the classical hill-climbing. Their comparative computational study was conducted on a set of randomly generated instances. Several limitations of this earlier works remain unaddressed: 1. Scalability : Existing benchmark instances are limited to small and medium-sized problems, all of which can be solved efficiently by the ILP model in a matter of seconds. As a result, the practical scalability and limitations of these methods have not been fully thoroughly explored. Moreover, the current literature lacks real-world problem instances, or at least instances with characteristics appearing in real-world applications. 2. Heuristic Potential : The heuristic methods developed stand far from leveraging advanced search operators or learning mechanisms commonly used in modern optimization, leaving room for significant methodological improvements for solving the tackled problem. 3. Explainability : There is a lack of systematic analysis to explain the performance of algorithms based on instance characteristics or internal algorithmic behaviors—a growing area of interest in optimization research. In this article, we address these gaps through the following contributions: 1. A state-of-the-art ILP-based metaheuristic approach is proposed for solving the LFCSP. The method is based on an adaptive variant of the Construct, Merge, Solve, Adapt (CMSA) framework [ 21 , 22 ] . 2. Two new benchmark datasets are introduced. The first one consists of dozens of synthetic instances which are significantly larger than the instances from the existing benchmarks. This allows for a deeper investigation into the scalability and robustness of both existing and new solving approaches. The

Read the complete text