지원사업
학술연구/단체지원/교육 등 연구자 활동을 지속하도록 DBpia가 지원하고 있어요.
커뮤니티
연구자들이 자신의 연구와 전문성을 널리 알리고, 새로운 협력의 기회를 만들 수 있는 네트워킹 공간이에요.
논문 기본 정보
- 자료유형
- 학술저널
- 저자정보
- 저널정보
- Korean Institute of Information Scientists and Engineers 정보과학회논문지 : 데이타베이스 정보과학회논문지 : 데이타베이스 제36권 제6호
- 발행연도
- 2009.12
- 수록면
- 455 - 465 (11page)
이용수
초록· 키워드
오류제보하기
서픽스 트리는 공통의 프리픽스의 빈도수가 높을 때 효과적인 알고리즘으로, 한정된 문자로만 구성된 DNA 유사성 검색을 위한 연구에서 널리 활용되고 있다. 그러나, 서픽스 트리는 인덱스 특성 상 메모리 공간을 많이 차지하며, 트리의 분할 시 DNA 시퀀스의 비율로 인한 쏠림현상이 발생한다는 문제점을 가진다. 따라서, 본 논문에서는 공통의 프리픽스를 가지는 가변길이의 파티셔닝 방법으로 합병하지 않는 인덱싱 방안인 SENoM을 제안한다. SENoM은 전체 시퀀스에서 공통의 프리픽스를 가지는 서픽스들의 발생 빈도수가 임계치 이하인 경우 디스크에 저장하고, 임계치 이상인 경우 임계치 이하가 될 때까지 프리픽스를 확장한다. 모든 파티션은 서브트리로 구축한 후 디스크에 저장하며, 질의처리를 위해, 구축된 파티션의 프리픽스를 서픽스로 가지는 트리를 구축한다. 제안하는 기법은 복잡한 합병과정을 제거하고, 많은 파티션 발생으로 인한 디스크 I/O 발생을 줄인다. 실험을 통해, SENoM이 Trellis 알고리즘에 비해 메모리 사용량을 약 35%, 인덱스 크기를 약 20% 감소시켰음을 보인다. 또한, 질의길이가 긴 경우에도 프리픽스 트리를 이용하여 효과적인 질의처리가 가능함을 보인다.
목차
요약
Abstract
1. 서론
2. 관련연구
3. SENoM 인덱싱 방안
4. 질의 처리 방안
5. 실험 및 분석
6. 결론
참고문헌
참고문헌 (16)
참고문헌 신청
1. [학술지(정기간행물)] - S. F. Altschul / 1990 / Basic Local Alignment Search Tool / Journal of the Molecular Biology 215 (3) : 403 ~ 410
2. [학술지(정기간행물)] - E. McCreight / 1976 / A Space-Economical Suffix Tree Construction Algorithm / Journal of the ACM 15 (2) : 514 ~ 534
3. [학술지(정기간행물)] - D. G. Jeffrey / 2002 / BeoBLAST: Distributed BLAST and PSI-BLAST on a Beowulf cluster / Journal of the Bioinformatics 18 (5) : 765 ~ 766
4. [학술지(정기간행물)] - E. Hunt / 2002 / Database Indexing for Large DNA and Protein Sequence Collections / Journal of the VLDB 11 (3) : 256 ~ 271
5. [학술지(정기간행물)] - D. Yao / 2005 / Hash-based Labeling Techniques for Storage Scaling / Journal of the VLDB 14 (2) : 222 ~ 237
2. [학술지(정기간행물)] - E. McCreight / 1976 / A Space-Economical Suffix Tree Construction Algorithm / Journal of the ACM 15 (2) : 514 ~ 534
3. [학술지(정기간행물)] - D. G. Jeffrey / 2002 / BeoBLAST: Distributed BLAST and PSI-BLAST on a Beowulf cluster / Journal of the Bioinformatics 18 (5) : 765 ~ 766
4. [학술지(정기간행물)] - E. Hunt / 2002 / Database Indexing for Large DNA and Protein Sequence Collections / Journal of the VLDB 11 (3) : 256 ~ 271
5. [학술지(정기간행물)] - D. Yao / 2005 / Hash-based Labeling Techniques for Storage Scaling / Journal of the VLDB 14 (2) : 222 ~ 237
함께 읽어보면 좋을 논문
논문 유사도에 따라 DBpia 가 추천하는 논문입니다. 함께 보면 좋을 연관 논문을 확인해보세요!
-
대용량 DNA서열 처리를 위한 서픽스 트리 생성 알고리즘의 개발
한국산업정보학회논문지
2010 .03
-
효과적인 DNA 검색을 위한 해쉬 기반의 서픽스 트리(Suffix Tree) 방안
한국정보과학회 학술발표논문집
2008 .10
-
DNA 스트링에 대하여 써픽스 배열을 구축하는 빠른 알고리즘
정보과학회논문지 : 시스템 및 이론
2007 .08
-
확장된 단어 서픽스 트리에서의 완전매칭 알고리즘
한국정보과학회 학술발표논문집
2000 .10
-
패킷 분류를 위한 이차원 이진 프리픽스 트리
정보과학회논문지 : 정보통신
2005 .08
-
부분 문자열 선택도 추정을 위한 서픽스트리 변환 기법
정보과학회논문지 : 데이타베이스
2007 .04
-
써픽스 배열 합병을 이용한 일반화된 써픽스 배열의 효율적인 구축 알고리즘
정보과학회논문지 : 시스템 및 이론
2005 .06
-
효율적인 써픽스 배열 합병 알고리즘과 응용
한국정보과학회 학술발표논문집
2004 .04
-
Comparisons of Practical Performance for Constructing Compressed Suffix Arrays
정보과학회논문지 : 시스템 및 이론
2007 .06
-
대용량 DNA 시퀀스 데이타베이스를 위한 효율적인 인덱싱
정보과학회논문지 : 데이타베이스
2004 .12
-
DNA 스트링에 효율적인 써픽스 배열 구축 알고리즘
한국정보과학회 학술발표논문집
2004 .04
-
최장 길이 우선 검색에 기초한 프리픽스 길이에 따른 이진 IP 검색 구조
한국통신학회논문지
2006 .08
-
써픽스 배열을 구축하는 빠른 알고리즘
한국정보과학회 학술발표논문집
2004 .10
-
네트워크 보안을 위한 서픽스 트리 기반 고속 패턴 매칭 알고리즘
전자공학회논문지
2014 .06
-
압축된 써픽스 배열을 직접 구축하는 선형시간 알고리즘
한국정보과학회 학술발표논문집
2003 .04
-
써픽스 배열 합병을 위한 선형 시간 알고리즘
한국정보과학회 영남지부 학술발표논문집
2003 .12
-
비디오 프리픽스-캐슁 기법의 성능 개선
한국통신학회 학술대회논문집
2003 .07
-
IP 주소 검색을 위한 가중 이진 프리픽스 트리
한국통신학회논문지
2004 .11
-
비디오 스트리밍을 위한 효율적인 프리픽스-캐슁 기법
한국통신학회 학술대회논문집
2002 .11
이 논문의 저자 정보
이 논문과 함께 이용한 논문
최근 본 자료
댓글(0)
0
UCI(KEPA) : I410-ECN-0101-2010-569-001635173