A Randomized Parallel Algorithm for Efficiently Finding Near-Optimal Universal Hitting Sets
© Springer Nature Switzerland AG 2020. As the volume of next generation sequencing data increases, an urgent need for algorithms to efficiently process the data arises. Universal hitting sets (UHS) were recently introduced as an alternative to the central idea of minimizers in sequence analysis with...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Springer International Publishing
2022
|
| Online Access: | https://hdl.handle.net/1721.1/145593 |
| _version_ | 1826201928785199104 |
|---|---|
| author | Ekim, Barış Berger, Bonnie Orenstein, Yaron |
| author2 | Massachusetts Institute of Technology. Department of Mathematics |
| author_facet | Massachusetts Institute of Technology. Department of Mathematics Ekim, Barış Berger, Bonnie Orenstein, Yaron |
| author_sort | Ekim, Barış |
| collection | MIT |
| description | © Springer Nature Switzerland AG 2020. As the volume of next generation sequencing data increases, an urgent need for algorithms to efficiently process the data arises. Universal hitting sets (UHS) were recently introduced as an alternative to the central idea of minimizers in sequence analysis with the hopes that they could more efficiently address common tasks such as computing hash functions for read overlap, sparse suffix arrays, and Bloom filters. A UHS is a set of k-mers that hit every sequence of length L, and can thus serve as indices to L-long sequences. Unfortunately, methods for computing small UHSs are not yet practical for real-world sequencing instances due to their serial and deterministic nature, which leads to long runtimes and high memory demands when handling typical values of k (e.g. k > 13). To address this bottleneck, we present two algorithmic innovations to significantly decrease runtime while keeping memory usage low: (i) we leverage advanced theoretical and architectural techniques to parallelize and decrease memory usage in calculating k-mer hitting numbers; and (ii) we build upon techniques from randomized Set Cover to select universal k-mers much faster. We implemented these innovations in PASHA, the first randomized parallel algorithm for generating near-optimal UHSs, which newly handles k > 13. We demonstrate empirically that PASHA produces sets only slightly larger than those of serial deterministic algorithms; moreover, the set size is provably guaranteed to be within a small constant factor of the optimal size. PASHA’s runtime and memory-usage improvements are orders of magnitude faster than the current best algorithms. We expect our newly-practical construction of UHSs to be adopted in many high-throughput sequence analysis pipelines. |
| first_indexed | 2024-09-23T11:59:05Z |
| format | Article |
| id | mit-1721.1/145593 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T11:59:05Z |
| publishDate | 2022 |
| publisher | Springer International Publishing |
| record_format | dspace |
| spelling | mit-1721.1/1455932022-10-04T03:26:59Z A Randomized Parallel Algorithm for Efficiently Finding Near-Optimal Universal Hitting Sets Ekim, Barış Berger, Bonnie Orenstein, Yaron Massachusetts Institute of Technology. Department of Mathematics Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © Springer Nature Switzerland AG 2020. As the volume of next generation sequencing data increases, an urgent need for algorithms to efficiently process the data arises. Universal hitting sets (UHS) were recently introduced as an alternative to the central idea of minimizers in sequence analysis with the hopes that they could more efficiently address common tasks such as computing hash functions for read overlap, sparse suffix arrays, and Bloom filters. A UHS is a set of k-mers that hit every sequence of length L, and can thus serve as indices to L-long sequences. Unfortunately, methods for computing small UHSs are not yet practical for real-world sequencing instances due to their serial and deterministic nature, which leads to long runtimes and high memory demands when handling typical values of k (e.g. k > 13). To address this bottleneck, we present two algorithmic innovations to significantly decrease runtime while keeping memory usage low: (i) we leverage advanced theoretical and architectural techniques to parallelize and decrease memory usage in calculating k-mer hitting numbers; and (ii) we build upon techniques from randomized Set Cover to select universal k-mers much faster. We implemented these innovations in PASHA, the first randomized parallel algorithm for generating near-optimal UHSs, which newly handles k > 13. We demonstrate empirically that PASHA produces sets only slightly larger than those of serial deterministic algorithms; moreover, the set size is provably guaranteed to be within a small constant factor of the optimal size. PASHA’s runtime and memory-usage improvements are orders of magnitude faster than the current best algorithms. We expect our newly-practical construction of UHSs to be adopted in many high-throughput sequence analysis pipelines. 2022-09-27T18:32:00Z 2022-09-27T18:32:00Z 2020 2022-09-27T18:27:21Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/145593 Ekim, Barış, Berger, Bonnie and Orenstein, Yaron. 2020. "A Randomized Parallel Algorithm for Efficiently Finding Near-Optimal Universal Hitting Sets." Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), 12074. en 10.1007/978-3-030-45257-5_3 Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer International Publishing bioRxiv |
| spellingShingle | Ekim, Barış Berger, Bonnie Orenstein, Yaron A Randomized Parallel Algorithm for Efficiently Finding Near-Optimal Universal Hitting Sets |
| title | A Randomized Parallel Algorithm for Efficiently Finding Near-Optimal Universal Hitting Sets |
| title_full | A Randomized Parallel Algorithm for Efficiently Finding Near-Optimal Universal Hitting Sets |
| title_fullStr | A Randomized Parallel Algorithm for Efficiently Finding Near-Optimal Universal Hitting Sets |
| title_full_unstemmed | A Randomized Parallel Algorithm for Efficiently Finding Near-Optimal Universal Hitting Sets |
| title_short | A Randomized Parallel Algorithm for Efficiently Finding Near-Optimal Universal Hitting Sets |
| title_sort | randomized parallel algorithm for efficiently finding near optimal universal hitting sets |
| url | https://hdl.handle.net/1721.1/145593 |
| work_keys_str_mv | AT ekimbarıs arandomizedparallelalgorithmforefficientlyfindingnearoptimaluniversalhittingsets AT bergerbonnie arandomizedparallelalgorithmforefficientlyfindingnearoptimaluniversalhittingsets AT orensteinyaron arandomizedparallelalgorithmforefficientlyfindingnearoptimaluniversalhittingsets AT ekimbarıs randomizedparallelalgorithmforefficientlyfindingnearoptimaluniversalhittingsets AT bergerbonnie randomizedparallelalgorithmforefficientlyfindingnearoptimaluniversalhittingsets AT orensteinyaron randomizedparallelalgorithmforefficientlyfindingnearoptimaluniversalhittingsets |