Earticle

Studying patterns in DNA sequences has been for years the subject of many research papers in bioinformatics. This paper evaluates two algorithms used for DNA comparison. Those are: Longest Common Substring and Subsequence (LCS, LCSS). Evaluation is performed based on the different code implementations for those two algorithms. Accuracy and performance are the two major criteria that are used for the evaluation of algorithms’ implementation. Results showed that while those two algorithms are popular, their implementations are not consistent through research papers or websites that use and implement those algorithms for DNA sequence comparison.

문자열 연산이 계산 생물학 분야에 응용되면서 효율적인 문자열 연산을 위한 다양한 자료구조와 알고리즘이 연구되고 있다. 최장 공통 부분문자열 문제는 두 개 이상의 문자열에서 가장 길게 일치하는 부분문자열을 찾는 연산이며, 최대 반복자 문제는 하나의 문자열에서 두 번 이상 반복되는 부분문자열을 찾는 연산이다. 이 연산은 패턴 매칭, 유사도 측정 등의 문자열 처리 분야에서 중요하게 사용되고 있다. 본 논문에서는 RMESH(Reconfigurable MESH) 구조에서 3-차원 n×n×n 프로세서를 사용하여 두 문자열의 최장 공통 부분문자열을 구하는 알고리즘과 주어진 문자열의 최대 반복자를 찾는 알고리즘을 제안하며, 이 알고리즘들은 모두 O(1)시간 복잡도를 갖는다.

Since string operations were applied to computational biology area, various data structures and algorithms for computing efficient string operations have been studied. The longest common substring problem is an operation to find the longest matching substring in more than two strings, and maximal repeat of string problem is an operation to find substrings repeated more than once in the given string. These operations are importantly used in the string processing area such as pattern matching and likelihood measurement. In this paper, we present algorithms to compute the longest common substring of two strings and to find the maximal repeat of string using three-dimensional n×n×n processors on RMESH(Reconfigurable MESH). Our algorithms have O(1) time complexity.