Multi-strand Reconstruction from Substrings

The problem of reconstruction of strings based upon their substrings spectrum has received significant attention recently due to its applicability to DNA applications in storage and sequencing. In contrast to previous works, we consider in this paper the setup of this problem where multiple strings are reconstructed together. Given a multiset S of strings, all their substrings of some fixed length \ell, defined as the \ell-profile of S, are received and the goal is to reconstruct all strings in the multiset S. A multi-strand \ell-reconstruction code is a set of multisets such that every multiset S can be reconstructed from its \ell-profile. Given the number of strings k and their length n, we first find a lower bound on the value of \ell to have multi-strand \ell-reconstruction codes with asymptotic rate 1. We then present two constructions of such codes and show that their rates approach 1 for values of \ell that asymptotically behave like the lower bound to have this asymptotic rate.