OASIS: An Online and Accurate Technique for Local-alignment Searches on Biological Sequences

Summary: OASIS uses an A*-search over a suffix-tree index to deliver accurate Smith–Waterman local alignments on large biological datasets. For short queries it is an order of magnitude faster than SW, comparable to BLAST, and returns results in decreasing score for online use. (summarized by gpt-5-nano on Feb 09 2026)

Paper ID: 9225
Venue: VLDB
Year: 2003
Pagerank: 7.6778551e-05
Overall Rank: 3,164 | 78.30%
DOI: 10.1016/B978-012722442-8/50085-9

Incoming Non-self Citations Over Time

Authors

1. Colin Meek (University of Michigan)
2. Jignesh M. Patel (University of Michigan)
3. Shruti Kasetty (University of Michigan)

BibTeX Citation

@article{meek_vldb03,
        title = {{OASIS: An Online and Accurate Technique for Local-alignment Searches on Biological Sequences}},
        author = {Meek, Colin and Patel, Jignesh M. and Kasetty, Shruti},
        journal = {PVLDB},
        series = {{VLDB} '03},
        doi = {10.1016/B978-012722442-8/50085-9},
        url = {https://doi.org/10.1016/B978-012722442-8/50085-9},
        year = {2003}
}

Incoming Citations (Sorted by Pagerank)

Showing 9 of 9 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
3,470	Practical Suffix Tree Construction	2004	VLDB	7.3893019e-05
5,242	Serial and Parallel Methods for I/O Efficient Suffix Tree Construction	2009	SIGMOD	6.3019356e-05
5,726	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.1079184e-05
6,182	Reference-Based Alignment in Large Sequence Databases	2009	VLDB	5.9493566e-05
6,496	Reference-Based Indexing of Sequence Databases	2006	VLDB	5.8632988e-05
6,780	Discovering Longest-lasting Correlation in Sequence Databases	2013	VLDB	5.7766335e-05
8,803	ALAE: Accelerating Local Alignment with Affine Gap Exactly in Biosequence Databases	2012	VLDB	5.3684984e-05
9,973	Exploiting Structure in Regular Expression Queries	2023	SIGMOD	5.1845938e-05
10,396	Regular Expression Indexing for Log Analysis	2026	SIGMOD	5.093636e-05

Outgoing Citations (Sorted by Pagerank)

Showing 3 of 3 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
430	A Fast Index for Semistructured Data	2001	VLDB	0.00018600166
2,008	A Database Index to Large Biological Sequences	2001	VLDB	9.310515e-05
4,776	An Efficient Index Structure for String Databases	2001	VLDB	6.513844e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	10,086	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB
2	7,692	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD
3	2,143	An Approximate Search Engine for Structural Databases	2000	SIGMOD
4	12,558	Improving Suffix Array Locality for Fast Pattern Matching on Disk	2008	SIGMOD
5	12,841	Searching on the Secondary Structure of Protein Sequences	2002	VLDB
6	6,496	Reference-Based Indexing of Sequence Databases	2006	VLDB
7	12,183	Online Ordering of Overlapping Data Sources	2014	VLDB
8	6,182	Reference-Based Alignment in Large Sequence Databases	2009	VLDB
9	5,846	Continuously Adaptive Similarity Search	2020	SIGMOD
10	8,803	ALAE: Accelerating Local Alignment with Affine Gap Exactly in Biosequence Databases	2012	VLDB