Portal de Periódicos da CAPES

Reconstructing trees from traces

2021; Institute of Mathematical Statistics; Volume: 31; Issue: 6 Linguagem: Inglês

10.1214/21-aap1662

2168-8737

Sami Davies, Miklós Z. Rácz, Cyrus Rashtchian,

Genomics and Phylogenetic Studies

We study the problem of learning a node-labeled tree given independent traces from an appropriately defined deletion channel. This problem, tree trace reconstruction, generalizes string trace reconstruction, which corresponds to the tree being a path. For many classes of trees, including complete trees and spiders, we provide algorithms that reconstruct the labels using only a polynomial number of traces. This exhibits a stark contrast to known results on string trace reconstruction, which require exponentially many traces, and where a central open problem is to determine whether a polynomial number of traces suffice. Our techniques combine novel combinatorial and complex analytic methods.