# ICS 269, Fall 1998: Theory Seminar

## October 23, 1998:

Reconstructing Binary Sequences by the Minimum Number of their
Subsequences

Dan Hirschberg, ICS, UC Irvine

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.