A1 Refereed original research article in a scientific journal

Levenshtein's sequence reconstruction problem and results for larger alphabet sizes




AuthorsJunnila, Ville; Laihonen, Tero; Lehtilä, Tuomo

PublisherElsevier BV

Publication year2025

JournalTheoretical Computer Science

Journal name in sourceTheoretical Computer Science

Article number115279

Volume1045

ISSN0304-3975

eISSN1879-2294

DOIhttps://doi.org/10.1016/j.tcs.2025.115279

Web address https://doi.org/10.1016/j.tcs.2025.115279

Self-archived copy’s web addresshttps://research.utu.fi/converis/portal/detail/Publication/498927423


Abstract

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.
This reprint may differ from the original in pagination and typographic detail. Please cite the original version.




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.


Last updated on 2025-31-07 at 11:18