다중 변수 간격이 있는 최장 공통 부분 수열 문제 해결에 대한 연구

On Solving the Multiple Variable Gapped Longest Common Subsequence Problem

본 논문에서는 연속된 해의 문자들 간에 유연한 간격 제약 조건을 포함하는, 고전적인 LCS(Longest Common Subsequence, 최장 공통 부분 수열) 문제의 일반화된 형태인 Variable Gapped Longest Common Subsequence (VGLCS) 문제를 다룬다. 이 문제는 분자 서열 비교에서, 잔기들 사이의 구조적 거리 제약 조건을 고려해야 할 때, 그리고 시계열 분석에서, 이벤트들이 특정 시간 지연 내에 발생해야 할 때 발생하는 문제이다. 본 연구에서는 루트 기반 상태 그래프 표현을 기반으로 하는 탐색 프레임워크를 제안하며, 이 프레임워크의 상태 공간은 일반적으로 많은 수의 루트된 상태 부분 그래프로 구성된다. 발생하는 조합적 폭발 현상에 대처하기 위해, 반복적인 빔 탐색 전략을 사용하여, 유망한 후보 루트 노드들의 전역 풀을 동적으로 유지하며, 이를 통해 반복 과정에서의 다양성을 효과적으로 제어한다. 고품질의 해를 탐색하기 위해, LCS 문헌에서 알려진 여러 휴리스틱 기법들을 독립적인 빔 탐색 절차에 활용한다. 현재까지 알려진 바로는, 본 연구는 최대 10개의 입력 시퀀스와 최대 500개의 문자를 포함하는 320개의 합성 데이터 세트를 활용한 VGLCS 문제에 대한 최초의 종합적인 계산 연구이다. 실험 결과는 제안된 방법이 유사한 실행 시간 내에서 기준 빔 탐색 방식보다 더 안정적인 성능을 보임을 보여준다.

This paper addresses the Variable Gapped Longest Common Subsequence (VGLCS) problem, a generalization of the classical LCS problem involving flexible gap constraints between consecutive solutions' characters. The problem arises in molecular sequence comparison, where structural distance constraints between residues must be respected, and in time-series analysis where events are required to occur within specified temporal delays. We propose a search framework based on the root-based state graph representation, in which the state space comprises a generally large number of rooted state subgraphs. To cope with the resulting combinatorial explosion, an iterative beam search strategy is employed, dynamically maintaining a global pool of promising candidate root nodes, enabling effective control of diversification across iterations. To exploit the search for high-quality solutions, several known heuristics from the LCS literature are utilized into the standalone beam search procedure. To the best of our knowledge, this is the first comprehensive computational study on the VGLCS problem comprising 320 synthetic instances with up to 10 input sequences and up to 500 characters. Experimental results show robustness of the designed approach over the baseline beam search in comparable runtimes.