Trace reconstruction with constant deletion probability and related results

ABSTRACT

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 some universal constant γ and uniformly chosen strings of length n, for any δ < γ 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 Õ (√n) for any δ < 1 even for worst case strings, and we derive lower bound results for simpler classes of algorithms based on summary statistics from the traces.

REFERENCES

• 1: Milton Abramowitz, Handbook of Mathematical Functions, With Formulas, Graphs, and Mathematical Tables,, Dover Publications, Incorporated, 1974
• 2: H. Alzer. Sharp inequalities for the digamma and polygamma functions Forum Mathematicum, vol. 16, no. 2, pp. 181--221. 2004.
• 3: Tuǧkan Batu , Sampath Kannan , Sanjeev Khanna , Andrew McGregor, Reconstructing strings from random traces, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 4: R. L. Dobrushin. Shannon's Theorems for Channels with Synchronization Errors. Problems of Information Transmission, 3(4):11--26, 1967. Translated from Problemy Peredachi Informatsii, vol. 3, no. 4, pp 18--36, 1967.
• 5: E. Drinea and M. Mitzenmacher. Improved lower bounds for the capacity of i.i.d. deletion and duplication channels. IEEE Trans. on Information Theory, 53:8, pp. 2693--2714, 2007.
• 6: S. Kannan and A. McGregor. More on reconstructing strings from random traces: insertions and deletions. In Proc. of the Int'l. Symp. on Information Theory, pp. 297--301, 2005.
• 7: V. I. Levenshtein. Efficient reconstruction of sequences. IEEE Transactions on Information Theory, vol. 47, no. 1, pp. 2--22, 2001.
• 8: Vladimir I. Levenshtein, Efficient reconstruction of sequences from their subsequences or supersequences, Journal of Combinatorial Theory Series A, v.93 n.2, p.310-332, Feb. 2001 [doi>10.1006/jcta.2000.3081]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Probabilistic computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations in finite fields

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.3 Applications

General Terms:
Algorithms, Design, Theory