SimSearcher: A local similarity search engine for biological sequence databases

Abstract

In this paper an efficient local similarity search engine is developed exploiting some techniques of data mining. First of all, all frequent patterns in the database are retrieved and recorded in a one-time preprocessing process. Then a query sequence is checked for whether any pattern from the preprocessing stage is matched to the query. Two regions coming from the query and a database sequence that both match to a pattern form a possible seed for the local similarity. Finally, we extend and score each such seed region pair to see whether there really exists a local similarity with a score high enough for reporting. For computational efficiency, a novel clustering approach is proposed and is integrated into the proposed system, which is based on the local similarity search engine - DELPHI system proposed by IBM. Extensive experiments are demonstrated to show the performance of our system.