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)

Paper ID: 10063
Venue: VLDB
Year: 2009
Pagerank: 5.9493566e-05
Overall Rank: 6,182 | 57.59%
DOI: 10.14778/1687627.1687651

Incoming Non-self Citations Over Time

Authors

1. Panagiotis Papapetrou (Boston University)
2. Vassilis Athitsos (University of Texas)
3. George Kollios (Boston University)
4. Dimitrios Gunopulos (University of Athens; University of California Riverside)

BibTeX Citation

@article{papapetrou_vldb09,
        title = {{Reference-Based Alignment in Large Sequence Databases}},
        author = {Papapetrou, Panagiotis and Athitsos, Vassilis and Kollios, George and Gunopulos, Dimitrios},
        journal = {PVLDB},
        series = {{VLDB} '09},
        doi = {10.14778/1687627.1687651},
        url = {https://doi.org/10.14778/1687627.1687651},
        year = {2009}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,459	WHAM: A High-throughput Sequence Alignment Method	2011	SIGMOD	8.550768e-05
5,726	Pigeonring: A Principle for Faster Thresholded Similarity Search	2019	VLDB	6.1079184e-05
6,858	A Generic Framework for Efficient and Effective Subsequence Retrieval	2012	VLDB	5.7523396e-05
12,283	RCSI: Scalable similarity search in thousand(s) of genomes	2013	VLDB	5.093636e-05

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,040	VGRAM: Improving Performance of Approximate Queries on String Collections Using Variable-Length Grams	2007	VLDB	0.00012466499
2,103	Cost-Based Variable-Length-Gram Selection for String Collections to Support Approximate Queries Efficiently	2008	SIGMOD	9.1621686e-05
2,262	n-Gram/2L: A Space and Time Efficient Two-Level n-Gram Inverted Index Structure	2005	VLDB	8.8440146e-05
3,164	OASIS: An Online and Accurate Technique for Local-alignment Searches on Biological Sequences	2003	VLDB	7.6778551e-05
3,440	Approximate Embedding-Based Subsequence Matching of Time Series	2008	SIGMOD	7.4142918e-05
5,691	Fast nGram-Based String Search Over Data Encoded Using Algebraic Signatures	2007	VLDB	6.120274e-05
6,496	Reference-Based Indexing of Sequence Databases	2006	VLDB	5.8632988e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	5,592	Ranked Subsequence Matching in Time-Series Databases	2007	VLDB
2	3,164	OASIS: An Online and Accurate Technique for Local-alignment Searches on Biological Sequences	2003	VLDB
3	10,086	Efficient and Effective KNN Sequence Search with Approximate n-grams	2014	VLDB
4	13,474	On the String Matching with k Differences in DNA Databases	2021	VLDB
5	12,283	RCSI: Scalable similarity search in thousand(s) of genomes	2013	VLDB
6	3,440	Approximate Embedding-Based Subsequence Matching of Time Series	2008	SIGMOD
7	6,858	A Generic Framework for Efficient and Effective Subsequence Retrieval	2012	VLDB
8	8,803	ALAE: Accelerating Local Alignment with Affine Gap Exactly in Biosequence Databases	2012	VLDB
9	7,692	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD
10	6,496	Reference-Based Indexing of Sequence Databases	2006	VLDB