An Efficient Parallel and Adaptive Algorithm for Large-Scale Multiple Longest Common Subsequence Problems

The Multiple Longest Common Subsequence (MLCS) Problem is to find one or more longest common subsequences from multiple (≥ 3) strings. However, as the scale of the sequences increases, the time and space consumption of traditional algorithms increases drastically. To effectively address large-scale MLCS problems, this paper proposes a parallel and adaptive algorithm that is highly efficient in both space and time called PAST_MLCS. The algorithm primarily comprises three key parts: 1. Estimation of the lower bound based on the sum of coordinates and the sum of absolute deviations; 2. An efficient cached upper bound strategy based on a dynamic hash table; 3. A hierarchical parallel Directed Acyclic Graph (DAG) construction technique. By integrating the above three optimizations, this algorithm significantly reduces the time and space complexity in solving large-scale MLCS problems. Experimental results on biological DNA sequences show that the proposed algorithm achieves an order-of-magnitude improvement in time efficiency over current state-of-the-art methods when handling large-scale sets of 50,000 sequences, demonstrating its superior capability for complex MLCS problems.