Fundamental Limits of Multiple Sequence Reconstruction from Substrings

Kel Levick, Ilan Shomorony

Research output: Chapter in Book/Report/Conference proceedingConference contribution


The problem of reconstructing a sequence from the set of its length-k substrings has received considerable attention due to its various applications in genomics. We study an uncoded version of this problem where multiple random sources are to be simultaneously reconstructed from the union of their k-mer sets. We consider an asymptotic regime where m = na i.i.d. source sequences of length n are to be reconstructed from the set of their substrings of length k = ß logn, and seek to characterize the (a,ß) pairs for which reconstruction is information-theoretically feasible. We show that, as n ?8a + 1, the source sequences can be reconstructed if ß > max(2a + 1, a + 2) and cannot be reconstructed if ß < max (2a + 1,a + 3/2), characterizing the feasibility region almost completely. Interestingly, our result shows that there are feasible (a,ß) pairs where repeats across the source strings abound, and non-trivial reconstruction algorithms are needed to achieve the fundamental limit.

Original languageEnglish (US)
Title of host publication2023 IEEE International Symposium on Information Theory, ISIT 2023
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781665475549
StatePublished - 2023
Event2023 IEEE International Symposium on Information Theory, ISIT 2023 - Taipei, Taiwan, Province of China
Duration: Jun 25 2023Jun 30 2023

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095


Conference2023 IEEE International Symposium on Information Theory, ISIT 2023
Country/TerritoryTaiwan, Province of China

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Information Systems
  • Modeling and Simulation
  • Applied Mathematics


Dive into the research topics of 'Fundamental Limits of Multiple Sequence Reconstruction from Substrings'. Together they form a unique fingerprint.

Cite this