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 |
|---|---|---|---|---|
| 2,219 | WHAM: A High-throughput Sequence Alignment Method | 2011 | SIGMOD | 8.9998232e-05 |
| 5,605 | Pigeonring: A Principle for Faster Thresholded Similarity Search | 2019 | VLDB | 6.2161107e-05 |
| 6,753 | A Generic Framework for Efficient and Effective Subsequence Retrieval | 2012 | VLDB | 5.8414302e-05 |
| 12,094 | RCSI: Scalable similarity search in thousand(s) of genomes | 2013 | VLDB | 5.1725247e-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,026 | VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams | 2007 | VLDB | 0.00012661091 |
| 2,055 | Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently | 2008 | SIGMOD | 9.3220009e-05 |
| 2,224 | n-Gram/2L: A Space and Time Efficient Two-Level n-Gram Inverted Index Structure | 2005 | VLDB | 8.992609e-05 |
| 3,113 | OASIS: An Online and Accurate Technique for Local-alignment Searches on Biological Sequences | 2003 | VLDB | 7.7983445e-05 |
| 3,367 | Approximate Embedding-Based Subsequence Matching of Time Series | 2008 | SIGMOD | 7.5433008e-05 |
| 5,562 | Fast nGram-Based String Search Over Data Encoded Using Algebraic Signatures | 2007 | VLDB | 6.2337613e-05 |
| 6,392 | Reference-Based Indexing of Sequence Databases | 2006 | VLDB | 5.9556329e-05 |
Previous
Page 1 / 1
Next
Semantically Similar Papers
| Overall Rank | Paper | Year | Venue | Pagerank |
|---|---|---|---|---|
| 5,495 | Ranked Subsequence Matching in Time-Series Databases | 2007 | VLDB | 6.2653095e-05 |
| 9,935 | Efficient and Effective KNN Sequence Search with Approximate n-grams | 2014 | VLDB | 5.2359544e-05 |
| 3,113 | OASIS: An Online and Accurate Technique for Local-alignment Searches on Biological Sequences | 2003 | VLDB | 7.7983445e-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 | 5.1725247e-05 |
| 3,367 | Approximate Embedding-Based Subsequence Matching of Time Series | 2008 | SIGMOD | 7.5433008e-05 |
| 6,753 | A Generic Framework for Efficient and Effective Subsequence Retrieval | 2012 | VLDB | 5.8414302e-05 |
| 8,682 | ALAE: Accelerating Local Alignment with Affine Gap Exactly in Biosequence Databases | 2012 | VLDB | 5.4529717e-05 |
| 7,493 | Efficient Top-k Algorithms for Approximate Substring Matching | 2013 | SIGMOD | 5.6670665e-05 |
| 6,392 | Reference-Based Indexing of Sequence Databases | 2006 | VLDB | 5.9556329e-05 |