Fast Matching Method for DNA Sequences = DNA 서열을 위한 빠른 매칭 기법

국문 초록 (Abstract)

DNA 서열은 각 종을 나타내는 근본적인 정보이며, 다른 종 간의 DNA 서열 비교는 중요한 작업이다. DNA 서열은 길이가 매우 길며 또 종의 종류도 다양하기 때문에, DNA 서열 비교에서는 빠른 매칭 뿐만 아니라 효율적인 저장도 중요한 요소이다. 즉, 인코딩 된 DNA 서열에 적합한 빠른 문자열 매칭 방법이 필요하다. 본 논문에서는 매칭 시 디코딩이 필요하지 않은 인코딩 된 DNA 서열을 위한 빠른 매칭 알고리즘을 제시한다. 제시하는 알고리즘은 네 문자 한 바이트 인코딩을 이용하며 서픽스 기법과 다중 패턴 매칭 기법을 접목하고 있다. 실험 결과로는 본 논문에서 제시하는 방법이 AGREP보다 약 다섯 배 빠름을 보이는데, 이는 알려진 알고리즘들 중에서 가장 빠른 결과이다.

다국어 초록 (Multilingual Abstract)

DNA sequences are the fundamental information for each species and a comparison between DNA sequences of different species is an important task. Since DNA sequences are very long and there exist many species, not only fast matching but also efficient storage is an important factor for DNA sequences. Thus, a fast string matching method suitable for encoded DNA sequences is needed. In this paper, we present a fast string matching method for encoded DNA sequences which does not decode DNA sequences while matching. We use four-characters-to-one-byte encoding and combine a suffix approach and a multi-pattern matching approach. Experimental results show that our method is about 5 times faster than AGREP and the fastest among known algorithms.

목차 (Table of Contents)

• 요약
• Abstract
• 1. Introduction
• 2. Preliminaries
• 3. Proposed Method
• 4. Experimental Results
• 5. Conclusions
• References

참고문헌 (Reference)

1 Jorma Tarhio, "String Matching in the DNA Alphabet" 27 (27): 851-861, 1997

2 Yusuke Shibata, "Speeding Up Pattern Matching by Text Compression" 306-315, 2000

3 Kimmo Fredriksson, "Shift-Or String Matching with Super-Alphabets" 87 (87): 201-204, 2003

4 Kimmo Fredriksson, "Practical and Optimal String Matching" 376-387, 2005

5 Gonzalo Navarro, "Practical and Flexible Pattern Matching over Ziv-Lempel Compressed Text" 2 (2): 347-371, 2004

6 R. Nigel Horspool, "Practical Fast Searching in Strings" 10 (10): 501-506, 1980

7 Amihood Amir, "Let Sleeping Files Lie: Pattern Matching in Z- compressed Files" 705-714, 1994

8 Gonzalo Navarro, "LZgrep: a Boyer-Moore String Matching Tool for Ziv-Lempel Compressed Text" 35 (35): 1107-1130, 2005

9 Gonzalo Navarro, "Flexible Pattern Matching in Strings: Practical On-Line Search Algorithms for Texts and Biological Sequences" Cambridge University Press 2002

10 Gonzalo Navarro, "Fast and Flexible String Matching by Combining Bit- Parallelism and Suffix Automata" 5 (5): 2000

11 Sun Wu, "Fast Text Searching Allowing Errors" 35 (35): 83-91, 1992

12 J.Y. Kim, "Fast String Matching Using an -gram Algorithm" 24 (24): 79-88, 1994

13 D. E. Knuth, "Fast Pattern Matching in Strings" 6 : 323-350, 1977

14 "FASTA"

15 Cyril Allauzen, "Efficient experimental string matching by weak factor recognition. 12th Annual Symposium on Combinatorial Pattern Matching" 51-72, 2001

16 Amihood Amir, "Efficient Two- Dimensional Compressed Matching" 279-288, 1992

17 Edleno Silva de Moura, "Direct Pattern Matching on Compressed Text" IEEE Computer Society 90-95, 1998

18 Lei Chen, "Compressed Pattern Matching in DNA Sequences" 62-68, 2004

19 Petri Kalsi, "Comparison of Exact String matching Algorithms for Biological Sequences" 417-426, 2008

20 "BLAST"

21 Sun Wu, "AGREP - A Fast Approximate Pattern-matching Tool" 153-162, 1992

22 Daniel M. Sunday, "A Very Fast Substring Search Algorithm" 33 (33): 132-142, 1990

23 Christian Charras, "A Very Fast String Matching Algorithm for Small Alphabets and Long Patterns" 55-64, 1998

24 Udi Manber, "A Text Compression Scheme That Allows Fast Searching Directly in the Compressed File" 15 (15): 124-136, 1997

25 Beate Commentz-Walter, "A String Matching Algorithm Fast on the Average" 118-132, 1979

26 Beate Commentz-Walter, "A String Matching Algorithm Fast on the Average" Heidelberg Scientific Center 1979

27 Frantisek Franek, "A Simple Fast Hybrid Pattern- Matching Algorithm" 288-297, 2005

28 Ricardo Baeza-Yates, "A New Approach to Text Searching" 35 (35): 74-82, 1992

29 Robert S. Boyer, "A Fast String Searching Algorithm" 20 (20): 762-772, 1977

30 Yusuke Shibata, "A Boyer-Moore Type Algorithm for Compressed Pattern Matching" 181-194, 2000