Trace reconstruction with constant deletion probability and related results

Thomas Holenstein, Michael Mitzenmacher, Rina Panigrahy, and Udi Wieder

January 2008

We provide several new results for the trace reconstruction problem. In this setting, a binary string yields a collection of traces, where each trace is independently

obtained by independently deleting each bit with a fixed probability. Each trace therefore consists of a random subsequence of the original sequence. Given the

traces, we wish to reconstruct the original string with high probability. The questions are how many traces are necessary for reconstruction, and how efficiently can the

reconstruction be performed. Our primary result is that for any deletion probability smaller than some universal constant and uniformly chosen strings of length n, a reconstruction is possible with poly(n) traces in poly(n) time with high probability. We also obtain algorithms that require a number of traces exponential in ~O(pn) for any p < 1 even for worst case strings, and we derive lower bound results for simpler classes of algorithms based on summary statistics from the traces.

Publication type | Inproceedings |

Published in | ACM-SIAM Symposium on Discrete Algorithms (SODA) |

Address | San Francisco, CA |

> Publications > Trace reconstruction with constant deletion probability and related results