초록

용어보기논문에서 용어와 풀이말을 자동 추출한 결과로, 시범 서비스 중입니다. AI-Helper

대표적인 인덱스 자료 구조인 써픽스 트리와 써픽스 배열은 긴 문자열에서 임의의 패턴을 검색하는 데 효율적이다. 써픽스 트리는 써픽스 배열보다 큰공간을 차지하지만, 이미 구축된 써픽스 트리의 정보를 이용하여 쉽게 합병할 수 있다. 본 논문에서는 문자열 A와 B에 대한 써픽스 배열이 구축되어 있을 때 A#B$의 일반화된 써픽스 배열을 구축하기 위한 합병 알고리즘을 두 가지 제시하였다. 이 알고리즘을 사용하면 기존의 유전체 서열 써픽스 배열을 재사용하는 방식으로 합병하여, 빠른 시간 안에 효율적으로 합병된 써픽스 배열을 만들 수 있다. 실험 결과, 합병 알고리즘은 일반화된 써픽스 배열을 다시 구축하는 것보다 5배정도 빠른 속도를 보였다.

대표적인 인덱스 자료 구조인 써픽스 트리와 써픽스 배열은 긴 문자열에서 임의의 패턴을 검색하는 데 효율적이다. 써픽스 트리는 써픽스 배열보다 큰공간을 차지하지만, 이미 구축된 써픽스 트리의 정보를 이용하여 쉽게 합병할 수 있다. 본 논문에서는 문자열 A와 B에 대한 써픽스 배열이 구축되어 있을 때 A#B$의 일반화된 써픽스 배열을 구축하기 위한 합병 알고리즘을 두 가지 제시하였다. 이 알고리즘을 사용하면 기존의 유전체 서열 써픽스 배열을 재사용하는 방식으로 합병하여, 빠른 시간 안에 효율적으로 합병된 써픽스 배열을 만들 수 있다. 실험 결과, 합병 알고리즘은 일반화된 써픽스 배열을 다시 구축하는 것보다 5배정도 빠른 속도를 보였다.

AI 본문요약

엑셀 다운로드 AI-Helper

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

• 연구 주제
• 연구 방법
• 연구 결과

문제 정의

• 본 논문에서는 알파벳이 고정되어 있을 때, 이미 구축된 두 써 픽스 배열을 직접 합병하여 일반화된 써픽스 배열을 구축할 수 있는 효율적인 알고리즘을 두 가지 제시하였다. 이 알고리즘들은 유전체 서열간의 상관관계를 파악하는데 필요한 일반화된 써픽스 배열올 빠른 시간 안에 .
• 써픽스 트리를 구축하는 방법 중 대표적인의 알고리즘들[1, 3, 4] 역시 기존 트리에서 검색을 통해 새로운 접미사를 삽입하는 방법을 사용하였다. 인덱스 자료 구조 상의 검색 방법은 전위 검색 (forward search)와 후위 검색(backward search)으로 구분할 수 있으며, 본 논문에서는 이 두 가지 검색 방법을 사용한 써 픽스 배열 합병 알고리즘을 제시하고자 한다.

가설 설정

• 길이 zi인 문자열 A와 길이 m인 문자열 B에 대한 써픽스 배열이 이미 구축되어 있다고 가정하고, 4의 써픽스 배열을 pOSA, B의 써픽스 배열을 QOSB라 홍}자. QOSA상에서 B의 접미사들과 가장 일치하는 부분을 검색하여 그 위치에 삽입하면 두 써 픽스 배열올 합병할 수 있다.

제안 방법

• Aboulehoda et al.⑸은 써픽스 배열을 써픽스 트리처럼 탑다운(top-down) 방식으로 순회할 수 있도록 수정한, 향상된 써 픽스 배열(enhanced suffix array)을 제시하였다. 이 정보는 up, down, ne;出Index의 세 가지 필드로 이루어지지만, 실제 하나의 필드에 저장할 수 있다.
• 본 논문에서는 상수 알파벳에서 정의된 문자열 A와 8에 대한 써픽스 배열이 이미 구축되어 있을 때, A#B$의 써픽土 배열을 다시 구축하지 않고 직접 합병하는 선형시간 알고리즘을 두 가지 제시하였다.
• 전위 검색 방범을 사용하기 위해 써픽스 링크가 필요하였는데, 본 논문에서는 써픽스 배열 상에서 써픽스 링크를 정의하여 이와 같은 전위 검색 방법을 사용할 수 있도록 하였다. 써픽스 링크를 계산하기 위해서는 향상된 써픽스 배열 상에서 전위 깊이 우선 순회(preorder depth-first traverse)를 통해 최대로 일치하는 접두사를 찾아야 한다, 우선 뿌리 구간 [L기의 첫 번째 자식 구간부터 써픽스 링크를 찾는다.
• 합병 알고리즘의 효율성을 검증하기 위하여, 본 논문의 써 픽스 배열 합병 알고리즘의 수행 시간과 의 써픽스 배열을 다시 구축하는[1 낀 시간올 비교해보았다., 와 3의 길이는 같다고 가정하여, 각기 IM, 5M, 10M, 30M 크기의 임의 생성 문자열을 대상으로, 알파벳의 크기롤 2, 4, 64, 128로 변화시키며, Pentium 4 2.

대상 데이터

• 다시 구축하는[1 낀 시간올 비교해보았다., 와 3의 길이는 같다고 가정하여, 각기 IM, 5M, 10M, 30M 크기의 임의 생성 문자열을 대상으로, 알파벳의 크기롤 2, 4, 64, 128로 변화시키며, Pentium 4 2.8Ghz, 2GB RAM의 컴퓨터상에서 실험하였다.

이론/모형

• 후위 검색온 Burrow-Wheeler 변환[기에 기반을 둔 검색 방법으로 압축된 써픽스 배열(compressed suffix array)의 검색에서도 사용되었다[8, 9]. 최근 Hon et 이은 후위 검색 올 사용하면 써픽스 배열을 합병할 수 있음을 밝혔고, Sim et aL[ll]은 후위 검색의 속도를 증가시켰다.

성능/효과

• 구축해야 했다. 그러나 본 논문에서 제시한 합병 알고리즘을 사용하면 일반화된 써픽스 배열을 효올적으로 구축할 수 있게 된다. 이렇게 일반화된 써픽스 배열은 유전체 서열 간 상관관계를 찾는 것에 응용될 수 있다.
• 실험 결과, 두 써픽스 배열을 합병하는 것은 辨B$의 써 픽스배열을 다시 구축하는 것에 비해 5배 정도 빠른 속도를 보였다. 이 알고리즘을 사용하면 큰 용량의 유전체 서열의 상관관계를 파악하기 위해 새로운 써픽스 배열을 구축할 필요 없이 두 써픽스 배열을 합병하여 효율적으로 처리할 수 있게 된다.
• 5배 정도 빠르다. 전위 검색 방법을 사용한 합병 알고리즘은 알파벳이 작을 때(2, 4), 후위 검색 방법을 사용한 합병 알고리즘은 알파벳이 클 때(64, 128) 빠른 속도를 보였다.

본문요약 정보가 도움이 되었나요? 예 아니오 제출

이 논문을 인용한 문헌

더보기