Heuristic method finds longer shared sequences faster for many inputs
A Configurable Heuristic for the MLCS Problem
Distributed, Parallel, and Cluster Computing
Summary
Finding the longest shared pattern in many sequences is a tough problem that gets very slow or uses too much memory. The authors present a method called ARP that builds solutions step by step, swaps parts to get better answers, and focuses on likely pattern groups. Users can control how much the method tries to improve versus how fast it runs. Tests show ARP can find longer shared patterns faster than older approaches and matches the best advanced methods while running quicker.
What this means in practice
- •For bioinformatics engineers: Speed up the alignment and comparison of large biological sequence sets by using ARP to find longer common subsequences with less memory.
- •For software developers in pattern matching: Integrate ARP heuristic to efficiently detect long shared patterns in large collections of text or data sequences.
Authors
Farhana Akter Tumpa, Rebin Silva Valan Arasu, Rajiv Gupta
Abstract
Motivation: The Multiple Longest Common Subsequence (MLCS) problem for an arbitrary number of sequences is an NP-hard problem in sequence analysis. Existing exact algorithms based on dynamic programming or MLCS-DAG pruning rapidly exhaust memory as sequence lengths and set sizes grow, while heuristic and hyper-heuristic approaches compromise solution quality and require heavy parameter tuning, respectively. Results: This paper presents the ARP heuristic that, for a given primary sequence, performs three key actions: (i) Adding-$Δ$s, which incrementally builds a solution by adding subsequences, called $Δ$s, of the primary sequence to an initial solution; (ii) Replacing-Subsequences, which enhances the diversity of the solution set via targeted replacement of subsequences common to all solutions; and (iii) Prioritizing groups of characters from the primary sequence that are likely to appear together in longer common subsequences. ARP allows the user to configure the degree of Replacements and Prioritization actions for carrying out quality-runtime tradeoff. Empirical evaluations on both synthetic and biological sequence sets demonstrate that ARP's fastest configuration AOnly finds significantly longer common subsequences than the BNMAS classical heuristic and its aggressive configuration attains solution quality comparable to state-of-the-art hyper-heuristic (UB-HH) while running 1.1$\times$-1.7$\times$ faster.