🚀 go-pugleaf

Gentle people,
  I started to work with sequences a couple of months ago and 
encountered a problem which may be different from those faced by 
biological sequence analysis but, hopefully, you can give me an 
answer or, at least, point me in the right direction.

The problem:
partition a given sequence S into a minimal number of patterns.

(We assume some finite alphabet and, of course, S is finite. The 
problem gets a bit different flavour when S may not have a partition, 
so let us assume that a partitioning of S is possible.)

A pattern P is any sequence with all symbols distinct and length at least 2.
P occurs in a sequence S if P is a subsequence of S (not necessarily 
a substring).
A subsequence of S is an
- do(P), disjoint occurence of P, if it consists of (at least 2) 
disjoint occurrences of pattern P
and it is an
- mdo(P), maximal do(P), if it is do(P) and there are no occurrences 
of P in the rest of S, i.e., in
S \ mdo(P) = the subsequence of S obtained by removing the subsequence mdo(P).

A partition (exact cover) of a sequence S is given by
   a) a set of mutually distinct (not necessarily disjoint) patterns 
P1...Pn, with
   b) mutually disjoint, nonempty subsequences do(P1)...do(Pn) of S which,
   c) together, constitute the whole S.
It is minimal if there is no partition with a smaller set a) (with 
fewer patterns).
It is MDO if all do(Pi) in point b) are, actually, mdo(Pi).

Question 1.
The problem seems - obviously - NP-hard but does anybody know of a 
proof of that?

Question 2.
Suppose that
    i) there is a minimal partition with N patterns, and
   ii) there is some MDO partition (obviously, with at least N patterns).
Is there, then, an MDO partition with N patterns?

Conjecture 2 (the answer Yes to question 2) is quite intriguing 
since, on the one hand, it seems plausible - a minimal partition 
should contain mdo's of involved patterns but, on the other hand, 
there seems to be no reason why it should happen to be the case. (If 
we drop the assumption ii), it is, in fact, wrong, i.e., there are 
sequences which can be partitioned with N patterns, but which have no 
MDO partition.) We have run tens of tests (on random sequences (with 
exact partitions) up to 20-30 symbols) and never met a counterexample 
to Conjecture 2.

Any hints are appreciated

	Michal
-- 

--------------------
Assoc. Prof. Michal Walicki
Institute of Informatics
University of Bergen
5020 Bergen, Norway
http://www.ii.uib.no/~michal
(on leave at IST, Lisbon, until 8.2010)