OASIS: An Online and Accurate Technique for Local-alignment Searches on Biological Sequences Colin Meek, Jignesh M. Patel, and Shruti Kasetty   View Paper (PDF)   Return to Potpourri - Access Control, Bioinformatics & Security (Session C10) Abstract A common query against large protein and gene sequence data sets is to locate targets that are similar to an input query sequence. The cur- rent set of popular search tools, such as BLAST, employ heuristics to improve the speed of such searches. However, such heuristics can some- times miss targets, which in many cases is unde- sirable. The alternative to BLAST is to use an accurate algorithm, such as the Smith-Waterman (S-W) algorithm. However, these accurate algo- rithms are computationally very expensive, which limits their use in practice. This paper takes on the challenge of designing an accurate and efficient algorithm for evaluating local-alignment searches. To meet this goal, we propose a novel search al- gorithm, called OASIS. This algorithm employs a dynamic programming A*-search driven by a suffix-tree index that is built on the input data set. We experimentally evaluate OASIS and demon- strate that for an important class of searches, in which the query sequence lengths are small, OA- SIS is more than an order of magnitude faster than S-W. In addition, the speed of OASIS is compa- rable to BLAST. Furthermore, OASIS returns re- sults in decreasing order of the matching score, making it possible to use OASIS in an online set- ting. Consequently, we believe that it may now be practically feasible to query large biological se- quence data sets using an accurate local-alignment search algorithm. ©2004 Association for Computing Machinery