Research AreasPublications

Reconstruction Algorithms

Dr. Daniella Bar-Lev, Dr. Sagi Markovich, Prof. Eitan Yaakobi, Yonatan Yehezkeally, "Adversarial Torn - paper Codes", IEEE International Symposium on Information Theory (ISIT), 2022, pp. 2934 – 2939

abstractBibTeX

BibTeX

@INPROCEEDINGS{9834766,
author={Bar-Lev, Daniella and Marcovich, Sagi and Yaakobi, Eitan and Yehezkeally, Yonatan},
booktitle={2022 IEEE International Symposium on Information Theory (ISIT)},
title={Adversarial Torn
-
paper Codes},
year={2022},
volume={},
number={},
pages={2934-2939},
doi={10.1109/ISIT50566.2022.9834766}}

copy to clipboard

This paper studies the adversarial torn-paper channel. This problem is motivated by applications in DNA data storage where the DNA strands that carry the information may break into smaller pieces that are received out of order. Our model extends the previously researched probabilistic setting to the worst-case. We deve lop code constructions for any parameters of the channel for which non-vanishing asymptotic rate is possible and show that our constructions achieve optimal asymptotic rate while allowing for efficient encoding and decoding. Finally, we extend our results to related settings included multi-strand storage, presence of substitution errors, or incomplete coverage.

Dr. Daniella Bar-Lev, Dr. Sagi Markovich, Prof. Eitan Yaakobi, Yonatan Yehezkeally, "Adversarial Torn-paper Codes", IEEE International Symposium on Information Theory, Aalto, Finland, (June-July 2022), 2947 – 2952.

Kui Cai, Han Mao Kiah, Tuan Thanh Nguyen, Prof. Eitan Yaakobi, "Coding for Sequence Reconstruction for Single Edits", IEEE Transactions on Information Theory, 68 (2022), 66–79.

Han Mao Kiah, Tuan Thanh Nguyen, Prof. Eitan Yaakobi, "Coding for Sequence Reconstruction for Single Edits", IEEE International Symposium on Information Theory, Los Angeles, California, (June 2020), 676–681.

Shubhransh Singhvi, Avital Boruchovsky, Han-Mao Kiah, Prof. Eitan Yaakobi, "Data-Driven Bee Identification for DNA Strands", International Symposium on Information Theory, Taipei, Taiwan, (June 2023), 797–802.

Yonatan Yehezkeally, Dr. Daniella Bar-Lev, Dr. Sagi Markovich, Prof. Eitan Yaakobi, "Generalized Unique Reconstruction from Substrings", IEEE Transactions on Information Theory, 69 (2023), 5648–5659.

Dvir Ben-Shabat, Adar Hadad, Avital Boruchovsky, Prof. Eitan Yaakobi, "GradHC: highly reliable gradual hash-based clustering for DNA storage systems", Bioinformatics, Volume 40, Issue 5, May 2024.

Yonatan Yehezkeally, Dr. Sagi Markovich, Prof. Eitan Yaakobi, "Multi-strand Reconstruction from Substrings", IEEE Information Theory Workshop, Kanazawa, Japan, (October 2021).

Dr. Maria Abu-Sini, Prof. Eitan Yaakobi, "On Levenshtein’s Reconstruction Problem Under Insertions, Deletions, and Substitutions", IEEE Transactions on Information Theory, 67 (2021), 7132-7158.

Dr. Maria Abu-Sini, Prof. Eitan Yaakobi, "On List Decoding of Insertions and Deletions under the Reconstruction Model", IEEE International Symposium on Information Theory, Melbourne, Australia, (July 2021), 1706 – 1711.

Dr. Maria Abu-Sini, Prof. Eitan Yaakobi, "On the Intersection of Multiple Insertion (or Deletion) Balls and its Application to List Decoding under the Reconstruction Model", IEEE Transactions on Information Theory, 70 (2024), 3262–3297.

Johan Chrisnata, Han Mao Kiah, Prof. Eitan Yaakobi, "Optimal Reconstruction Codes for Deletion Channels", IEEE International Symposium on Information Theory and Its Applications, Kapolei, Hawai’i, (October 2020), 279 – 283., Best Student Paper Award.

Dr. Omer Sabary, Alexander Yucovich, Guy Shapira, Prof. Eitan Yaakobi, "Reconstruction Algorithms for DNA Storage Systems", Scientific Reports, 14-1951 (2024).

Dr. Omer Sabary, Alexander Yucovich, Guy Shapira, Prof. Eitan Yaakobi, "Reconstruction Algorithms for DNA-Storage Systems", 26th International Conference on DNA Computing and Molecular Programming, (September 2020).

Yonatan Yehezkeally, Dr. Daniella Bar-Lev, Dr. Sagi Markovich, Prof. Eitan Yaakobi, "Reconstruction from Substrings with Partial Overlap", International Symposium on Information Theory and Its Applications, Tsukuba, Japan (October 2022).

Dr. Maria Abu-Sini, Prof. Eitan Yaakobi, "Reconstruction of Sequences in DNA Storage", IEEE International Symposium on Information Theory, Paris, France (July 2019), 290–294.

Michal Horovitz, Prof. Eitan Yaakobi, "Reconstruction of Sequences over Non-Identical Channels", IEEE Transactions on Information Theory, 65 (2019), 1267–1286.

Dr. Sagi Markovich, Prof. Eitan Yaakobi, "Reconstruction of Strings from their Substrings Spectrum", IEEE Transactions on Information Theory, 67 (2021), 4369–4384.

Dr. Sagi Markovich, Prof. Eitan Yaakobi, "Reconstruction of Strings from their Substrings Spectrum", IEEE International Symposium on Information Theory, Los Angeles, California, (June 2020), 658–663.

Dr. Daniella Bar-Lev, Itai Orr, Dr. Omer Sabary, Tuvi Etzion, Prof. Eitan Yaakobi, "Scalable and Robust DNA-Based Storage via Coding Theory and Deep Learning", Nature Machine Intelligence, 7 (2025) 639–649.

Roy Shafir, Dr. Omer Sabary, Leon Anavy, Prof. Eitan Yaakobi, Zohar Yakhini, "Sequence design and reconstruction under the repeat channel in enzymatic DNA synthesis‏", IEEE Transactions on Communications

abstractBibTeX

BibTeX

@ARTICLE{10313138,
author={Shafir, Roy and Sabary, Omer and Anavy, Leon and Yaakobi, Eitan and Yakhini, Zohar},
journal={IEEE Transactions on Communications},
title={Sequence Design and Reconstruction Under the Repeat Channel in Enzymatic DNA Synthesis},
year={2024},
volume={72},
number={2},
pages={675-691},
keywords={DNA;Noise measurement;Europe;Encoding;Reconstruction algorithms;Random variables;Memory;DNA-based informatics;DNA-based data storage;deletion channel;insertion channel;sequence reconstruction;enzymatic DNA synthesis;nucleic acid sequencing;alternating-length limited codes},
doi={10.1109/TCOMM.2023.3330848}}

copy to clipboard

Using synthetic DNA for data storage and for physical information encoding in labeling, tracing, and authentication applications is becoming more feasible as synthesis and reading technologies are improving. DNA in data storage applications has several advantages such as very high physical density and robustness. Some of the new synthesis technologies lead to repetition noise, consisting of sticky insertions and deletions in the resulting messages. In this paper, we address reconstruction algorithms for multiple trace communication channels with repetition (sticky insertion and deletion) noise. We prove correctness and analyze failure rates, both analytically and on simulated data. We identify a failure mechanism related to alternating stretches in the design sequence that leads to a potential bias in the data derived from reads (traces) and used for reconstruction. To minimize this effect we introduce alternating …

Jessica Bariffi, Antonia Wachter-Zeh, Prof. Eitan Yaakobi, "Sequence Reconstruction Over Coloring Channels for Protein Identification", IEEE International Symposium on Information Theory, Ann Arbor, Michigan, USA (June 2025).

Roy Shafir, Dr. Omer Sabary, Leon Anavy, Prof. Eitan Yaakobi, Zohar Yakhini, "Sequence Reconstruction Under Stutter Noise in Enzymatic DNA Synthesis", IEEE Information Theory Workshop, Kanazawa, Japan, (October 2021).

back