From saulsch@math.rutgers.edu  Sat Apr 15 23:06:54 2006
Received: from localhost (saulsch@localhost)
	by math.rutgers.edu (8.11.7p1+Sun/8.8.8) with ESMTP id k3G36rn14059
	for <zeilberg@math.rutgers.edu>; Sat, 15 Apr 2006 23:06:53 -0400 (EDT)
Date: Sat, 15 Apr 2006 23:06:53 -0400 (EDT)
From: Saul Schleimer <saulsch@math.rutgers.edu>
To: Doron Zeilberger <zeilberg@math.rutgers.edu>
Subject: bio problem
Message-ID: <Pine.GSO.4.44.0604152249150.10344-100000@math.rutgers.edu>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Status: RO
Content-Length: 794


Doron --

  Here is a mathematical problem asked of me by a biologist.  (So it must
be a math bio question).

\begin
  Fix an alphabat with four characters.  Fix a positive integer k.  Let
\Sigma be the set of all words in the alphabet of length k.  We call a
circular sequence \sigma a _de_Bruijn_ sequence if every element of \Sigma
appears exactly once as a substring of \sigma.
  If \sigma and \tau are de Brujin sequences call them _opposing_
sequences if they do not share any common subsequence of length k + 1.

1. Do opposing sequences exist?

2. Is there a decent way of producing them, given k?

3. Are there any "canonical" opposing pairs?
\end

The application is to designing DNA arrays of some kind.  I am a bit hazy
on the details but could find out more.

all the best,

saul

From saulsch@math.rutgers.edu  Sun Apr 16 09:19:06 2006
Received: from localhost (saulsch@localhost)
	by math.rutgers.edu (8.11.7p1+Sun/8.8.8) with ESMTP id k3GDJ5S20339
	for <zeilberg@math.rutgers.edu>; Sun, 16 Apr 2006 09:19:05 -0400 (EDT)
Date: Sun, 16 Apr 2006 09:19:05 -0400 (EDT)
From: Saul Schleimer <saulsch@math.rutgers.edu>
To: Doron Zeilberger <zeilberg@math.rutgers.edu>
Subject: Re: bio problem
In-Reply-To: <Pine.GSO.4.44.0604152249150.10344-100000@math.rutgers.edu>
Message-ID: <Pine.GSO.4.44.0604160911220.19136-100000@math.rutgers.edu>
MIME-Version: 1.0
Content-Type: TEXT/PLAIN; charset=US-ASCII
Status: RO
Content-Length: 1022


Doron --

  After thinking a bit more I have made the question harder:

>   Fix an alphabat with four characters.  Fix a positive integer k.  Let
> \Sigma be the set of all words in the alphabet of length k.  We call a
> circular sequence \sigma a _de_Bruijn_ sequence if every element of \Sigma
> appears exactly once as a substring of \sigma.
>   If \sigma and \tau are de Brujin sequences call them _opposing_
> sequences if they do not share any common subsequence of length k + 1.
>
> 1. Do opposing sequences exist?
>
> 2. Is there a decent way of producing them, given k?
>
> 3. Are there any "canonical" opposing pairs?

Call \sigma and \tau _m-opposing_ if for any pair of substrings of length
m, say \sigma' in \sigma and \tau' in \tau, there is at most one word of
length k appearing in both \sigma' and \tau'.

1. Clearly these exist (take m = k).  How much larger than k can m be?

2. Is there a way of producing them given k and m?

3. Are there "canonical" pairs?

Thanks for looking at this!

best,

saul