대용량 DNA서열 처리를 위한 서픽스 트리 생성 알고리즘의 개발

국문 초록 (Abstract)

서픽스 트리는 데이터의 내부구조를 자세히 나타내고 선형시간 탐색이 가능한 효과적인 자료구조로서 DNA 서열분석 등에 유용하다. 그러나 서열을 서픽스 트리로 구축하는 경우 트리의 크기가 원본의 최소 30배 이상으로 커지므로 테라바이트(TB)급의 대용량 DNA 서열의 경우에 메모리상의 응용은 매우 어려운 문제점이 있다. 이에 본 논문에서는 디스크를 이용한 대용량 DNA의 서픽스 트리 응용기법을 제시한다. 이때 DNA 서열구조를 고려한 서픽스 트리 선형탐색 특성 유지를 보장한다. 이를 검증하기 위하여 9G Byte의 유전자 단편 서열을 이용해 424G Byte의 서픽스 트리를 디스크에 구축한 다음, 임의의 질의 서열에 대해 KMP알고리즘과 비교한 결과 질의 응답시간에서 우수한 성능을 보였다.

다국어 초록 (Multilingual Abstract)

A Suffix Tree is an efficient data structure that exposes the internal structure of a string and allows efficient solutions to a wide range of complex string problems, in particular, in the area of computational biology. However, as the biological information explodes, it is impossible to construct the suffix trees in main memory. We should find an efficient technique to construct the trees in a secondary storage. In this paper, we present a method for constructing a suffix tree in a disk for large set of DNA strings using new index scheme. We also show a typical application example with a suffix tree in the disk.

목차 (Table of Contents)

• 요약
• Abstract
• 1. 서론
• 2. 관련 연구
• 3. 디스크를 이용한 서픽스 트리 생성
• 4. 실험 및 분석
• 5. 결론
• 참고문헌

참고문헌 (Reference)

1 Shimuzu,N., "The DNA sequence of human chromo- some 22" 402 : 489-495, 1999

2 Graham A. Stephen, "String Search" University College of North Wales 2003

3 Juha Karkkainen, "Sparse Suffix Tree"

4 E. Ukkonen, "On-Line Construction of Suffix Trees" 14 : 249-260, 1995

5 Hardison,R.C., "Long human-mouse sequence alignments reveal novel regulatory elements: a reason to sequence the mouse genome" 7 : 959-966, 1998

6 Thomas H. Cormen, "Introduction to Algorithms" The MIT Press 2005

7 Batzoglou,S., "Human and mouse gene structure: comparative analysis and application to exon prediction" 10 : 950-958, 2005

8 Mark Nelson, "Fast String Searching With Suffix Trees"

9 Dan Gusfild, "Algorithms on Strings, Trees, and Sequence : Computer Science and Computational Biology" CAMBRIDGE University Press 2002

10 Schwartz,S., "A web server for aligning two genomic DNA sequences" 10 : 577-586, 2004