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 길이의 상관 관계도 높지 않았다