지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
이 논문의 연구 히스토리 (4)
2015
Parallel Approximate String Matching under Hamming Distance for Multiple DNA Patterns with a Fixed-length on Graphic Processing Units
ThienLuan Ho
,
Hyun-Jin Kim
,
Seung-Rohk Oh
외 2명
정보 및 제어 논문집
2015.10
학술대회자료
An Effective Parallel Aho-Corasick Approach on Graphic Processing Units for String Matching in Deep Packet Inspection
ThienLuan Ho
,
Hyun-Jin Kim
,
Seung-Rohk Oh
외 2명
정보 및 제어 논문집
2015.04
학술대회자료
An Effective Parallel Aho-Corasick Approach on Graphic Processing Units for String Matching in Deep Packet Inspection
ThienLuan Ho
,
Hyun-Jin Kim
,
Seung-Rohk Oh
외 2명
대한전기학회 학술대회 논문집
2015.04
학술대회자료
- 이 논문의 후속연구가 궁금하신가요?
- 연관 학술논문 또는 학술발표를 통해 보다 발전된 연구결과를 확인하실 수 있습니다.
- 이 논문의 연구 히스토리 확인하기
초록· 키워드
오류제보하기
In this paper, we propose a parallel approximate string matching algorithm with k-mismatches for multiple fixed-length patterns (PMASM) in DNA sequences. PMASM is developed from parallel single pattern approximate string matching algorithms to effectively calculate the Hamming distances for multiple patterns with a fixed-length. In the preprocessing phase of PMASM, all target patterns are binary encoded and stored into a look-up memory. With each input character from the input string, the Hamming distances between a substring and all patterns can be updated at the same time based on the binary encoding information in the look-up memory. Moreover, PMASM adopts graphics processing units (GPUs) to process the data computations in parallel. This paper presents three kinds of PMASM implementation methods in GPUs: thread PMASM, block-thread PMASM, and shared-mem PMASM methods. The shared-mem PMASM method gives an example to effectively make use of the GPU parallel capacity. Moreover, it also exploits special features of the CUDA (Compute Unified Device Architecture) memory structure to optimize the performance. In the experiments with DNA sequences, the proposed PMASM on GPU is 385, 77, and 64 times faster than the traditional naive algorithm, the shift-add algorithm and the single thread PMASM implementation on CPU. With the same NVIDIA GPU model, the performance of the proposed approach is enhanced up to 44% and 21%, compared with the naive, and the shift-add algorithms.
목차
Abstract
1. Introduction
2. Problem Definitions
3. General-Purpose Parallel Computing Architecture
4. Previous Works
5. Proposed Parallel Approximate String Matching for Multiple Fixed-Length Patterns
6. Experimental Results
7. Conclusions
References
참고문헌 (15)
참고문헌 신청
S. Li, Q. Jiang, and D. Wei, “An optimized algorithm for finding approximate tandem repeats in DNA sequences,” Proc. 2nd Int. Workshop on Education Technology and Computer Science (ETCS), IEEE, vol. 3, pp. 68?71, 2010.
L.-L. Cheng, D. W. Cheung, and S.-M. Yiu, “Approximate string matching in DNA sequences,” Proc. 8th Int. Conf. Database Systems for Advanced Applications, (DASFAA), IEEE, pp. 303?310, 2003.
K. Inoue, et al, “Application of approximate pattern matching in two dimensional spaces to grid layout for biochemical network maps,” PloS One, vol. 7, no. 6, p. e37739, 2012.
Y. Liu, L. Guo, J. Li, M. Ren, and K. Li, “Parallel algorithms for approximate string matching with kmismatches on CUDA,” Proc. 26th Int. Parallel and Distributed Processing Symposium Workshops & PhD Forum (IPDPSW), IEEE, pp. 2414?2422, 2012.
G. Navarro, “A guided tour to approximate string matching,” ACM computing surveys (CSUR), vol. 33, no. 1, pp. 31?88, 2001.
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
Parallel Approximate String Matching under Hamming Distance for Multiple DNA Patterns with a Fixed-length on Graphic Processing Units
정보 및 제어 논문집
2015 .10
-
DNA 서열에 적합한 스트링 매칭 알고리즘
한국정보과학회 학술발표논문집
2018 .06
-
An Effective Parallel Aho-Corasick Approach on Graphic Processing Units for String Matching in Deep Packet Inspection
정보 및 제어 논문집
2015 .04
-
An Effective Parallel Aho-Corasick Approach on Graphic Processing Units for String Matching in Deep Packet Inspection
대한전기학회 학술대회 논문집
2015 .04
-
Parallel Computation of Z-Function for Order-Preserving Pattern Matching and Order-Preserving Multiple Pattern Matching
Journal of KIISE
2018 .08
-
Parallel Algorithms for Finding δ-approximate Periods and γ-approximate Periods of Strings over Integer Alphabets
Journal of KIISE
2017 .08
-
CUDA based parallel design of a shot change detection algorithm using frame segmentation and object movement
한국컴퓨터정보학회논문지
2015 .07
-
다중 GPU기반 홀로그램 생성을 위한 병렬처리 성능 최적화 기법 기재
스마트미디어저널
2019 .01
-
다중 GPU 사용을 위한 CUDA C 행렬의 곱 프로그램의 구현
한국정보기술학회논문지
2020 .11
-
Hybrid Parallel High Efficiency Video Coding Extensions on Screen Content Coding Decoder on Embedded systems
대한전자공학회 학술대회
2019 .06
-
GPU 메모리 용량을 초과하는 위성영상의 GPU 기반 병렬처리
대한공간정보학회 학술대회
2020 .06
-
이진인코딩을 이용한 순위다중패턴매칭 알고리즘 병렬화
한국정보과학회 학술발표논문집
2020 .07
-
단일 GPU 환경에서 오픈 소스를 이용한 CUDA 메모리 사용 패턴 분석
전자공학회논문지
2025 .02
-
국방정보시스템 성능향상을 위한 효율적인 GPU적용방안 연구
디지털산업정보학회논문지
2015 .01
-
A tool for the design of DNA base sequences for molecular circuits
제어로봇시스템학회 국제학술대회 논문집
2017 .10
-
Workload Characteristics-based L1 Data Cache Switching-off Mechanism for GPUs
한국컴퓨터정보학회논문지
2018 .10
-
CPU-GPU 구조 기반 능동 소음 제어 알고리즘 개발
한국소음진동공학회 학술대회논문집
2018 .10
-
A Case Study of the Base Technology for the Smart Grid Security : Focusing on a Performance Improvement of the Basic Algorithm for the DDoS Attacks Detection Using CUDA
멀티미디어학회논문지
2016 .02
-
Parallel Implementation of the Order-Preserving Multiple Pattern Matching Algorithm using the Karp-Rabin Algorithm
Journal of KIISE
2021 .03
-
CPU-GPU 메모리 계층을 고려한 고처리율 병렬 KMP 알고리즘
전기학회논문지
2018 .05
이 논문의 저자 정보
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2018-560-001008773