The problem of reconstructing an arbitrary binary sequence of length n by the minimum number of its subsequences of length n - t is considered. For any t the corresponding minimum number of subsequences which are sufficient to reconstruct uniquely an unknown sequence is found. An algorithm for reconstructing sequences by this minimum number of their subsequences based on majority and threshold functions is presented. As a preliminary result, for any t the maximum number of sequences of length n - t of a binary sequence of length n is found. In discussing general applicability and extensibility of algorithms for this problem, bounds are given on the average number of sequences of length n - t of a binary sequence of length n.
The presentation consists of work due to Vladimir I. Levenshtein* plus extensions due to Dan Hirschberg.
* V. I. Levenshtein, "Reconstructing binary sequences by a minimum number of their subsequences or supersequences of a given length," Proc. 5th Int. Wkshop on Alg. and Combinatorial Coding Theory, Sozopol, Bulgaria, Jun 1-7, 1996, pp. 176-183.