A hybrid beam search framework with deep representation learning for the multiple longest common subsequence problem

Abstract

The Multiple Longest Common Subsequence (MLCS) problem is a classical computational challenge in biological sequence analysis and comparative genomics. Existing approximate methods often lack effective mechanisms for incorporating contextual information from local sequence fragments when processing complex multi-sequence biological data, which may cause promising candidate paths to be overlooked in the search space and make it difficult to achieve a good balance between computational efficiency and solution quality. We propose a hybrid beam search framework enhanced by deep representation learning, which consists of three core modules. First, a lightweight Transformer encoder is combined with contrastive learning to perform representation learning on local sequence fragments. Second, a non-dominated filtering strategy and a dual-criterion evaluation mechanism are introduced during candidate-path expansion to screen and evaluate search branches. Finally, a multidimensional scoring model is constructed to rank candidate paths and guide beam-search pruning. Experiments were conducted on randomly simulated DNA datasets and real biological sequence fragments obtained from NCBI. The real datasets include bacteriophage sequences with relatively concentrated host backgrounds, as well as heterogeneous viral sequences from different viral taxa and sources. The experimental results show that, under different sequence-length and sequence-number settings, the proposed method generally obtains longer common subsequences than representative approximate algorithms while maintaining good computational efficiency. In addition, on small-scale instances for which exact solutions can be obtained, the approximate solutions produced by the proposed method remain close to the exact optima. By combining the context-based sequential representation information with heuristic search strategies, this study proposes a hybrid search framework for solving the MLCS problem. Experimental results show that the proposed method can obtain high-quality approximate solutions across different sequence scales and characteristics while maintaining good computational efficiency.