[논문]트라이 인덱스를 이용한 DNA 시퀀스 검색

원정임; 박용일; 윤지희; 박상현

트라이 인덱스를 이용한 DNA 시퀀스 검색
DNA Sequence Searching Using a Trie Index 원문보기

원정임 (한림대학교 컴퓨터공학과) , 박용일 (한림대학교 컴퓨터공학과) , 윤지희 (한림대학교 컴퓨터공학과) , 박상현 (연세대학교 컴퓨터과학과)

본 논문에서는 대규모 DNA 시퀀스를 위한 트라이 인덱싱 기법을 기반으로 하는 효율적인 부분 시퀀스 검색 기법을 제시한다. 제안된 인덱싱 방안에서는 저장 공간 감소를 위하여 시퀀스의 각 문자를 최소 비트 정보로 표현하며, 저장 구조로서 포인터를 사용하지 않는 디스크 기반의 이진 접미어 트라이 구조를 사용한다. 질의 처리 방안에서는 포인터가 없는 이진 트라이 구조 상에서 질의 시퀀스를 검색하기 위하여 이진 정보 기반의 연산과정을 필요로 하며, 또한 단말 정보를 효율적으로 검색하기 위하여 별도의 단말정보 테이블과 인덱스 구조를 사용한다. 실험 결과에 의하면 제안된 방식은 기존의 접미어 트리 인덱싱 방식에 비하여 약 30~50%의 저장 공간 감소 효과를 가질 뿐 아니라, 평균 질의 처리 시간에 있어 약 20배까지의 성능 개선 효과를 갖는 것으로 나타났다.

* AI 자동 식별 결과로 적합하지 않은 문장이 있을 수 있으니, 이용에 유의하시기 바랍니다.

문제 정의

' 본 논문에서는 대규모 DNA 시퀀스를 위한 부분 시퀀스 검색 문제에 관하여 논한다. 참고 문헌 [4] 에서는 DNA 시퀀스의 각 문자를 최소 비트 정보로 표현하고, 저장 구조로서 포인터 없는 디스크 기반의 접미어 트라이를 사용하는 새로운 인덱스 구조와 질의 처리 방식을 제안한 바 있다.
이 과정은 인덱스 외 검색 공간을 확대시켜, 알고리즘 성능 저하의 주요 원인으로 작용할 수 있다. 본 연구에서는 이진 트라이 인 덱스 구조상에서 단말 노드 정보를 효율적으로 검색하기 위한 두 가지의 서로 다른 접근 방식을 제안하고 그 성능올 비교, 분석한다. 또한, 제안한 기법의 유용성을 평가하기 위하여 실제의 대규모 DNA 시퀀스를 대상으로 하는 다양한 실험올 수행하여 그 성능을 비교, 분석한다.

가설 설정

트라이 구조를 이진 트라이 구조로 제한하여 이진 데이터 저장 구조로 사용할 수 있다. 또한, 이진 트라이 구조에서 에지 정보가 '0'이 면 왼쪽 에지에, ‘1’이면 오른쪽 에지에 청보가 저장되는 것을 가정함으로써 에지 정보를 생략 표현할 수 있다. 이와 같이 형성된 이진 트라이 구조는 포인터를 사용하지 않눈 이진 데이터 표현이 가능하다.

제안 방법

자. 다차원 인덱스롤 검색하여 p0와 pl 사이에 존재하는 모든 단말 노드들을 검색한다.
트리롤 이용한 방식에서는 단말노드의 페이지 정보에 대하여 B*-트리 인덱스롤 구성하였다. 다차원 인덱스를 이용한 방식에서는 다차원 인덱스서 현재 시퀀스 데이터베이스 분야에서 가장 널리 사용되고 있는 R*-트 리〔기를 사용하였으며, 인덱스 엔트리로서 각 단말 노드를 2개의 정수로 표현하였다. (그림 3)에 제안된 인덱스의 크기를 기존의 접미어 트리 인덱스 기법에 의하여 생성된 인덱스 크기와 비교한 결과를 보인다.
본 연구에서는 이진 트라이 인 덱스 구조상에서 단말 노드 정보를 효율적으로 검색하기 위한 두 가지의 서로 다른 접근 방식을 제안하고 그 성능올 비교, 분석한다. 또한, 제안한 기법의 유용성을 평가하기 위하여 실제의 대규모 DNA 시퀀스를 대상으로 하는 다양한 실험올 수행하여 그 성능을 비교, 분석한다.
실험 1 (인덱스 크기 비교) : 제안된 인덱스 구조에서는 접미어 트라이 인덱스 외에 폐이지 정보와 단말노드 정보를 귈요로 한다. 또한 단말노드의 효율적 검색을 위하여 두 가지의 서로 다른 인덱스를 사용할 수 있다.
또한 단말노드의 효율적 검색을 위하여 두 가지의 서로 다른 인덱스를 사용할 수 있다. 트리롤 이용한 방식에서는 단말노드의 페이지 정보에 대하여 B*-트리 인덱스롤 구성하였다. 다차원 인덱스를 이용한 방식에서는 다차원 인덱스서 현재 시퀀스 데이터베이스 분야에서 가장 널리 사용되고 있는 R*-트 리〔기를 사용하였으며, 인덱스 엔트리로서 각 단말 노드를 2개의 정수로 표현하였다.

대상 데이터

제안된 기법의 성능을 평가하기 위하여 인덱스의 크기 및 질의 처리 시간을 기존 방식과 실험을 통하여 비교 분석한다. 비교 대상의 인덱스 구조로는 디스크 기반의 접미어 트리롤 사용한다. 살험 데이터로는 GenBank[6]로부터 다운받은 Human Chromosome 18~21번의 5가지 DNA 시퀀스롤 사용하였다 시퀀스 내에 출현하는 서로 다른 문자 수는 7~8개이다.
비교 대상의 인덱스 구조로는 디스크 기반의 접미어 트리롤 사용한다. 살험 데이터로는 GenBank[6]로부터 다운받은 Human Chromosome 18~21번의 5가지 DNA 시퀀스롤 사용하였다 시퀀스 내에 출현하는 서로 다른 문자 수는 7~8개이다. 실험을 위한 하드웨어 플랫폼으로는 Windows 2000 Server■를 운영체제로 사용하고, 1GB의 주기억장치, 40GB 디스크를 갖는 Pentium IV 2GHz의 PC< 사용한다.
실험 2 (질의처리 시간 비교) : 제안된 두 가지 방식에 의한 질의 처리 시간을 기존의 접미어 트리 방식과 비교한 결과를 (그림 4)에 보인다. 실험 데이터로는 D(433M)를 사용하였으며, 질의 길이 변화에 따르는 질의 처리 시간을 비교한 결과이다. Y축은 로그 스케일링 되어 있으며, 측정 단위는 msec이다.

데이터처리

제안된 기법의 성능을 평가하기 위하여 인덱스의 크기 및 질의 처리 시간을 기존 방식과 실험을 통하여 비교 분석한다. 비교 대상의 인덱스 구조로는 디스크 기반의 접미어 트리롤 사용한다.

성능/효과

실험 결과에 의하면 Trie(B+Tree)는 질의 길이가 짧은 경우, 단말노드 검색을 위한 트라이 인덱스 검색 시간이 증가하여 전체 검색 시간이 증가하지만, 질의 길이가 긴 경우, 질의처리 시간이 현저히 감소함을 볼 수 있다. 반면에 Trie(R*Tree)눈 질의 길이에 무관하게 거의 일정한 질의 처리 시간을 나타내며, Suffix에 비하여 약 20배의 성능 감소 효과를 나타내는 것으로 나타났다.
(그림 3)에서 Trie(B+Tree) 와 Trie(R*Tree)는 단말노드 검색 방식으로 각각 B' 트리R*-트리 방식을 사용한 경우를 나타내며, Suffix는 비교 대상의 접미어 트리 검색 방식을 나타낸다. 실험 결과로부터 제안된 방식 중, Trie(B+Tree)는 Suffix에 비하여 약 50%의 저장 공간 감소 효과를 나타내고, Trie(R*Tree)는 Suffix에 비하여 약 30%의 저장 공간 감소 효과를 나타내는 것으로 나타났다.
Y축은 로그 스케일링 되어 있으며, 측정 단위는 msec이다. 실험 결과에 의하면 Trie(B+Tree)는 질의 길이가 짧은 경우, 단말노드 검색을 위한 트라이 인덱스 검색 시간이 증가하여 전체 검색 시간이 증가하지만, 질의 길이가 긴 경우, 질의처리 시간이 현저히 감소함을 볼 수 있다. 반면에 Trie(R*Tree)눈 질의 길이에 무관하게 거의 일정한 질의 처리 시간을 나타내며, Suffix에 비하여 약 20배의 성능 감소 효과를 나타내는 것으로 나타났다.
참고 문헌 [4] 에서는 DNA 시퀀스의 각 문자를 최소 비트 정보로 표현하고, 저장 구조로서 포인터 없는 디스크 기반의 접미어 트라이를 사용하는 새로운 인덱스 구조와 질의 처리 방식을 제안한 바 있다. 실험 결과에 의하면 제안된 인덱스 방식은 기존의 접미어 트리 방식에 비하여 약 50%의 저 창 공간 감소 효과를 갖는 것으로 나타났다. 본 연구는 [4] 의 선행 연구 결과롤 활용, 확장한 후속 연구로서, 그 주요 내용은 다음과 같다.

원문 보기

ScienceON 원문보기

*원문 PDF 파일 및 링크정보가 존재하지 않을 경우 KISTI DDS 시스템에서 제공하는 원문복사서비스를 사용할 수 있습니다.

내보내기 메뉴

내보내기 구분

파일저장
인쇄
메일전송

구성항목

기본정보
상세정보

관리번호, 논문명, 저널/프로시딩명, 저자 , 발행년, 권, 호, 시작페이지, 끝페이지, 발행기관

저장형식

Text(ASCII format)
Excel format
RefWorks Direct Export
RIS format (for Reference Manager, ProCite, EndNote), Scholar's Aids, Mendeley

메일정보

받는사람 (필수): @
보내는사람 (선택): @
제목
내용: KISTI 검색결과 이메일 서비스

안내

총 건의 자료가 검색되었습니다.

다운받으실 자료의 인덱스를 입력하세요. (1-10,000)

검색결과의 순서대로 최대 10,000건 까지 다운로드가 가능합니다.

데이타가 많을 경우 속도가 느려질 수 있습니다.(최대 2~3분 소요)

다운로드 파일은 UTF-8 형태로 저장됩니다.
파일의 내용이 제대로 보이지 않을실 때는 웹브라우저 상단의 보기 -> 인코딩 -> 자동선택 여부를 확인하십시오.

Text(ASCII format)
Excel format

표제어: PCR

동의어: Packet Collision Rate

용어 설명 출처 목록 (6)

용어 설명: PCR은 세균 특이성이 있는 primer를 이용하여 적은 수의 세균이 있을지라도 쉽게 검출할 수 있는 유용한 방법이며, 이를 이용하여 구강 내 치면세균막이나 타액에서 직접 세균을 검출할 수 있게 되었다[8].

AI-Helper ※ AI-Helper는 을 사용합니다.

AI-Helper

안녕하세요, AI-Helper입니다. 좌측 "선택된 텍스트"에서 텍스트를 선택하여 요약, 번역, 용어설명을 실행하세요.
※ AI-Helper는 부적절한 답변을 할 수 있습니다.

연합인증

트라이 인덱스를 이용한 DNA 시퀀스 검색
DNA Sequence Searching Using a Trie Index 원문보기

초록
AI-Helper