Journal of Korea Society of Industrial Information Systems (한국산업정보학회논문지)

Korea Society of Industrial Information Systems (한국산업정보학회)
권호 표지
DOI QR코드

DOI QR Code

Suffix Tree Constructing Algorithm for Large DNA Sequences Analysis

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

  • 최해원 (경운대학교 컴퓨터공학과)
  • Received : 2009.08.18
  • Accepted : 2010.02.20
  • Published : 2010.03.30
Download PDF
⟨ Previous Next ⟩

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.

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

Keywords

References

  1. Dan Gusfild, Algorithms on Strings, Trees, and Sequence : Computer Science and Computational Biology, CAMBRIDGE University Press, 2002.
  2. Juha Karkkainen and Esko Ukkonen, "Sparse Suffix Tree," COCOON, pp.219-233, 1996.
  3. E. Ukkonen, "On-Line Construction of Suffix Trees," Algorithmica, vol. 14, pp.249-260, 1995. https://doi.org/10.1007/BF01206331
  4. Hardison,R.C., Oeltjen,J. and Miller,W., "Long human-mouse sequence alignments reveal novel regulatory elements: a reason to sequence the mouse genome," Genome Res., vol. 7, pp.959-966, 1998.
  5. Shimuzu,N., Roe,B.A., Chissoe,S. et al., "The DNA sequence of human chromosome 22," Nature , vol. 402, pp.489-495, 1999. https://doi.org/10.1038/990031
  6. Mark Nelson, "Fast String Searching With Suffix Trees," Dr. Dobb's Journal, 1996.
  7. Graham A. Stephen, String Search, University College of North Wales, 2003.
  8. Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest, Introduction to Algorithms, The MIT Press, 2005.
  9. Schwartz,S., Zhang,Z., Frazer,K.A., Smit,A., Riemer,C., Bouck,J., Gibbs,R., Hardison,R. and Miller,W., "A web server for aligning two genomic DNA sequences," Genome Res., vol. 10, pp.577-586, 2004.
  10. Batzoglou,S., Pachter,L., Mesirov,J.P., Berger,B. and Lander,E.S. , "Human and mouse gene structure: comparative analysis and application to exon prediction," Genome Res., vol. 10, pp.950-958, 2005.