Reference-Based Alignment in Large Sequence Databases
Summary: RBSA speeds up optimal subsequence retrieval under edit distance and Smith-Waterman by reference-based filtering, assuming the best match deviates only slightly from the query. Query segments of fixed-length with precomputed reference scores and alphabet collapsing enable strong pruning; exact and approximate RBSA outperform q-grams, BLAST, and BWT. (summarized by gpt-5-nano on Feb 09 2026)
Incoming Non-self Citations Over Time
Authors
Incoming Citations (Sorted by Pagerank)
Showing 4 of 4 citing papers.
| Rank | Citing Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,947 | WHAM: A High-throughput Sequence Alignment Method | 2011 | SIGMOD | 9.9963826e-05 |
| 6,080 | Pigeonring: A Principle for Faster Thresholded Similarity Search | 2019 | VLDB | 5.219249e-05 |
| 6,982 | A Generic Framework for Efficient and Effective Subsequence Retrieval | 2012 | VLDB | 4.8685999e-05 |
| 12,094 | RCSI: Scalable similarity search in thousand(s) of genomes | 2013 | VLDB | 4.1905499e-05 |
Previous
Page 1 / 1
Next
Outgoing Citations (Sorted by Pagerank)
Showing 7 of 7 cited papers.
Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.
| Rank | Cited Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 1,203 | VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams | 2007 | VLDB | 0.00013317317 |
| 2,196 | Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently | 2008 | SIGMOD | 9.318552e-05 |
| 2,215 | n-Gram/2L: A Space and Time Efficient Two-Level n-Gram Inverted Index Structure | 2005 | VLDB | 9.2695849e-05 |
| 2,500 | OASIS: An Online and Accurate Technique for Local-alignment Searches on Biological Sequences | 2003 | VLDB | 8.6388583e-05 |
| 3,297 | Approximate Embedding-Based Subsequence Matching of Time Series | 2008 | SIGMOD | 7.2549403e-05 |
| 5,404 | Fast nGram-Based String Search Over Data Encoded Using Algebraic Signatures | 2007 | VLDB | 5.5247333e-05 |
| 6,458 | Reference-Based Indexing of Sequence Databases | 2006 | VLDB | 5.0484248e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,883 | Ranked Subsequence Matching in Time-Series Databases | 2007 | VLDB | 5.2865165e-05 |
| 9,934 | Efficient and Effective KNN Sequence Search with Approximate n-grams | 2014 | VLDB | 4.245954e-05 |
| 2,500 | OASIS: An Online and Accurate Technique for Local-alignment Searches on Biological Sequences | 2003 | VLDB | 8.6388583e-05 |
| 13,285 | On the String Matching with k Differences in DNA Databases | 2021 | VLDB | - |
| 12,094 | RCSI: Scalable similarity search in thousand(s) of genomes | 2013 | VLDB | 4.1905499e-05 |
| 3,297 | Approximate Embedding-Based Subsequence Matching of Time Series | 2008 | SIGMOD | 7.2549403e-05 |
| 6,982 | A Generic Framework for Efficient and Effective Subsequence Retrieval | 2012 | VLDB | 4.8685999e-05 |
| 8,701 | ALAE: Accelerating Local Alignment with Affine Gap Exactly in Biosequence Databases | 2012 | VLDB | 4.4599782e-05 |
| 7,707 | Efficient Top-k Algorithms for Approximate Substring Matching | 2013 | SIGMOD | 4.6676985e-05 |
| 6,458 | Reference-Based Indexing of Sequence Databases | 2006 | VLDB | 5.0484248e-05 |