Ordered sampling of uniform variables

I need to sample starting positions in a DNA sequence of given length L.

These starting positions represent starting points of functional domains in DNA sequences. They have a length of d. The starting positions should be distributed uniformly and must have a minimal distance of d between them (functional domains should not overlap). Positions higher then L-d+1 are not possible because functional domains should be complete.

The approach of sampling iterativly a starting position i and procecede with sampling in uniformly in the interval [i+d, L-d+1] does not produce a uniform distribution.

Do you know of any solution to this?

• Depending on the relative sizes of L, d and the number of samples you need, this may work: sample starting positions uniformly without the distance requirement, and reject if the distance requirement is not met. Typically you're not going to have many functional domain starting points in a sequence, so you should not get too many rejections. – Nick Sabbe Sep 15 '11 at 10:21
• Surely this is correct but I was wondering for a more elegant solution. – peri4n Sep 15 '11 at 10:31
• Elegance is in the eye of the beholder. But: I didn't post it as a solution :-) – Nick Sabbe Sep 15 '11 at 11:19
• Actually, come to think of it: what do you mean by uniform distribution in this case? If e.g. L is 4 and d is 2 while n is also 2, the only solution is to take positions 1 and 3. In what way can this ever be 'distributed uniformly'? – Nick Sabbe Sep 15 '11 at 11:26
• Surely this would be uniform distributed. Every solution (there is only one) has the same probability (1). – peri4n Sep 15 '11 at 11:28

In java'ish pseudo-code:

curpos=-d+1
for(i=1; i<=n; i++)
{
maxendrange=L-(n-i+1)*d // make sure there's room for all the remaining domains
minstartrange=curpos+d //skip the previous domain
newpos=sampleuniform(minstartrange, maxendrange)
//store result somewhere
}

I haven't proved it or anything, but I'm quite sure this should give equal probability to all possible solutions.

Edit: Within the loop, you would have to weight based on how many ways you can position $n-i$ domains (with the distance restriction) in a sequence of length $L-(curpos+2d)$. It's going to require a lot of calculations that are bound to be more 'expensive' than simply sampling without the distance requirement and rejecting based on it.

As such I return to my original idea (as mentioned in my comment): it will probably be the most effective solution...

• Against your intuition. This is clearly not uniform distributed. :D – peri4n Sep 15 '11 at 14:24
• The more I investigate in this problem. The more I think you are right. I have a mathematical approximation. A benchmark will decide which way is the best. – peri4n Sep 15 '11 at 18:42