Efficient Reconstruction of Sequences from Their Subsequences or Supersequences

✍ Scribed by Vladimir I. Levenshtein

• Publisher: Elsevier Science
• Year: 2001
• Tongue: English
• Weight: 176 KB
• Volume: 93
• Category: Article
• ISSN: 0097-3165
• DOI: 10.1006/jcta.2000.3081

✦ Synopsis

In the paper two combinatorial problems for the set F n q of sequences of length n over the alphabet F q =[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 F n q 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 # F n q which are sufficient for its reconstruction. Simple algorithms to recover X # F n q 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.