A1 Refereed original research article in a scientific journal
Levenshtein's sequence reconstruction problem and results for larger alphabet sizes
Authors: Junnila, Ville; Laihonen, Tero; Lehtilä, Tuomo
Publisher: Elsevier BV
Publication year: 2025
Journal: Theoretical Computer Science
Journal name in source: Theoretical Computer Science
Article number: 115279
Volume: 1045
ISSN: 0304-3975
eISSN: 1879-2294
DOI: https://doi.org/10.1016/j.tcs.2025.115279
Web address : https://doi.org/10.1016/j.tcs.2025.115279
Self-archived copy’s web address: https://research.utu.fi/converis/portal/detail/Publication/498927423
The problem of storing large amounts of information safely for a long period of time has become essential. One of the most promising new data storage mediums are the polymer-based data storage systems, like the DNA-storage system. These storage systems are highly durable and they consume very little energy to store the data. When information is retrieved from a storage, however, several different types of errors may occur in the process. It is known that the Levenshtein's sequence reconstruction framework is well-suited to overcome such errors and to retrieve the original information. Many of the previous results regarding Levenshtein's sequence reconstruction method are so far given only for the binary alphabet. However, larger alphabets are natural for the polymer-based data storage. For example, the quaternary alphabet is suitable for DNA-storage due to the four amino-acids in DNA. The results for larger alphabets often require, as we will see in this work, different and more complicated techniques compared to the binary case. Moreover, we show that an increase in the alphabet size makes some error types behave rather surprisingly.
Downloadable publication This is an electronic reprint of the original article. |
Funding information in the publication:
The authors declare the following financial interests/personal relationships which may be considered as potential competing interests: Ville Junnila reports financial support was provided by Research Council of Finland. Tero Laihonen reports financial support was provided by Research Council of Finland. Tuomo Lehtila reports financial support was provided by Research Council of Finland. If there are other authors, they declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.