Belief-Combining Framework for Multi-Trace Reconstruction over Channels with Insertions, Deletions, and Substitutions
Fuente:
arXiv
Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866912851517505536 |
|---|---|
| author | Nouri, Aria |
| author_facet | Nouri, Aria |
| contents | Optimal reconstruction of a source sequence from multiple noisy traces corrupted by random insertions, deletions, and substitutions typically requires joint processing of all traces, leading to computational complexity that grows exponentially with the number of traces. In this work, we propose an iterative belief-combining procedure that computes symbol-wise a posteriori probabilities by propagating trace-wise inferences via message passing. We prove that, upon convergence, our method achieves the same reconstruction performance as joint maximum a posteriori estimation, while reducing the complexity to quadratic in the number of traces. This performance equivalence is validated using a real-world dataset of clustered short-strand DNA reads. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_18920 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Belief-Combining Framework for Multi-Trace Reconstruction over Channels with Insertions, Deletions, and Substitutions Nouri, Aria Information Theory Optimal reconstruction of a source sequence from multiple noisy traces corrupted by random insertions, deletions, and substitutions typically requires joint processing of all traces, leading to computational complexity that grows exponentially with the number of traces. In this work, we propose an iterative belief-combining procedure that computes symbol-wise a posteriori probabilities by propagating trace-wise inferences via message passing. We prove that, upon convergence, our method achieves the same reconstruction performance as joint maximum a posteriori estimation, while reducing the complexity to quadratic in the number of traces. This performance equivalence is validated using a real-world dataset of clustered short-strand DNA reads. |
| title | Belief-Combining Framework for Multi-Trace Reconstruction over Channels with Insertions, Deletions, and Substitutions |
| topic | Information Theory |
| url | https://arxiv.org/abs/2601.18920 |