Efficient trace reconstruction in DNA storage systems using bidirectional beam search

This is the authors' abstract. We don't add key points for this paper.

-th order Markov chain. Instead of doing alignment, we identify the sequence most likely generated by the Markov chain as the consensus. This inspires bidirectional beam search (BBS), an algorithm that reconstructs the consensus in linear time with respect to its length. Experiments on multiple public Nanopore sequencing datasets demonstrate that BBS achieves top-tier accuracy while being approximately 20× faster than existing methods, showing its potential to enhance the efficiency and reliability of DNA data storage systems.