More Like this

1. Nanopore decoding with speed and versatility for data storage

   https://doi.org/10.1093/bioinformatics/btaf006  

   Volkel, Kevin D; Hook, Paul W; Keung, Albert; Timp, Winston; Tuck, James M (December 2024, Bioinformatics)

   Mathelier, Anthony (Ed.)

   Abstract MotivationAs nanopore technology reaches ever higher throughput and accuracy, it becomes an increasingly viable candidate for reading out DNA data storage. Nanopore sequencing offers considerable flexibility by allowing long reads, real-time signal analysis, and the ability to read both DNA and RNA. We need flexible and efficient designs that match nanopore’s capabilities, but relatively few designs have been explored and many have significant inefficiency in read density, error rate, or compute time. To address these problems, we designed a new single-read per-strand decoder that achieves low byte error rates, offers high throughput, scales to long reads, and works well for both DNA and RNA molecules. We achieve these results through a novel soft decoding algorithm that can be effectively parallelized on a GPU. Our faster decoder allows us to study a wider range of system designs. ResultsWe demonstrate our approach on HEDGES, a state-of-the-art DNA-constrained convolutional code. We implement one hard decoder that runs serially and two soft decoders that run on GPUs. Our evaluation for each decoder is applied to the same population of nanopore reads collected from a synthesized library of strands. These same strands are synthesized with a T7 promoter to enable RNA transcription and decoding. Our results show that the hard decoder has a byte error rate over 25%, while the prior state of the art soft decoder can achieve error rates of 2.25%. However, that design also suffers a low throughput of 183 s/read. Our new Alignment Matrix Trellis soft decoder improves throughput by 257× with the trade-off of a higher byte error rate of 3.52% compared to the state of the art. Furthermore, we use the faster speed of our algorithm to explore more design options. We show that read densities of 0.33 bits/base can be achieved, which is 4× larger than prior MSA-based decoders. We also compare RNA to DNA, and find that RNA has 85% as many error-free reads when compared to DNA. Availability and implementationSource code for our soft decoder and data used to generate figures is available publicly in the Github repository https://github.com/dna-storage/hedges-soft-decoder (10.5281/zenodo.11454877). All raw FAST5/FASTQ data are available at 10.5281/zenodo.11985454 and 10.5281/zenodo.12014515. 

   more » « less
2. DP-DNA: A Digital Pattern-Aware DNA Encoding Scheme to Improve Encoding Density of DNA Storage

   https://doi.org/10.1109/MASCOTS59514.2023.10387655  

   Li, Bingzhe; Ou, Li; Yuan, Bo; Du, David H.C. (October 2023, IEEE)

   With the rapid increase of available digital data, we are searching for a storage media with high density and capability of long-term preservation. Deoxyribonucleic Acid (DNA) storage is identified as such a promising candidate, especially for archival storage systems. However, the encoding density (i.e., how many binary bits can be encoded into one nucleotide) and error handling are two major factors intertwined in DNA storage. Considering encoding density, theoretically, one nucleotide (i.e., A, T, G, or C) can encode two binary bits (upper bound). However, due to biochemical constraints and other necessary information associated with payload, currently the encoding densities of various DNA storage systems are much less than this upper bound. Additionally, all existing studies of DNA encoding schemes are based on static analysis and really lack the awareness of dynamically changed digital patterns. Therefore, the gap between the static encoding and dynamic binary patterns prevents achieving a higher encoding density for DNA storage systems. In this paper, we propose a new Digital Pattern-Aware DNA storage system, called DP-DNA, which can efficiently store digital data in the DNA storage with high encoding density. DP-DNA maintains a set of encoding codes and uses a digital pattern-aware code (DPAC) to analyze the patterns of a binary sequence for a DNA strand and selects an appropriate code for encoding the binary sequence to achieve a high encoding density. An additional encoding field is added to the DNA encoding format, which can distinguish the encoding scheme used for those DNA strands, and thus we can decode DNA data back to its original digital data. Moreover, to further improve the encoding density, a variable-length scheme is proposed to increase the feasibility of the code scheme with a high encoding density. Finally, the experimental results indicate that the proposed DP-DNA achieves up to 103.5% higher encoding densities than prior work. 

   more » « less
3. Lotus: A Multi-FPGA Task Dataflow Architecture to Accelerate Cycle-Level Simulation

   https://doi.org/10.1109/ISCA66397.2026.00129  

   Elsabbagh, Fares; Emer, Joel S; Sanchez, Daniel (June 2026, IEEE)

   Simulation is crucial to design and build hardware. But simulating large and complex digital designs is slow. Hardware emulators are the standard accelerator for cycle-level RTL simulation, but these systems are expensive, inefficient, slow to compile for, and limited to simulating RTL. Emulators consist of many chips, typically FPGAs, to which the design is compiled. Emulators are bottlenecked by communication, and use FPGAs at a fraction of their speed. We present Lotus, a large-scale architecture that accelerates cycle-level simulation. Lotus uses multiple FPGAs like emulators, but takes a different approach: rather than mapping logic directly to FPGAs, Lotus implements thousands of simple cores, along with hardware support that enables software simulation to scale. Lotus simulates digital systems by encoding them as large dataflow graphs of tiny tasks that run on these cores. Lotus uses dataflow execution to extract abundant parallelism; task priorities to focus work on the critical path; and selective execution to avoid ineffectual work. We contribute new implementations of these techniques that scale to multiple chips and require simple hardware. We also develop a compiler to use Lotus efficiently from high-level dataflow graphs. We build an implementation of Lotus using 8 FPGAs, featuring over two thousand cores. On several large designs, this Lotus prototype achieves speeds comparable to emulators, while reducing the number of FPGAs needed by up to 7.5x and improving performance per FPGA by up to 23x. Lotus is also 8x faster than a 128-core server. Overall, Lotus is the first system to show that software simulation can outperform emulators by leveraging large-scale parallelism. 

   more » « less
4. Simulating 3-symbol Turing machines with SIMD||DNA

   David Doty and Aaron Ong (January 2023, SAND 2022: 1st Symposium on Algorithmic Foundations of Dynamic Networks)

   James Aspnes and Othon Michail (Ed.)

   SIMD||DNA [Wang et al., 2019] is a model of DNA strand displacement allowing parallel in-memory computation on DNA storage. We show how to simulate an arbitrary 3-symbol space-bounded Turing machine with a SIMD||DNA program, giving a more direct and efficient route to general-purpose information manipulation on DNA storage than the Rule 110 simulation of Wang, Chalk, and Soloveichik [Wang et al., 2019]. We also develop software (https://github.com/UC-Davis-molecular-computing/simd-dna) that can simulate SIMD||DNA programs and produce SVG figures. 

   more » « less
5. Regulation of Error-Prone DNA Double-Strand Break Repair and Its Impact on Genome Evolution

   https://doi.org/10.3390/cells9071657  

   Hanscom, Terrence; McVey, Mitch (July 2020, Cells)

   null (Ed.)

   Double-strand breaks are one of the most deleterious DNA lesions. Their repair via error-prone mechanisms can promote mutagenesis, loss of genetic information, and deregulation of the genome. These detrimental outcomes are significant drivers of human diseases, including many cancers. Mutagenic double-strand break repair also facilitates heritable genetic changes that drive organismal adaptation and evolution. In this review, we discuss the mechanisms of various error-prone DNA double-strand break repair processes and the cellular conditions that regulate them, with a focus on alternative end joining. We provide examples that illustrate how mutagenic double-strand break repair drives genome diversity and evolution. Finally, we discuss how error-prone break repair can be crucial to the induction and progression of diseases such as cancer. 

   more » « less