TY - GEN

T1 - Fundamental Limits of Multiple Sequence Reconstruction from Substrings

AU - Levick, Kel

AU - Shomorony, Ilan

N1 - Publisher Copyright:
© 2023 IEEE.

PY - 2023

Y1 - 2023

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85171454831&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85171454831&partnerID=8YFLogxK

U2 - 10.1109/ISIT54713.2023.10206707

DO - 10.1109/ISIT54713.2023.10206707

M3 - Conference contribution

AN - SCOPUS:85171454831

T3 - IEEE International Symposium on Information Theory - Proceedings

SP - 791

EP - 796

BT - 2023 IEEE International Symposium on Information Theory, ISIT 2023

PB - Institute of Electrical and Electronics Engineers Inc.

T2 - 2023 IEEE International Symposium on Information Theory, ISIT 2023

Y2 - 25 June 2023 through 30 June 2023

ER -