초록 close

단백질 시퀀스처럼 가중치를 가지는 스트링에 대한 탐색 알고리즘을 개발한다. ∑를 알파벳이라 하고 모든a in Sigma`` 에 대해서 무게 가 주어진다고 하자. 스트링 에서 (단, 모든 ), 서브스트링 로 정의하면, 이것의 무게는 가 된다. 다루고자 하는 문제는 스트링 를 사전 처리하여 탐색 자료구조를 만드는데, 이 자료구조는 나중에 질문 무게 이 주어진 경우, 인 서브스트링 가 있는가 라는 질문에 응답하는데 사용된다. 본 논문에서 는 기존의 결과를 향상시키는 알고리즘을 제시한다. 기존의 알고리즘의 경우 만큼의 메모리를 사용하 는 탐색 자료구조를 이용하여 시간에 질문응답을 하였으나, 본 논문의 알고리즘은 질문 응답 시간은 그대로 유지하면서 메모리만 으로 줄인다.


We are developing searching algorithms for weighted strings such as protein sequences. Let ∑ be an alphabet and for each a in Sigma``its weight is given. Given a string with each , a substring has weight . The problem we are dealing with is to preprocess to build a searching structure, and later, given a query weight , the structure is used to answer the question of whether there is a substring such that . In this paper an algorithm that improves over the previous result will be presented. The previously best known algorithm answers a query in time using a searching structure that requires amount of memory. Our algorithm reduces the memory requirement to while achieving the same query answer time.