Efficient Reconstruction of Sequences from Their Subsequences or Supersequences

In the paper two combinatorial problems for the set Fnq of sequences of length n over the alphabet Fq={0, 1, …, q−1} are considered. The maximum size N−q(n, t) of the set of common subsequences of length n−t and the maximum size N+q(n, t) of the set of common supersequences of length n+t of two different sequences of Fnq are found for any nonnegative integers n and t. The number N−q(n, t)+1 (respectively, N+q(n, t)+1) is equal to the minimum number N of different subsequences of length n−t (supersequences of length n+t) of an unknown sequence X∈Fnq which are sufficient for its reconstruction. Simple algorithms to recover X∈Fnq from N−q(n, t)+1 of its subsequences of length n−t and from N+q(n, t)+1 of its supersequences of length n+t are given.