2022/04/20 by Will Solow, Solow, Will, Matthew Barich +3
Biochemistry, Genetics and Molecular Biology · Computer Science · #Algorithms and Data Compression #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Genomics and Phylogenetic Studies #RNA and protein synthesis mechanisms
paper · pdf · doi:10.48550/arxiv.2204.09562
openalex publication_date 2022/04/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
The Exact Circular Pattern Matching (ECPM) problem consists of reporting every occurrence of a rotation of a pattern P in a text T. In many real-world applications, specifically in computational biology, circular rotations are of interest because of their prominence in virus DNA. Thus, given no restrictions on pre-processing time, how quickly all such circular rotation occurrences is of interest to many areas of study. We highlight, to the best of our knowledge, a novel approach to the ECPM problem and present four data structures that accompany this approach, each with their own time-space trade-offs, in addition to experimental results to determine the most computationally feasible data structure.