Tell me more ×
Cross Validated is a question and answer site for statisticians, data analysts, data miners and data visualization experts. It's 100% free, no registration required.
up vote 1 down vote favorite

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?

share|improve this question
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
show 1 more comment

1 Answer

up vote 0 down vote accepted

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...

share|improve this answer
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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.