Earticle

초록

영어

The longest common subsequence (LCS for short) is one of the main criteria of measuring sequence similarity. Finding the LCS of two strings requires a time proportional to the product of the lengths of the two strings. The maximal common subsequence(MCS for short) is a variant of the LCS, where the constraint is weakened from longest to maximal. Recently, a (sub)linearithmictime algorithm for finding an MCS of two strings was proposed. The lengths of MCS’s of two strings may not be identical unlike the lengths of LCS’s. Although the length of the LCS is very long, an MCS of length 1 may exist. Therefore, the efficacy of MCS for measuring similarity depends on which MCS is found. In this paper, in order to examine the efficacy of MCS, we compare the lengths of LCS and MCS and analyze the correlation of the two lengths for various real data and randomly generated data. The ratio of the length of MCS to the length of LCS was 15.5% to 58.0% in the real data and 12.6% to 55.3% in the random data. The correlation between the lengths of MCS and LCS was not high.

한국어

최장 공통 부분 서열(Longest Common Subsequence, LCS)은 서열의 유사도(similarity)를 나타내는 주요 지 표 중 하나로 사용되며, 일반적으로 두 문자열의 LCS를 계산하는 데는 문자열 길이의 곱에 비례하는 시간이 필요하 다. 극대 공통 부분 서열(Maximal Common Subsequence, MCS)은 최장(longest) 조건을 극대(maximal)로 완화한 것으로, 최근 두 문자열의 MCS를 선형에 가까운 시간에 찾는 알고리즘이 개발되었다. 두 문자열의 MCS의 길이는 LCS의 길이와 달리 유일하지 않을 수 있으며, LCS의 길이가 매우 길더라도 길이가 1인 MCS가 존재할 수 있다. 따라서 MCS의 유사도로서의 효용성은 어떤 MCS를 찾는지에 따라 달라진다. 본 논문에서는 MCS 알고리즘 의 효용성을 알아보기 위해, 다양한 실제 데이터와 랜덤 생성 데이터에 대해 MCS의 길이를 LCS의 길이와 비교하 고 상관 관계를 분석한다. MCS의 길이는 LCS 길이 대비 실제 데이터에서는 15.5~58.0%, 랜덤 데이터에서는 12.6~55.3%로 나타났고, MCS의 길이와 LCS 길이의 상관 관계도 높지 않았다

목차

요약
Abstract
1. 서론
2. 배경지식
2.1 최장 공통 부분 서열
2.2 극대 공통 부분 서열
3. 실험 및 결과
3.1 실험 설정
3.2 MCS와 LCS의 길이 차이
3.3 MCS와 LCS 길이의 상관관계
3.4 LCS와 MCS의 시간 비교
4. 결론 및 향후 연구
Acknowledgements
참고문헌

키워드

저자

• 이동엽 [ DongYeop Lee | 세종대학교 컴퓨터공학과 ]
• 나중채 [ Joong Chae Na | 세종대학교 컴퓨터공학과 ] 교신저자

참고문헌

발행기관

간행물

표지보기 관심저널 등록

• 간행물명

  한국차세대컴퓨팅학회 논문지 [THE JOURNAL OF KOREAN INSTITUTE OF NEXT GENERATION COMPUTING]

• 간기

  격월간

• pISSN

  1975-681X

• 수록기간

  2005~2026

• 등재여부

  KCI 등재

• 십진분류

  KDC 566 DDC 004