Searching Algorithms for Protein Sequences and Weighted Strings
Sung-Kwon Kim · Jeongbo gwahaghoe nonmunji. si'seu'tem mich i'lon · 2002
We are developing searching algorithms for weighted strings such as protein sequences. Let be an alphabet and for each its weight is given. Given a string , a substring has weight .The problem we are dealing with is to preprocess A to build a searching structure, and later, given a query weight M, the structure is used to answer the question of whether there is a substring A(i,j) 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 O(n) amount of memory. Our algorithm reduces the memory requirement to while achieving the same query answer time.