본문 바로가기
KERD
논문KCI 등재

k-오차문제를 위한 4-러시안 알고리즘의 계산 단계 병렬화

Parallelizing the computation step of the Four-Russians’ algorithm for the k-difference problem

김진욱|김영호|심정섭
한국차세대컴퓨팅학회 (KINGComputing)|2013.04|한국차세대컴퓨팅학회 논문지 (The Journal of Korean Institute of Next Generation Computing)|제9권 제2호|pp. 78-88

0

조회

0

다운로드

5

인용

0

참고문헌

키워드

근사문자열매칭편집거리4-러시안 알고리즘edit distancek-오차문제동적프로그래밍approximate string matchingk-difference problemthe Four-Russians’ algorithm
주제분류컴퓨터학

초록

근사문자열매칭문제는 오랫동안 활발히 연구되어 왔다. 대표적인 근사문자열매칭문제로 편집거리문제와 k-오차문제가 잘 알려져 있다. 알파벳 ∑에 대해 길이가 각각 m ,n 인 두 문자열 P와 T가 주어졌을 때, 편집거리문제는 P와 T사이의 편집거리를 계산하는 문제이며, k -오차문제는 T 내에서 P가 k 이내의 편집거리로 발생하는 모든 위치를 찾는 문제이다. 편집거리문제와 k-오차문제는 동적프로그래밍을 이용하여 O(mn) 시간과 공간을 이용하여 해결할 수 있으며, 접미사트리를 이용하면 k-오차문제는 O(kn)시간과 공간을 이용하여 해결할 수 있다. 편집거리문제는 4-러시안 알고리즘을 이용해서도 해결할 수 있다. 4-러시안 알고리즘은 블록 크기를 t라 할 때, 전처리 단계에서 O(((3ㅣ∑ㅣ)^2t)t²)시간과 O(((3ㅣ∑ㅣ)^2t)t)공간, 계산 단계에서 O(mn/t)시간과 O(mn) 공간을 이용하여 편집거리를 계산한다. 본 논문에서는 4-러시안 알고리즘의 계산 단계를 m/t개의 쓰레드를 사용하여 O(m+n) 시간에 수행하도록 병렬화하여 k-오차문제를 해결하는 알고리즘을 제시한다. 실험결과, 제시된 4-러시안 병렬알고리즘은 기존의 4-러시안 순차알고리즘보다 DNA알파벳( ㅣ∑ㅣ=4 )의 경우 t= 2일 때 약 41배, t= 4일 때 약 19배 빠른 결과를 보였고, 이진알파벳(ㅣ∑ㅣ=2 )의 경우 t= 2일 때 약 45배, t = 5일 때 약 15배 빠른 결과를 보였다.

Abstract

Approximate string matching problems have been studied extensively for a long time. Two of the most well-known approximate string matching problems are the edit distance problem and the k-difference problem. Given two strings P(ㅣPㅣ=m) and T(ㅣTㅣ=n) over an alphabet ∑, the edit distance problem is to compute the edit distance between P and T. The k-difference problem is to find all the occurrences of P in T with at most edit distances. The edit distance problem and the k-difference problem can be solved in O(mn) time using dynamic programming technique. If suffix trees are used, the k-difference problem can be solved in O(kn) time and space. The edit distance problem also can be solved using Four-Russians’ algorithm whose preprocessing step runs in O(((3ㅣ∑ㅣ)^2t)t²) time and sO(((3ㅣ∑ㅣ)^2t)t) pace and the computation step runs in O(mn/t) time and O(mn) space where t is the size of the block. In this paper, we propose a parallelized version of the computation step of the Four-Russians’ algorithm for the k-difference problem which runs in O(m+n) time using m/t threads. For DNA alphabet, experimental results show that our parallel algorithm is about 41 times and 19 times faster than the (sequential) Four-Russians’ algorithm when t=2 and t=4, respectively. For binary alphabet, our parallel algorithm is about 45 times and 15 times faster than the (sequential) Four-Russians’ algorithm when t=2 and t=5, respectively.

참고문헌 (18)

  1. S. B. Needleman, "A General Method Applicable to the Search for Similarities in the Amino Acid Sequence of Two Proteins", J. Mol. Biol, 48(3), pp.443~453 (1970)
  2. T. F. Smith, "Identification of Common Molecular Subsequences", J. Mol. Biol, 147, pp.195~197 (1981)
  3. Approximate String Matching in DNA Sequences, "L. L. Cheng", IEEE, 303~310 (2003)
  4. 나중채, "샘플링 비율 조정을 통한 Clark의 Select 함수의 효율적 구현", 한국차세대컴퓨팅학회 논문지, 5(1), pp.24~29 (2009), 한국차세대컴퓨팅학회
  5. A. V. Aho, "Efficient String Matching: An Aid to Bibliographic Search", Communications of the ACM, 18(6) (1975)
  6. S. Forrest, "Self-nonself discrimination in a computer", Proc.IEEE Symp. Res. Security Privacy, 202(212), pp.202~212 (1994)
  7. 윤현철, "동적 최장공통비상위문자열 문제 해결 알고리즘", 한국차세대컴퓨팅학회 논문지, 6(6), pp.35~43 (2010), 한국차세대컴퓨팅학회
  8. D. Gusfield, "Algorithms on Strings, Trees, and Sequences" (1997), Cambridge university press
  9. V. I. Levenstein, "Binary codes capable of correcting deletions, insertions, and reversals", Sov. Phys. Dokl, 10, pp.707~710 (1966)
  10. Z. Galil, "An Improved Algorithm for Approximate String Matching", SIAM Journal on Computing, 19(6), pp.989~999 (1990)
  11. W. J. Masek, "A Faster Algorithm Computing String Edit Distance", Journal of computer and system science, 20(1), pp.18~31 (1980)
  12. V. Kundeti, "Extending the Four Russian Algorithm to Compute the Edit Script in Linear Space", ICCS 2008, Part I, LNCS, 5101, pp.893~902 (2008)
  13. 윤민, "GPU를 이용한 Salsa20 스트림 암호의 병렬화", 한국차세대컴퓨팅학회 논문지, 5(1), pp.53~62 (2009), 한국차세대컴퓨팅학회
  14. 정진홍, "GPU를 활용한 고성능 컴퓨팅 : 금융 파생 상품 모델링 케이스", 한국차세대컴퓨팅학회 논문지, 5(1), pp.30~40 (2009), 한국차세대컴퓨팅학회
  15. 윤현철, "CUDA를 이용한 최장공통비상위문자열 그래프 모델의 병렬생성", 정보과학회논문지 : 시스템 및 이론, 39(3), pp.202~208 (2012), 한국정보과학회
  16. L. Ligowski, "An efficient implementation of Smith Waterman algorithm on GPU using CUDA, for massively parallel scanning of sequence databases", Parallel & Distributed Processing (IPDPS). IEEE Int. Symp, 1(8), pp.1~8 (2009)
  17. 김영호, "4-러시안 알고리즘 기반의 편집거리 병렬계산", 정보처리학회논문지. 컴퓨터 및 통신시스템, 2(2), pp.67~74 (2013), 한국정보처리학회
  18. R. Li, "SOAP2: an improved ultrafast tool for short read alignment", Bioinformatics, 25(15), pp.1966~1967 (2009)

관련 논문AI추천

4-러시안 알고리즘 기반의 편집거리 병렬계산강대웅, 김영호, 심정섭, 정주희한국정보처리학회 · 정보처리학회논문지. 컴퓨터 및 통신시스템2013 · 제2권 제2호편집거리 계산을 위한 맵리듀스 알고리즘김진욱한국차세대컴퓨팅학회 · 한국차세대컴퓨팅학회 논문지2015 · 제11권 제2호GPU의 공유메모리를 활용한 확장편집거리 병렬계산김영호, 나중채, 심정섭한국정보처리학회 · 정보처리학회논문지. 컴퓨터 및 통신시스템2015 · 제4권 제7호k개의 오차를 허용하는 순위 패턴 매칭이인복(사)한국스마트미디어학회 · 스마트미디어저널2020 · 제9권 제2호문자열의 최장 공통 부분문자열과 최대 반복자를 구하기 위한 상수시간 RMESH 알고리즘우진운, 한선미한국정보처리학회 · 정보처리학회논문지. 컴퓨터 및 통신시스템2009 · 제16권 제5호DNA 서열분석을 위한 거리합기반 문자열의 근사주기김영호, 나중채, 심정섭, 정주희한국정보처리학회 · 정보처리학회 논문지2013 · 제2권 제2호

이 간행물의 다른 논문 (7건)

모바일 씬 클라이언트를 위한 크로스 레이어 기법과 하이브리드 프로토콜임철수, 허의남, 조철회, 송표, 김명섭, 이현우pp. 6-15QoS-enabled HOB Architecture and Bandwidth Reservation Protocol in EPON-WiMAX Integrated Network정복래pp. 16-23스마트폰의 증강현실을 활용한 광고의 속성이 광고태도와 브랜드태도, 구매의도에 미치는 영향김중규pp. 24-35데이터센터 에너지 감시장치의 패키지 형태 개발과 전력효율성 향상을 위한 Building block 구조의 에너지 최적화기술김경남, 조창희pp. 36-43GPGPU 응용의 고성능 원격수행을 위한 OpenCL 기반 오프로딩 프레임워크박찬익, 마정현, 박세진pp. 44-53
원문 보기