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