Trace Reconstruction for DNA Data Storage using Language Models

Authors: Michael Girsch, Reinhard Heckel
Primary area: applications to computer vision, audio, language, and other modalities
Keywords: DNA Data Storage, Trace Reconstruction, Language Models

Abstract:
DNA is a promising storage medium due to its high information density and
longevity. However, the storage process introduces errors, thus algorithms and
codes are required for reliable storage. A common important step in the recovery
of the information from DNA is trace reconstruction. In the trace reconstruction
problem, the goal is to construct a sequence from noisy copies corrupted by deletion,
insertion, and substitution errors. In this paper, we propose to use language
models trained with next-token prediction for trace reconstruction. A simple channel
model for the DNA data storage pipeline allows for self-supervised pretraining
on large amounts of synthetic data. Additional finetuning on real data enables us
to adapt to technology-dependent error statistics. The proposed method (TReconLM) outperforms
state-of-the-art trace reconstruction algorithms for DNA data storage, often
recovering significantly more sequences.

Decision: reject
Reviewer scores: 6, 8, 3, 5

Reviews and discussion:
<thread>
creation date:
1729931680933

thread_type:
official_review

<thread_object>
creator: reviewer_guws

<content>
summary:
This paper explores trace reconstruction of DNA sequences using a GPT model. Trace reconstruction aims to recover the original DNA sequence from several corrupted versions containing insertion, deletion, and substitution errors. On synthetic data with a fixed error probability, the GPT model performs well. However, while a pretrained GPT model did not achieve effective results on real data, fine-tuning significantly improved its performance, surpassing previous methods.

strengths:
Applying GPT to DNA storage problems is a promising direction, especially since tasks like multiple sequence alignment and trace reconstruction typically demand high computational resources. This work suggests the potential of using large language models (LLMs) to streamline these processes.

weaknesses:
Unlike traditional dynamic programming-based algorithms, the proposed GPT model relies heavily on dataset-specific statistics, as seen in real-world experiments where fine-tuning was necessary. Could training GPT with various error probabilities enable broader applicability, including for real data?
Section 5.3.2 shows that fine-tuning does not perform well on larger cluster sizes. Could the authors elaborate on the reasons for this limitation?
Including data and code would enable more thorough validation and replication of the results.

questions:
Please check weaknesses
</content>
</thread_object>

</thread>
<thread>
creation date:
1730107989285

thread_type:
official_review

<thread_object>
creator: reviewer_be5j

<content>
summary:
The author(s) introduced a DL-based approach for reconstructing DNA sequences from clustered DNA reads obtained through a DNA storage pipeline.  The study utilizes a next-token prediction transformer for this purpose. The model is pre-trained on synthetic data and subsequently fine-tuned using a specific open wet-lab dataset.

strengths:
Sequence reconstruction is a challenging and valuable topic within the fields of DNA storage and bioinformatics. 

The introduction of a next-token prediction transformer-based method for sequence reconstruction marks a novel contribution to the DNA storage research community. 

The experimental outcomes are promising.

weaknesses:
The reviewer’s primary concern relates to the limited novelty within the machine learning or learning representation community, as the work appears to be an application of established deep learning techniques. The authors may spend more context to address this comment in their rebuttal if there is one. 

The writting was somehow not treated carefully. For example, since the caption of Figure 3, the proposed method is abruptly referred to as “GPT”. Firstly, the proposed method lacks a formal name, and “GPT” is not a good choice. Secondly, even GPT is not predifined in the text.

questions:
1. Line 199. The author(s) assert that they "do not consider this (the discrepancy between the pretraining and finetuning data) here" without providing a rationale. The reviewer thought this may not be acceptable. 
1. As a DL-based method, the absence of comparative experiments with the closely related transformer models, DNAformer and RobuSeqNet, within the main text requires a justifiable explanation. 
1. Why is it necessary to train separate models for (sequence length $N=2$ to $N=5$) and (sequence length $N=6$ to $N=10$)? If this is necessary, the sequence length is a hyperparameter that requires analysis. (In Line 420, the author(s) refer to "sequences of length two to five". The reviewer suspects that this might actually refer to the cardinality of clusters, with the range extending from $N=2$ to $N=5$.)
1. What is the "subcluster" for in Line 392?
1. The reviewer posits that no method is capable of effectively reconstructing sequences from clusters with a cardinality of  $N=2$, due to the insufficient information available. However, the finetuned results presented in Figures 6 and 8 for $N=2$ are promising and appear to contradict this assertion. The authors are kindly requested to provide an explanation for this. Could it be that the model learned underlying patterns or distributions specific to the wet-lab data?
</content>
</thread_object>

</thread>
<thread>
creation date:
1730278883876

thread_type:
official_review

<thread_object>
creator: reviewer_7p2t

<content>
summary:
The paper presents a method for trace reconstruction in DNA data storage using language models. The approach involves training on synthetic data, with subsequent finetuning on real datasets to improve performance on technology-specific error distributions. Experimental results show that the proposed method outperforms existing approaches on the Hamming and Levenshtein distance metrics.

strengths:
- The paper is very well written.
- The approach is innovative.
- The concept is novel to my knowledge.
- The use case (high noise, few traces) is very relevant to real-world scenarios.
- Superior performance compared to the state of the art is demonstrated.

weaknesses:
Major:
- Although the model can handle different error patterns through fine-tuning, it may struggle with entirely new or highly variable error profiles in unseen data. Specifically, it is unclear how well burst errors would be handled.

Minor:
- Figure 3: The parameter N (number of traces) should be introduced.
- Line 235: Please explain why you are considering decoder-only transformers.

questions:
- One-hot encoded sequences are padded to a fixed predetermined length. As DNA synthesis methods are being developed that produce significantly longer oligonucleotides, is this fixed-length scheme generally compatible with sequencing technologies that produce long variable-length reads (nanopore)?
- The authors assume that the original sequence consists of bases chosen uniformly at random. If fine-tuning on real data would not be feasible, how would the scheme need to be adapted to accommodate non-uniform distributions?
- It would be nice to see an evaluation of the minimum number of traces required for given I/D/S error probabilities.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730584112812

thread_type:
official_review

<thread_object>
creator: reviewer_yysm

<content>
summary:
The authors propose a new LLM-based method for the trace reconstruction problem. The problem is reconstruct an unknown string given N noisy copies of the string. These noisy copies ("reads") are a natural byproduct of DNA sequencing technologies. They contain insertion, deletion, and substitution errors. To date, there is no know algorithm to solve this problem theoretically or empirically. For real systems, people use either combinatorial or network based algorithms to output the unknown string from a collection of 2 to 10 noisy reads. The authors compare their GPT-architecture solution to these other algorithms.

For a success metric, the authors use either perfect reconstruction fraction, or measure the average edit/Hamming distances of the reconstructed strings from the ground truth strings. They compare two versions of the GPT-based model: (1) pre-trained on purely synthetic data, (2) fine-tuned on real data. The difference in (2) is that real data may follow a different error pattern, as opposed to synthetic data in (1) which has uniformly distributed errors.

Compared to other methods, the authors show improved performance. In the appendix, they also compare a few other versions, including models with fewer parameters.

strengths:
The authors provide a new method that gives good results for trace reconstruction, for both real and synthetic datasets.

The authors justify that fine-tuning is both necessary and sufficient to adapt to real data error distributions.

The authors compare against several existing trace reconstruction algorithms, giving a thorough picture of the current ways to solve the problem in practice.

The paper is concise and easy to follow. The plots are clear, with consistent coloring and informative captions.

weaknesses:
The paper showcases a successful use of LLMs to solve a real problem. But the solution is not particularly surprising, especially as written. Transformers are very powerful, and the trace reconstruction inputs are consistently structured, without a very long context, so the model is clearly going to do pretty well if trained on the exact same data.

I think the biggest open question that is not answered by this paper is: How does the GPT model solve the trace reconstruction problem? Is there a way to analyze the underlying "algorithm" to get some insights into why it does better than the baselines? Are there specific types of instances where GPT does better than ITR consistently? The results between GPT and ITR are pretty close in many of the graphs (e.g., N > 7), so it would be nice to know concretely why / how GPT is outperforming ITR.

I would love to see some more insights that may generalize to other statistical problems. For example, was there anything the authors learned about pre-training or fine-tuning? Are there any lessons about the training algorithm? Or does everything just work "out of the box" with standard implementations of small GPT models? The success of the authors' method may inspire future efforts on using LLMs to solve statistical problems, and therefore, it would be good to share as detailed insights as possible. For example, one open question is what is the minimum model size needs for the trace reconstruction setting in this paper? It seems like 300M is enough, but 3M is too small?

The paper is missing some key technical details about the training process, hyperparameter tuning, training time, number of GPUs, etc. I would like to see this in the final paper for full transparency.

questions:
1) Another baseline would be how well can GPT Mini / Gemini Flash solve this problem in a few-shot manner? Is there a prompt that can get similar performance without needing to pre-train or fine-tune? This would make it easier to implement via an API rather than needing GPUs and knowing how to train LLMs (e.g, for biologists who want to solve this problem).

2) Can you perform some interpretability of the network to see what algorithm the GPT model is implementing under the hood? And do you think the fine-tuned model is doing something fundamentally different than the pre-trained model?

3) It would be helpful to dig deeper into this topic, and push the limits of what the LLMs are capable of. The point here is not just to try random other settings (this would not be a good use of time). The point is to develop general insights that can guide future researchers that want to know if an LLM can solve their (more complicated) statistical problem. For example, there are many variations of this problem that are easy to try synthetically (or others that the authors think would help undercover ideas that could inform (2) above):
- use very long reads, e.g., O(1000) bases --> do you need a much bigger model for this?
- increasing the read count and the error rate -- what happens if p_UB goes up to 0.4 but there are O(100) reads per cluster?
- for Figure 5, how many reads are necessary to get to ~0.0 error?

4) Overall, I would be happy to increase my score if the authors could show some more general findings beyond just "LLMs can solve trace reconstruction if they have enough data and enough parameters"

Minor comments:
- the logarithmic plot y-axis is a bit hard to read, I would also add into the appendix a table of the results for the average Hamming / Levenshtein distances at each N.
- Typo in Appendix D title "PARAMTERS"

-----------------

Post rebuttal: Increasing score 5 --> 6 since the authors added new parts to the paper, including:
1. attention maps
2. more training details
3. scaling laws
4. large cluster experiments

I encourage the authors to incorporate these more detailed / technical analyses to the main body of the paper, to make it clear that their method took some care to get to work.
</content>
</thread_object>

</thread>


Metareview:
metareview:
**Summary:**
This paper proposes a novel LLM-based method for the trace reconstruction problem, which is the problem of estimating the original DNA sequence from a number $N$ of noisy copies of it, where the noise is introduced via the DNA synthesis and sequencing processes. This paper models the noising process as the insertion-deletion-substitution (IDS) channel, and proposes training of an LLM to perform next-word prediction with training instances of the form given in equation (2).

**Strengths:**
The reviewers evaluated the proposal as innovative and promising. Most of them also valued the experimental results which exhibited superior empirical performance of the proposal compared with several baselines.

**Weaknesses:**
- As some reviewers mentioned, the idea would be regarded as a straightforward application of the idea of next-word prediction in LLMs to the trace reconstruction problem.
- This paper does not discuss the issue of contaminated sequences (Qin et al., 2024) or complementary strands, the latter of which could efficiently be dealt with the Siamese architecture (Bar-Lev et al., 2024).

**Reasons:**
The proposal of applying the idea of next-word prediction to the trace reconstruction would seem rather straightforward, so that the audience of the confefence might not be able to learn much out of it, even though it would be efficient in solving this particular problem.

Minor points:
- Abstract: next-token prediction → next-word prediction
- In the description of the IDS channel, how an output sequence $y$ is generated from an input sequence $x$ is not well described. There is no mention in Figure 2 to the output $y_\ell$. I guess that in "substitution" of $x_\ell$ one chooses one of the three letters that are different from $x_\ell$ *with equal probabilities*, but it is not described explicitly.
- I think that it would be more appropriate to look at the failure rate rather than the success rate, which would allow the authors to demonstrate more clearly how their proposal outperforms ITR.
- I did not understand the experimental setting in Section 5.2.1. I guess that the parameters $p_I,p_D,p_S$ are randomly selected from the uniform distribution $\mathcal{U}(0.01+0.01k,0.1+0.01k)$ with $k\in\{0,\ldots,10\}$, and these values are then used in generating test samples.