On the String Matching with k Differences in DNA Databases

Summary: Introduces a BWT(y)-based index for approximate DNA-string matching with insertions, deletions, and mismatches. Pattern decomposition enables candidate filtering and verification in O(k|T|) time, with average |T|=O(|Σ|^{2k}), outperforming prior methods for small k. (summarized by gpt-5.6-luna on Jul 24 2026)

Paper ID: 12793
Venue: VLDB
Year: 2021
Pagerank: -
Overall Rank: 13,474 | 7.56%
DOI: 10.14778/3447689.3447695

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

1. Yangjun Chen (University of Winnipeg)
2. Hoang Hai Nguyen (University of Winnipeg)

BibTeX Citation

@article{chen_vldb21,
        title = {{On the String Matching with k Differences in DNA Databases}},
        author = {Chen, Yangjun and Nguyen, Hoang Hai},
        journal = {PVLDB},
        series = {{VLDB} '21},
        volume = {14},
        number = {6},
        pages = {903--915},
        doi = {10.14778/3447689.3447695},
        url = {https://doi.org/10.14778/3447689.3447695},
        year = {2021}
}

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 0 of 0 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	6,858	A Generic Framework for Efficient and Effective Subsequence Retrieval	2012	VLDB
2	6,182	Reference-Based Alignment in Large Sequence Databases	2009	VLDB
3	3,470	Practical Suffix Tree Construction	2004	VLDB
4	8,542	Online Windowed Subsequence Matching over Probabilistic Sequences	2012	SIGMOD
5	5,691	Fast nGram-Based String Search Over Data Encoded Using Algebraic Signatures	2007	VLDB
6	12,558	Improving Suffix Array Locality for Fast Pattern Matching on Disk	2008	SIGMOD
7	6,496	Reference-Based Indexing of Sequence Databases	2006	VLDB
8	2,036	Bed-Tree: An All-Purpose Index Structure for String Similarity Search Based on Edit Distance	2010	SIGMOD
9	7,692	Efficient Top-k Algorithms for Approximate Substring Matching	2013	SIGMOD
10	4,776	An Efficient Index Structure for String Databases	2001	VLDB