단백질 시퀀스와 가중치 스트링에 대한 탐색 알고리즘 = Searching Algorithms for Protein Sequences and Weighted Strings

다국어 초록 (Multilingual Abstract)

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.

국문 초록 (Abstract)

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