Akademska digitalna zbirka SLovenije - logo
E-viri
Celotno besedilo
Recenzirano Odprti dostop
  • Generalized Unique Reconstr...
    Yehezkeally, Yonatan; Bar-Lev, Daniella; Marcovich, Sagi; Yaakobi, Eitan

    IEEE transactions on information theory, 2023-Sept., 2023-9-00, Letnik: 69, Številka: 9
    Journal Article

    This paper introduces a new family of reconstruction codes which is motivated by applications in DNA data storage and sequencing. In such applications, DNA strands are sequenced by reading some subset of their substrings. While previous works considered two extreme cases in which all substrings of pre-defined lengths are read or substrings are read with no overlap for the single string case, this work studies two extensions of this paradigm. The first extension considers the setup in which consecutive substrings are read with some given minimum overlap. First, an upper bound is provided on the attainable rates of codes that guarantee unique reconstruction. Then, efficient constructions of codes that asymptotically meet that upper bound are presented. In the second extension, we study the setup where multiple strings are reconstructed together. Given the number of strings and their length, we first derive a lower bound on the read substrings' length <inline-formula> <tex-math notation="LaTeX">\ell </tex-math></inline-formula> that is necessary for the existence of multi-strand reconstruction codes with non-vanishing rates. We then present two constructions of such codes and show that their rates approach 1 for values of <inline-formula> <tex-math notation="LaTeX">\ell </tex-math></inline-formula> that asymptotically behave like the lower bound.