1
$\begingroup$

My question is actually quite short, but I'll have to start by describing the context since I am not sure how to directly ask it.

Consider the following "game":

We have a segment of length n ("large segment") and m integers ("lengths"), all considerably smaller than n. For each of the m lengths we draw a random sub-segment of its length on the large segment. For example, if the large segment is of size 1000 (i.e. 1..1000) and we are given lengths 20, 10, 50, than a possible solution would be: 31..50, 35..44, 921..970 (sub-segments of lengths 20, 10 and 50 respectively).

Notes: 1. This is just a toy example. We usually have many more lengths so there are many overlaps and each position in the large segment is covered by multiple sub-segments. 2. Remember that the lengths are given; only their mapping to the large segment is random. 3. Drawing a sub-segment of length k is done bu simply drawing a number from a uniform distribution over 1..n-k (a sub-segment of size k can start at position 1, 2, ... n-k).

Now, we conduct many simulations of the process an d record the data. We finally examine for each position the distribution of number of sub-segments covering this position. If we look at positions that are relatively far from the edges of the large segment, the distribution in each such position is normal, and all the distributions look the same. The "problem" is that the positions at the ends do not look normal at all. This is not surprising, since, for example, if we are now drawing a sub-segment of length 10, the only way the very first position in the large segment will be covered is if we draw 1, whereas, for example, the 10th position will be covered if we draw 1,2,3,..10.

What I am trying to figure out is what is the kind of distribution we see in the "edge" positions (it's not normal, but I think it usually looks like a normal distribution with its tail cut in one direction), and also how can I approximate this distribution density function from my simulations. For the "center" positions, I just estimate the mean and standard deviation and since I beleive the distributions there are normal - I can use the normal density function. This alos makes me think if I really need to treat the positions in a categorical way - "near the edges" and "not near the edges", or whether there are actually the same in some sort (some generalization of the normal distribution?).

Thank you, and sorry again for the length of the post.

$\endgroup$
  • $\begingroup$ You mean that you are looking at the distribution of subsample lengths of subsegments covering each position, right? On the other hand (probably I'm wrong) I'm guessing it has something to do with the sequencing? $\endgroup$ – user88 Jul 31 '10 at 18:40
  • $\begingroup$ No, I'm looking at the distribution of the number of sub-segments covering a specific position. For example, if we focus on position 1 in the large segment, in the first simulation we have 4 sub-segments covering it; in the second simulation we have 1 sub-segment covering it, etc. I don't care what are the lengths of the sub-segments covering each position, just how many sub-segments there are. You are not completely wrong, this has started as a part of an exercise I've been working on in a biology course, but has gone to another domain :) $\endgroup$ – David B Jul 31 '10 at 18:45
  • $\begingroup$ Still, one more doubt -- what is a distribution of the lengths of subsamples? I think it is crucial to the answer. (I'm suspecting it is a binomial distribution) $\endgroup$ – user88 Jul 31 '10 at 18:58
  • $\begingroup$ the lengths of the sub-segments? A list of lengths is given. I believe the lengths distribute quite normally, but I did not check it. $\endgroup$ – David B Jul 31 '10 at 19:01
  • $\begingroup$ sounds like a poisson distribution... $\endgroup$ – John Jul 31 '10 at 19:08
4
$\begingroup$

I'm not sure I understand your question exactly, but I assume you are looking for the probability mass at each point, where an event is defined as a subsegment covering a particular position. If this is true, I believe you should be able to work out the exact probability mass function.

For each subsegment of length K the distribution at a particular location between K and N-K+1 is uniform and proportional to K. The distribution at the tails is stepwise increasing from 1 to K. This can be seen by just working out one example.

Given multiple subsegments of different sizes, simply add these functions up. You can then normalize everything so the weights sum to one if you want a proper distribution function. Given a length and a list of subsegment lengths, this probability mass function should be easy to code up in the language of your choice.

If you are interested in the number of segments covering any point, this is simply the sum of Bernoulli random variables with different p, defined at each point using the same pmf. The simplest approach would be to enumerate the possibilities from 1 to K.

$\endgroup$
  • $\begingroup$ I think I got the idea, although I will have to think about it some more. One other thing I intentionally did not mention at the beginning, is the fact we might have predefined "hot" subranges along our long segment. This means that every subrange that is drawn and completely includes one of the "hot" subranges will not be counted (it will be totally elimnated, not drawn again). $\endgroup$ – David B Jul 31 '10 at 19:12
  • $\begingroup$ For example, if we have a predefined "hot" subrange 20..25 and we are now drawing a subrange of length 40, and we happen to draw 11..50, than we don't count anything (we throw this subrange). However, if we happen to draw 21..60 we count as normal (since our subrange does not include the complete hot subrange, only part of it). $\endgroup$ – David B Jul 31 '10 at 19:13
  • $\begingroup$ If you want the pmf, then it seems the only sensible thing to do is to actually construct it. Some sort of counting approach probably works best, similar to what I suggested where you don't need to actually count everything. It's not clear what your goal is though. If you're interested in the pmf, then an exact pmf is obviously better than some ad hoc approximation. If you're interested in some underlying parameter, the fact that you can easily simulate from your distribution opens other possibilities. $\endgroup$ – Tristan Jul 31 '10 at 19:25
  • $\begingroup$ OK, so what I really want is the following: I do not know if where the hotspots are (how many are there or how long is each hotspit), but I do have a few hypotheses (each hypothesis is a set of hotspots; each hotspot is just a subrange). These are hidden variables. I also have one "true" mapping - where all the lengths were drawn and mapped to the long range. This is my data. What I aim to do is to check which of my hypotheses is most likely given the data (the "true" mapping). $\endgroup$ – David B Jul 31 '10 at 19:36
  • $\begingroup$ (and sorry I can't vote-up yet, I'm still new here :)) $\endgroup$ – David B Jul 31 '10 at 19:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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