Tree trace reconstruction using subtraces

DOI10.1017/JPR.2022.81MaRDI QIDQ6102057zbMATH OpenOpenAlexFDO

Authors Tatiana Brailovskaya, Miklós Z. Rácz

Publication date 8 May 2023

Published in Journal of Applied Probability (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2102.01541

zbMATH Keywords

statistical error correctiontrace reconstructiontree graphs

Mathematics Subject Classification ID

Combinatorial probability (60C05) Information storage and retrieval of data (68P20) Algorithms on strings (68W32) Miscellaneous topics in information and communication theory (94D99)

Abstract: Tree trace reconstruction aims to learn the binary node labels of a tree, given independent samples of the tree passed through an appropriately defined deletion channel. In recent work, Davies, R'acz, and Rashtchian used combinatorial methods to show that $exp(mathcalO(klo{g}_{k}n))$ samples suffice to reconstruct a complete $k$-ary tree with $n$ nodes with high probability. We provide an alternative proof of this result, which allows us to generalize it to a broader class of tree topologies and deletion models. In our proofs, we introduce the notion of a subtrace, which enables us to connect with and generalize recent mean-based complex analytic algorithms for string trace reconstruction.

Recommendations

• Trace reconstruction revisited
• Trace reconstruction with \(\exp(O(n^{1/3}))\) samples
• Optimal mean-based algorithms for trace reconstruction
• Optimal mean-based algorithms for trace reconstruction
• Lower bounds for trace reconstruction

Cites work

• Coded Trace Reconstruction
• Efficient reconstruction of sequences
• scientific article; zbMATH DE number 5764889 (Why is no real title available?)
• scientific article; zbMATH DE number 7650111 (Why is no real title available?)
• Lower bounds for trace reconstruction
• New lower bounds for trace reconstruction
• Optimal mean-based algorithms for trace reconstruction
• Optimal mean-based algorithms for trace reconstruction
• Reconstructing strings from random traces
• Reconstructing trees from traces
• Subpolynomial trace reconstruction for random strings and arbitrary deletion probability
• Trace Reconstruction Problems in Computational Biology
• Trace reconstruction with \(\exp(O(n^{1/3}))\) samples
• Trace reconstruction with varying deletion probabilities
• Trace reconstruction: generalized and parameterized

Cited in

(4)

• Reconstructing trees from traces
• scientific article; zbMATH DE number 4025477 (Why is no real title available?)
• Trace reconstruction from local statistical queries
• Global alignment of molecular sequences via ancestral state reconstruction

This page was built for publication: Tree trace reconstruction using subtraces

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