본문 바로가기
HOME> 논문 > 논문 검색상세

논문 상세정보

생물학 서열 데이타베이스에서 부분 문자열의 선적도 추정
Estimation of Substring Selectivity in Biological Sequence Database

배진욱   (서울대학교 전기·컴퓨터공학부UU0000691  ); 이석호   (서울대학교 컴퓨터공학부UU0000691  );
  • 초록

    지금까지 문자열 데이타에 대한 선택도 추정은 문자열들의 등장 회수에 대한 정보를 저장하고 있는 '카운트 서픽스 트리'를 생성한 뒤, 이 트리를 이용하여 부분 문자열들의 선택도를 추정하는 방법으로 이루어졌다. 그런데, 문자열 데이타가 생물학 서열처럼 매우 길어질 경우 카운트 서픽스 트리를 생성하는 일은 거의 불가능해진다는 문제점이 발생한다. 이 논문에서는 길이가 q인 부분 문자열들만을 삽입한 '카운트 큐그램 트리'를 제안한다. 카운트 큐그램 트리는 서열 내의 길이가 q 이하인 모든 부분 문자열(큐그램) 들의 정확한 등장 회수를 저장하고 있으며, 문자열의 전체 길이 N에 상관없는 크기로, O(N) 시간에 생성 가능하다. 또한, 이 논문에서는 카운트 큐그램 트리를 이용한 'k번째 최대겹침' 추정 방법을 제시한다. 이 추정 방법은 질의 문자열을 길이 q인 부분 문자열로 나눌 때 부분 문자열들의 겹치는 정도 k를 선택할 수 있도록 한 방법으로 이전 연구에서 제시한 '최대겹침' 방법을 확장하였다. q와 k를 변화시키며 진행한 실험 올 통해 대부분의 경우에 매우 정확하게 선택도를 추정할 수 있음을 확인하였다.


    Until now, substring selectivities have been estimated by two steps. First step is to build up a count-suffix tree, which has statistical information about substrings, and second step is to estimate substring selectivity using it. However, it's actually impossible to build up a count-suffix tree from biological sequences because their lengths are too long. So, this paper proposes a novel data structure, count q-gram tree, consisting of fixed length substrings. The Count q-gram tree retains the exact counts of all substrings whose lengths are equal to or less than q and this tree is generated in 0(N) time and in site not subject to total length of all sequences, N. This paper also presents an estimation technique, k-MO. k-MO can choose overlapping length of splitted substrings from a query string, and this choice will affect accuracy of selectivity and query processing time. Experiments show k-MO can estimate very accurately.


  • 주제어

    생물학 서열 데이터베이스 .   DNA 서열 .   부분 문자열 선택도 추정 .   카운트 서픽스 트리 .   카운트 큐그램 트리 .   k번째 최대겹침 추정 방법.  

  • 참고문헌 (17)

    1. R. Grossi and J. S. Vitter. Compressed suffix arrays and suffix trees with applications to text indexing and string matching. ACM Symposium on Theory of Computing, pages 397-456, 2000 
    2. ftp://ncbi.nlm.nih.gov/genomes/H_sapiens/, 2001 
    3. L. Gravano, P. G. Ipeirotis, H. V. Jagadish, N. Koudas, S. Muthukrishnan, and D. Srivastava. Approximate string joins in a database (almost) for free. In Proceedings of VLDB, 2001 
    4. E. Hunt, M. P. Atkinson, and R. W. Irving. A database index to large biological sequences. In Proceedings of VLDB, 2001 
    5. G. Navarro, E. Sutinen, J. Tannincn, and J. Tarhio. Indexing text with approximate q grams. In Proceedings of Combinatorial Pattern Matching, pages 350-363, 2000 
    6. E. M. McCreight. A space-economical suffix tree construction algorithm. Journal of the ACM, Volume 23, pages 262-272. 1976 
    7. E. Ukkonen. Approximate string-matching with q-grams and maximal matches. Theoretical Computer Science, Volume 92, pages 192-211, 1992 
    8. G. Navarro and R. Baeza-Yates, A practical q-gram index for text retrieval allowing errors. CLEL Electronic Journal, Volume 1. Number 2, 1998 
    9. H. V. Jagadish, H. T. Ng, and D. Srivastava. On effective multi-dimensional indexing for strings. In Proceedings of ACM SIGMOD, pages 403-414, 2000 
    10. P. Fcrragina, N. Koudas, S. Muthukrishnan, and D. Srivastava. Two-dimensional substring indexing. In Proceedings of ACM Symposium on Principles of Database Systems, 2001 
    11. Z. Chen, H. V. Jagadish, F. Korn, N. Koudas, S. Muthukrishnan, R. T. Ng, and D. Srivastava. Counting twig matches in a tree. In Proceedings of ICDE, pages 595-604. 2001 
    12. A. Aboulnaga, A. R. Alarneldecn, and J. F. Naughton. Estimating the selectivity of XML path expressions for internet scale applications. In Proceedings of VLDB, pages 591-600, 2001 
    13. P. J. Haas, J. F. Naughton, S. Seshadri, and L. Stokes. Sampling-based estimation of the number of distinct values of an attribute. In Proceedings of VLDB, pages 311-322, 1995 
    14. V. Poosala, Y. E. Ioannidis, P. J. Haas, and E. J. Shekita, Improved histograms for selectivity estimation of range predicates. In Proceedings of ACM SIGMOD, 1996 
    15. P. Krishnan, J. S. Vitter, and B. Iyer. Estimating alphanumeric selectivity in the presence' of wildcards. In Proceedings of ACM SIGMOD, pages 282-293, 1996 
    16. H. V. Jagadish, R. T. Ng, and D. Srivastava. Substring selectivity estimation. In Proceedings of ACM Symposium on Principles of Database Systems, June 1999 
    17. H. V. Jagadish, O. Kapitskaia, R. T. Ng, and D. Srivastava. Multi-dimensional substring selectivity estimation. In Proceedings of VLDB, 1999 

 저자의 다른 논문

  • 배진욱 (5)

    1. 1999 "복수 데이터베이스에서 링크를 이용한 연관 규칙 탐사" 정보과학회논문지. Journal of KISS (b):software and applications. B 26 (8): 939~954    
    2. 2000 "주문형 오디오 시스템을 위한 웹 캐시 구조의 설계 및 평가" 정보과학회논문지. Journal of KIISE. 데이타베이스 27 (2): 209~215    
    3. 2005 "범위 모자이크 질의의 효율적인 수행" 정보과학회논문지. Journal of KIISE. 데이타베이스 32 (5): 487~497    
  • 이석호 (35)

 활용도 분석

  • 상세보기

    amChart 영역
  • 원문보기

    amChart 영역

원문보기

무료다운로드
  • NDSL :
유료다운로드

유료 다운로드의 경우 해당 사이트의 정책에 따라 신규 회원가입, 로그인, 유료 구매 등이 필요할 수 있습니다. 해당 사이트에서 발생하는 귀하의 모든 정보활동은 NDSL의 서비스 정책과 무관합니다.

원문복사신청을 하시면, 일부 해외 인쇄학술지의 경우 외국학술지지원센터(FRIC)에서
무료 원문복사 서비스를 제공합니다.

NDSL에서는 해당 원문을 복사서비스하고 있습니다. 위의 원문복사신청 또는 장바구니 담기를 통하여 원문복사서비스 이용이 가능합니다.

이 논문과 함께 출판된 논문 + 더보기