The sequence reconstruction problem involves a model where a sequence is transmitted over several identical channels. This model investigates the minimum number of channels required for the unique reconstruction of the transmitted sequence. Levenshtein established that this number exceeds the maximum size of the intersection between the error balls of any two distinct transmitted sequences by one. In this paper, we consider channels subject to multiple bursts of insertions and multiple bursts of deletions, respectively, where each burst has an exact length of valueb. Our key findings are as follows: • Insertion Case: We investigateb-burst-insertion balls of radiustcentered atq-ary sequences of lengthn. We establish that the size of an error ball is independent of its chosen center. Furthermore, we demonstrate that the intersection between error balls centered at two sequences differing only at their first position yields the largest intersection size, denoted byNq,b+(n,t). We also propose a reconstruction algorithm with linear runtime complexity, which processesNq,b+(n,t)+1 distinct output sequences from the channel to recover the correct transmitted sequence. • Deletion Case: We examineb-burst-deletion balls of radiustcentered atq-ary sequences of lengthn. In contrast to burst-insertion balls, we prove that the size of a burst-deletion ball is dependent on its chosen center. Particularly, we show that theb-burst-deletion ball centered at theb-cyclic sequence 0b⸰ 1b⸰ · · · ⸰ (q− 1)b⸰ 0b· · · achieves the largest size. For binary alphabets, we then demonstrate that the intersection ofb-burst-deletion balls centered at 0b⸰ 1b⸰ 0b⸰ 1b· · · and 0b−1⸰ 1 ⸰ 1b⸰ 0b⸰ 1b· · · yields the largest size, denoted byN2,b−(n,t). Moreover, we propose a reconstruction algorithm with linear runtime complexity, which processesN≥N2,b−(n,t)+1 distinct output sequences from the channel to reconstruct the correct transmitted sequence1.

In this paper, we investigate binary reconstruction codes capable of correcting one deletion and one substitution. We define the \emph{single-deletion single-substitution ball} function $ \mathcal{B} $ as a mapping from a sequence to the set of sequences that can be derived from it by performing one deletion and one substitution. A binary \emph{$(n,N;\mathcal{B})$-reconstruction code} is defined as a collection of binary sequences of length $ n $ such that the intersection size between the single-deletion single-substitution balls of any two distinct codewords is strictly less than $ N $. This property ensures that each codeword can be uniquely reconstructed from $ N $ distinct elements in its single-deletion single-substitution ball. Our main contribution is to demonstrate that when $ N $ is set to $ 4n - 8 $, $ 3n - 4 $, $2n+9$, $ n+21 $, $31$, and $7$, the redundancy of binary $(n,N;\mathcal{B})$-reconstruction codes can be $0$, $1$, $2$, $ \log\log n + 3 $, $\log n + 1 $, and $ 3\log n + 4 $, respectively, where the logarithm is on base two.

In this paper, we propose a partitioning technique that decomposes a pair of sequences with overlappingt-deletions-substitution balls into sub-pairs, where the≤t-burst-deletion balls of each sub-pair intersect. This decomposition facilitates the development oft-deletions-substitution correcting codes that leverage approaches from≤t-burst-deletion correction. Building upon established approaches in the≤t-burst-deletion correction domain, we constructt-deletions-substitution correcting codes fort∈ {1, 2} over binary alphabets and fort= 1 in non-binary alphabets, with some constructions matching existing results and others outperforming current methods. Our framework offers new insights into the underlying principles of prior works, elucidates the limitations of current approaches, and provides a unified perspective on error correction strategies.

This paper addresses fundamental challenges in two-dimensional error correction by constructing optimal codes forcriss-cross deletions. We consider ann×narrayXover aq-ary alphabet Σq:= {0, 1, . . . ,q−1} that is subject to a (tr, tc)-criss-cross deletion, which involves the simultaneous removal oftrrows andtccolumns. A codeC⊆ Σn×nqis defined as a (tr, tc)-criss-cross deletion correcting codeif it can successfully correct these deletions. Our primary technical contributions are as follows: •Theoretical Bounds: We derive a sphere-packing type lower bound and a Gilbert-Varshamov type upper bound on the redundancy of optimal codes. Our results indicate that the optimal redundancy for a (tr, tc)-criss-cross deletion correcting code lies between (tr, tc)nlogq+(tr, tc) logn+Oq,tr,tc(1) and (tr, tc)nlogq+2(tr, tc) logn+Oq,tr,tc(1), where the logarithm is on base two, and Oq,tr,tc (1) is a constant that depends solely onq, tr, andtc. •Optimal Constructions: For the case of (1, 1)-criss-cross deletions, we propose two families of constructions that achieve 2nlogq+ 2 logn+Oq(1) bits of redundancy. This redundancy is optimal up to an additive constant termOq(1), which depends solely onq. One family is designed for non-binary alphabets, while the other addresses arbitrary alphabets. For the case of (tr, tc)-criss-cross deletions, we provide a strategy to derive optimal codes when both unidirectional deletions occur consecutively. •Efficient Decoders: We propose decoding algorithms with a time complexity ofO(n2) for our codes, which are optimal for two-dimensional scenarios.

LetB(·) be an error ball function. A set ofq-ary sequences of lengthnis referred to as an (n, q, N; B)-reconstruction codeif each sequencexwithin this set can be uniquely reconstructed from anyNdistinct elements within its error ballB(x). The main objective in this area is to determine or establish bounds for the minimum redundancy of (n, q, N; B)-reconstruction codes, denoted by ρ(n, q, N; B). In this paper, we investigate reconstruction codes where the error ball corresponds to either thet-deletion ball Dt(·) or thet-insertion ball It(·). Our primary technical contributions include: • Establishing a fundamental connection between reconstruction codes for deletions and insertions. Specifically, for any positive integersn, t, q, N, any (n, q, N; It)-reconstruction code is also an (n, q, N; Dt)-reconstruction code. This leads to the inequality ρ(n, q, N; Dt) ≤ ρ(n, q, N; It). • Identifying a significant distinction between reconstruction codes for deletions and insertions whenN=O(nt−1) andt≥ 2. For deletions, we prove that there exists some constantKsuch that ρ(n, q,2(q−1)t−1/qt−1(t−1)!nt−1+Knt−2;Dt) =O(1), which disproves a conjecture posed in [1]. In contrast, for insertions, we show that there exists some constantK′ such that ρ(n, q,(q−1)t−1(t−1)!nt−1+K′nt−2;It) = log logn+O(1), which extends a key result from [2]. • Constructing (n, q, N; B)-reconstruction codes, whereB∈ {D2,I2}, forN∈ {2, 3, 4, 5} and establishing respective upper bounds of 3 logn+O(log logn), 3 logn+O(1), 2 logn+ O(log logn) and logn+ O(log logn) on the minimum redundancy ρ(n, q, N; B). This generalizes results previously established in [3].

Consider a length-n sequencexover aq-ary alphabet. The fixed-length Levenshtein ballLt(x) of radius t contains all length-nq-ary sequences that can be derived fromxby performingtdeletions followed bytinsertions. Recent studies have successfully characterized fixed-length Levenshtein balls in the context of radiust= 1. These works have derived explicit formulas for various quantities, including the exact size of the balls, extremal bounds (minimum and maximum sizes), as well as expected sizes and their concentration properties. However, the general case involving an arbitrary number oftdeletions andtinsertions (t> 1) remains largely uninvestigated. This work systematically examines fixed-length Levenshtein balls with multiple deletions and insertions, focusing specifically onfixed-length burst Levenshtein balls, where deletions occur consecutively, as do insertions. We provide solutions for explicit cardinality formulas, extremal bounds (minimum and maximum sizes), expected size, and concentration properties surrounding the expected value.

Codes correcting bursts of deletions and localized deletions have garnered significant research interest in recent years. One of the primary objectives is to construct codes with minimal redundancy. Currently, the best known constructions of q-ary codes correcting a burst of at most t deletions ((≤t)-burstdeletion correcting codes) achieve redundancy log n+8 log log n+ o(log log n) (for anyqandt) or log n +tlog log n + O(1) (for even q). For codes correcting singlet-localized-deletion, state-ofthe- art constructions attain redundancy log n+O 􀀀 t(log log n)2) (for any q and t) or log n + 2t log log n + O(1) (for even q). Here, n denotes the code-length, and q and t are fixed. These codes employ a position-estimation component to approximate error positions, augmented by additional constraints that enable error-correction given the information about error positions. In this work, we first generalize thet-localized-deletion model to a (t, T)-localized-deletion model and then explore code constructions for correcting such errors. We select codewords from the set of sequences whose differential sequences are strong-(ℓ, ϵ)- locally-balanced. By imposing a VT-type constraint and an L1- weight constraint on the differential sequences of codewords, we construct novel position-estimation codes. When q ≥ 2 and tqis even andtq-ary (≤t)- burst-deletion correcting code and a (t, T)-localized-deletion correcting code with redundancy log n+(t−1) log log n+O(1). In addition to improving previous redundancy, our technique is novel and leads to simpler position-estimation codes compared to earlier works. Finally, we present an efficient encoder that maps an arbitrary input sequence into a sequence whose differential sequence is strong-(ℓ, ϵ)-locally-balanced. To our knowledge, no prior algorithm for this specific task has been reported.

In this paper, we investigate codes designed to correct two bursts of deletions, where each burst has a length of exactlyb, whereb> 1. The previous best construction, achieved through the syndrome compression technique, had a redundancy of at most 7 logn+O(logn/ log logn) bits. In contrast, our work introduces a novel approach for constructing q-ary codes that attain a redundancy of at most 5 logn+O(log logn) bits for allb> 1 andq≥ 2. Additionally, for the case whereb= 1, we present a new construction of q-ary two-deletion correcting codes with a redundancy of 5 logn+ O(log logn) bits, for allq> 2.

Bursts of errors are a class of errors that can be found in a variety of applications. A burst of t edits refers to a burst of t deletions, or a burst of t insertions, or a burst of t substitutions. This paper focuses on studying codes that can correct a burst of t edits. Our primary approach involves the use of the tool called weighted-summation VT sketch. The$(t,k)$-weighted-summation VT sketch of a length-n sequence is defined as the weighted summation of the VT sketch of each row of its$t\times \lceil n/t \rceil $array representation, with weights in the i-th row set as$k^{i-1}$for$i=1,2,\ldots,t$. By employing the weighted-summation VT sketch alongside multiple weight sketches, we introduce a construction for q-ary t-burst-substitution correcting codes with a redundancy of$\log n+O(1)$, where the logarithm base is 2. Subsequently, we improve the redundancy to address specific types of burst-substitution errors, such as inversion errors, adjacent-block-transposition errors, and absorption errors. Moreover, by utilizing the method developed in the construction of burst-substitution correcting codes and imposing additional run-length-limited constraints, locally-bounded constraints, and strong-locally-balanced constraints, respectively, we introduce three constructions of t-burst-deletion correcting codes, each requiring a redundancy of$\log n+O(\log \log n)$. Any t-burst-deletion-correcting code is also a t-burst-insertion correcting code, allowing us to intersect the t-burst-substitution-correcting codes and t-burst-deletion-correcting codes designed above to derive three constructions of q-ary t-burst-edit-correcting codes. The first two constructions have a redundancy of$\log n+(t\log q-1)\log \log n+O(1)$, while the third construction has a redundancy of$\log n+\log \log n+O(1)$. Most of the proposed codes demonstrate superior performance compared to previous results, with the exception of burst-deletion correcting codes. Furthermore, in cases of single-edit errors (t-burst-edit error with$t=1$), the redundancy of the first two constructions of quaternary single-edit correcting codes outperforms the results of Gabrys et al. (IEEE Trans. Inf. Theory 2023). We also provide efficient encoding and decoding algorithms for our codes to enhance their practical usability.

Nanopore sequencing is a promising technology for DNA sequencing. In this paper, we investigate a specific model of the nanopore sequencer, which takes aq-ary sequence of lengthnas input and outputs a vector of lengthn+ℓ−1 referred to as an ℓ-read vector where thei-th entry is a multi-set composed of the ℓ elements located between the (i−ℓ+1)-th andi-th positions of the input sequence. Considering the presence of substitution errors in the output vector, we study ℓ-read codes under the Hamming metric. An ℓ-read (n,d)q-code is a set ofq-ary sequences of lengthnin which the Hamming distance between ℓ-read vectors of any two distinct sequences is at leastd. Here, the Hamming distance between two ℓ-read vectors is defined as the number of positions at which the corresponding multi-sets differ. We first improve the result of Banerjeeet al., who studied ℓ-read (n,d)q-codes with the constraint ℓ ≥ 3 andd= 3. Then, we investigate the bounds and constructions of 2-read codes with a minimum distance of 3, 4, and 5, respectively. Our results indicate that whend∈ {3, 4}, the optimal redundancy of 2-read (n,d)q-codes iso(logqn), while ford= 5 it is logqn+o(logqn). Additionally, we establish an equivalence between 2-read (n, 3)q-codes and classicalq-ary single-insertion reconstruction codes using two distinct noisy reads. We improve the lower bound on the redundancy of classicalq-ary single-insertion reconstruction codes as well as the upper bound on the redundancy of classicalq-ary single-deletion reconstruction codes when using two distinct noisy reads.

Recently, codes for correcting a burst of errors have attracted significant attention. One of the most important reasons is that bursts of errors occur in certain emerging techniques, such as DNA storage. In this paper, we investigate a type of error, called a$(t,s)$-burst, which deletes t consecutive symbols and inserts s arbitrary symbols at the same coordinate. Note that a$(t,s)$-burst error can be seen as a generalization of a burst of insertions ($t=0$), a burst of deletions ($s=0$), and a burst of substitutions ($t=s$). Our main contribution is to give explicit constructions of q-ary$(t,s)$-burst correcting codes with$\log n + O(1)$bits of redundancy for any given constant non-negative integers t, s, and$q \geq 2$. These codes have optimal redundancy up to an additive constant. Furthermore, we apply our$(t,s)$-burst correcting codes to combat other various types of errors and improve the corresponding results. In particular, one of our byproducts is a permutation code capable of correcting a burst of t stable deletions with$\log n + O(1)$bits of redundancy, which is optimal up to an additive constant.

An edit refers to a single insertion, deletion, or substitution. This paper aims to construct binary codes that can correct two edits. To do this, a necessary and sufficient condition for a code to be two-edit correctable is provided, showing that a code is a two-edit correcting code if and only if it can correct two deletions, up to two substitutions, and one deletion and up to one substitution, separately. This criterion allows for the construction of two-edit correcting codes leveraging these three types of error correcting codes. In the field of constructing codes for correcting two deletions, we present a construction with$4\log n+O(\log \log n)$redundant bits that can be viewed as a subcode proposed by Guruswami and Håstad, and provide an alternative proof. Moreover, our two-deletion correcting codes can also correct up to two substitutions after making a slight modification. In the field of constructing codes for correcting one deletion and up to one substitution, we present a construction with$4 \log n+O(\log \log n)$redundant bits, which outperforms the best previously known results$6 \log n+O(1)$. Leveraging these codes, we obtain a construction of two-edit correcting codes with$6 \log n+O(\log \log n)$redundant bits. This outperforms the best previously known result, which requires at least$8\log n$redundant bits. Moreover, we also consider the list-decoding problem under the two-edit channel and construct a two-edit list-decodable code with a list size of two employing$4 \log n+O(\log \log n)$redundant bits.

Motivated by certain emerging storage media, such as DNA storage and racetrack memories, we study the problem of designing$(n,N;\mathcal {D}_{k})$-reconstruction codes, where the deletion ball function$\mathcal {D}_{k}$maps a sequence of length$n$to the set consisting of all its subsequences of length$n-k$, in which any two distinct sequences do not share$N$distinct subsequences of length$n-k$. Note that the problem of designing$(n,N;\mathcal {D}_{k})$-reconstruction codes can be seen not only as a relaxed coding problem of$k$-deletion correcting codes, but also as a dual problem of the sequence reconstruction problem. In this work, we focus on the case when$k=2$and$2 \leq N \leq 6$. Note that when$N=1$, the best known$(n,N;\mathcal {D}_{2})$-reconstruction codes (two-deletion correcting codes) have$4 \log n + o(\log n)$bits of redundancy. Firstly, we improve the redundancy to$3 \log n + o(\log n)$when$N \in \{2,3\}$and further improve it to$2 \log n +o(\log n)$when$N=4$. Then, for$N \in \{5,6\}$, we design reconstruction codes with$\log n + o(\log n)$bits of redundancy outperforming the previous best known result$2 \log n+ o(\log n)$.

Motivated by applications in modern storage devices such as DNA storage and racetrack memories, we study the sequence reconstruction problem which involves two important issues. One is determining the maximum intersection size between two error balls. The other is designing reconstruction codes in which each transmitted sequence can be reconstructed from a given number of noisy reads with redundancy as small as possible. In this paper, we focus on channels that introduce single-burst-insertion/deletion error. We fully determine the maximum intersection size between two burst-insertion/deletion balls for both fixed-length and variable-length models. Then we characterize a pair of sequences when their burst-insertion/deletion balls have intersection of a certain size. Using these characterizations, we design reconstruction codes for all values$N$of the number of noisy reads and analyze their lower bounds. In addition, we extend our results to the burst-edit channel.

Permutation codes and multi-permutation codes have been widely considered due to their various applications, especially in flash memory. In this paper, we consider permutation codes and multi-permutation codes against a burst of stable deletions. In particular, we propose a construction of permutation codes correcting a burst stable deletion of length$s$, with redundancy$\log n+ 2\log \log n+O(1{)}$. Compared to the previous known results, our improvement relies on a different strategy to retrieve the missing symbol on the first row of the array representation of a permutation. We also generalize our constructions for multi-permutations and the variable length burst model. Furthermore, we propose a linear-time encoder with optimal redundancy for single stable deletion correcting permutation codes.