Longest Filled Common Subsequence for Song Identification from Degraded Audio via Construct--Merge--Solve--Adapt Optimization

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 instances, which provide limited insight 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 set of large-sized instances prove that the designed adaptive CMSA achieves state-of-the-art performance, outperforming four known approaches. Notably, among 1,510 problem instances with known optimal solutions, our approach matches the proven optimum on 1,486 instances---corresponding to 98.4\% of these instances. These results demonstrate substantially improved scalability on large problem instances. As an engineering contribution, we propose a novel application of LFCS to song identification from degraded audio excerpts, using real-world energy-profile instances derived from popular music. Finally, we conduct an empirical explainability analysis to identify critical feature combinations influencing algorithm performance, revealing the key problem features associated with the success or failure of the approaches across different instance types.

60 pages, 9 figures