2015/12/01 by Wing-Kai Hon, Sharma V. Thankachan, Hon, Wing-Kai +3 · 1 citation
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #DNA and Biological Computing #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genomic variations and chromosomal abnormalities #cs.DS
paper · pdf · doi:10.48550/arxiv.1512.00378
15 pages. A preliminary version of this paper appears in Proceedings of the 26th International Symposium on Algorithms and Computation (ISAAC), Nagoya, Japan, 2015
arxiv created 2015/12/01 · openalex publication_date 2015/12/01 · arxiv updated 2015/12/02 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We revisit the exact shortest unique substring (SUS) finding problem, and propose its approximate version where mismatches are allowed, due to its applications in subfields such as computational biology. We design a generic in-place framework that fits to solve both the exact and approximate k-mismatch SUS finding, using the minimum 2n memory words plus n bytes space, where n is the input string size. By using the in-place framework, we can find the exact and approximate k-mismatch SUS for every string position using a total of O(n) and O(n2) time, respectively, regardless of the value of k. Our framework does not involve any compressed or succinct data structures and thus is practical and easy to implement.