Reconstructing strings from random traces

MaRDI QIDQ5501353zbMATH OpenFDO

Authors Tuğkan Batu, Sampath Kannan, Sanjeev Khanna, Andrew McGregor

Publication date 3 August 2015

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Algorithms on strings (68W32)

Recommendations

• Subpolynomial trace reconstruction for random strings and arbitrary deletion probability
• Trace reconstruction revisited
• Trace reconstruction with varying deletion probabilities
• Trace reconstruction with \(\exp(O(n^{1/3}))\) samples
• Optimal mean-based algorithms for trace reconstruction

Cited in

(22)

• Optimal mean-based algorithms for trace reconstruction
• Subpolynomial trace reconstruction for random strings and arbitrary deletion probability
• New lower bounds for trace reconstruction
• Reconstructing trees from traces
• The trace reconstruction problem for spider graphs
• On the word fragment length for unambiguous reconstruction of a periodic word from a complete multiset of fragments of fixed length
• Lower bounds for trace reconstruction
• Efficient Reconstruction of RC-Equivalent Strings
• Trace reconstruction: generalized and parameterized
• String reconstruction from substring compositions
• Information-Theoretic Foundations of DNA Data Storage
• Tree trace reconstruction using subtraces
• Reconstruction of hypermatrices from subhypermatrices
• Improvements on permutation reconstruction from minors
• Trace reconstruction from local statistical queries
• Polynomial-time trace reconstruction in the smoothed complexity model
• Levenshtein's sequence reconstruction problem and results for larger alphabet sizes
• Global alignment of molecular sequences via ancestral state reconstruction
• Circular trace reconstruction
• Polynomial-time trace reconstruction in the low deletion rate regime
• On the decoding error weight of one or two deletion channels
• Near-optimal trace reconstruction for mildly separated strings

This page was built for publication: Reconstructing strings from random traces

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5501353)