본 논문은 연속 문자 사이 갭 제약을 유연화한 LCS의 일반화인 가변 갭 최장 공통 부분 수열(VGLCS) 문제를 다룬다. 분자 서열 비교나 시계열 분석과 같이 거리·시간 제약이 중요한 응용에 동기를 두고, 루트 기반 상태 그래프 표현 위에서 검색 프레임워크를 제안한다. 조합 폭발을 다루기 위해 유망 루트 노드 풀을 동적으로 유지하는 반복 빔 서치 전략을 도입하고, LCS 문헌의 휴리스틱을 결합한다. 최대 10개 입력 시퀀스, 500자 길이의 320개 합성 인스턴스 실험에서 베이스라인 빔 서치 대비 견고성 향상이 비슷한 실행 시간으로 달성됨을 보였다.
- •갑 제약이 있는 LCS 일반화 문제 VGLCS를 체계적으로 정의
- •루트 기반 상태 그래프 표현과 반복 빔 서치 프레임워크 제안
- •기존 LCS 휴리스틱을 통합해 고품질 해 탐색 강화
- •320개 합성 인스턴스에서 베이스라인 대비 견고성 향상 입증
0단 자동
AI가 규칙대로 쓰고 그대로 게시했습니다. 사람이 따로 보지 않았습니다.
- 규칙 판
- 규칙 판 도입 이전 기사입니다.
- 남기는 것
- 규칙 판 · 모델 · 시각
- 판 기록
- 아직 없습니다.
On Solving the Multiple Variable Gapped Longest Common Subsequence Problem
- 1.가변 갭을 갖는 최장 공통 부분수열 VGLCS 문제를 위한 탐색 프레임워크
- 2.뿌리 기반 상태 그래프와 반복 빔 서치로 조합 폭발을 관리
- 3.LCS 기존 휴리스틱을 활용해 고품질 해를 탐색
- 4.320개 합성 인스턴스 실험에서 베이스라인 대비 강건성 확인
왜 중요한가?
분자 서열 비교와 시계열 분석 등 실응용에 필요한 가변 갭 LCS의 최초 종합 계산 연구로 해당 문제의 성능 기준선을 확립
본문 미리보기
arXiv:2604.18645v1 Announce Type: new Abstract: 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 searc
전체 내용이 궁금하다면?
원문을 직접 읽어보세요
이 글이 만들어진 과정
- 13:10AI 초안
