Earticle

최장 공통 부분 서열(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 길이의 상관 관계도 높지 않았다

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.

Grammatical inference methods are expected to find grammatical structures hidden in biological sequences. One hopes that studies of grammar serve as an appropriate tool for theory formation. Thus, we have developed JSequitur for automatically generating the grammatical structure of biological sequences in an inference framework of string compression algorithms. Our original motivation was to find any grammatical traits of several cancer genes that can be detected by string compression algorithms. Through this research, we could not find any meaningful unique traits of the cancer genes yet, but we could observe some interesting traits in regards to the relationship among gene length, similarity of sequences, the patterns of the generated grammar, and compression rate.

최근 들어 웜 바이러스의 출현과 더불어, 인터넷 대란과 같은 서비스 거부 공격의 피해 사례가 급증하고 있다. 이에 따라 네트워크 보안이 많은 관심을 받고 있는데, 보안의 여러 분야 가운데에서도 특히 침입탐지와 대응에 관한 연구가 활발히 이루어지고 있다. 또한 이러한 작업들을 자동화하기 위한 도구들이 개발되고 있지만 그 정확성이 아직 신뢰할 만한 수준에 이르지 못하고 있는 것이 지금의 현실이다. 본 논문에서는 이벤트 로그를 분석하여 침입 패턴을 예측하고, 이를 기반으로 자동화된 침입 탐지 및 대응을 구현할 수 있는 String Matching 알고리즘을 제안하고자 한다.