2024/02/21 by Saumya Talera, Parth Bansal, Talera, Saumya +5
Computer Science · #Data Mining Algorithms and Applications #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Graph Theory and Algorithms
paper · pdf · doi:10.48550/arxiv.2402.13920
openalex publication_date 2024/02/21 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
Genome assembly is a prominent problem studied in bioinformatics, which computes the source string using a set of its overlapping substrings. Classically, genome assembly uses assembly graphs built using this set of substrings to compute the source string efficiently, having a tradeoff between scalability and avoiding information loss. The scalable de Bruijn graphs come at the price of losing crucial overlap information. The complete overlap information is stored in overlap graphs using quadratic space. Hierarchical overlap graphs [IPL20] (HOG) overcome these limitations, avoiding information loss despite using linear space. After a series of suboptimal improvements, Khan and Park et al. simultaneously presented two optimal algorithms [CPM2021], where only the former was seemingly practical. We empirically analyze all the algorithms for computing Hierarchical overlap graphs, where the optimal algorithm~[CPM2021] outperforms the previous algorithms as expected. However, it is still based on relatively complex arguments for its formal proof and uses relatively complex data structures for its implementation. We present an intuitive algorithm, using only elementary arrays, which is also optimal. Our algorithm empirically proves even better for both time and memory over all the algorithms, highlighting its significance in both theory and practice. We further explore the applications of hierarchical overlap graphs to solve variants of suffix-prefix queries on a set of strings, recently studied by Loukides et al.~[CPM2023]. They presented state-of-the-art algorithms requiring complex black-box data structures, making them seemingly impractical. Our algorithms, despite failing to match their theoretical bounds, answer queries in 0.002-100~ms for datasets having around a billion characters.