Efficient trace reconstruction in DNA storage systems using Bidirectional Beam Search

Abstract

MotivationAs DNA data storage systems gain popularity, the need for an efficient trace reconstruction algorithm becomes increasingly important. These algorithms aim to reconstruct the original encoded sequence from its noisy sequenced copies (or "traces"), enabling a faster and more reliable decoding process. Previous works have often been adaptations of methods for multiple sequence alignment or read error correction, typically operating under strict assumptions such as fixed error rates. However, such methods demonstrate limited generalizability to real datasets with higher error rates and suffer from slow processing times when dealing with a large number of traces. ResultsWe propose a new probabilistic formulation of the trace reconstruction problem. Instead of optimizing alignment among traces, we model the traces as observations of a k-th order Markov chain and try to predict the sequence that is generated by the Markov chain with the highest probability. Such a formulation inspires a novel solution, i.e. Bidirectional Beam Search (BBS), whose reconstruction phase operates in linear time with respect to the length of the encoded sequences. Experiments on multiple public Nanopore datasets demonstrate that BBS achieves top-tier accuracy compared with the state-of-the-art methods while being [~]20x faster, showing its potential to enhance the efficiency of DNA data storage systems. Availability and ImplementationThe implementation of BBS is available at https://github.com/GZHoffie/bbs, and the dataset and scripts for reproducibility are available at https://github.com/GZHoffie/bbs-test.