Probability of combinations of beads on cut necklaces (mass spectrometry physics problem)

Question

I have a math problem related to peptide mass spectrometry which I am unable to solve myself. Hopefully some of you guys will find it to be an interesting challenge. I have expressed it below in terms of beads on a necklace so that you hopefully won't need to understand the technology to solve the problem.

You have bags containing a near infinite number (for our purposes) of strings with an equal number of beads; lets call them necklaces. There are two types of beads; white and black. There is a certain abundance of white and black beads respectively which is the same in all conceivable bags, and these beads are randomly distributed on the necklaces. The necklaces are taken out of the bag and sorted into categories depending on the number of black beads they contain. This means that for a bag with necklaces of length five (five beads) there are six categories:

w = white
b = black

0: wwwww
1: bwwww, wbwww, wwbww, wwwbw, wwwwb
2: bbwww, bwbww, bwwbw, bwwwb, wbbww, wbwbw, wbwwb, wwbbw, wwbwb, wwwbb
3: bbbww, bbwbw, bbwwb, bwbbw, bwbwb, bwwbb, wbbbw, wbbwb, wbwbb, wwbbb
4: wbbbb, bwbbb, bbwbb, bbbwb, bbbbw
5: bbbbb

The necklaces have direction, meaning that wwwwb is not identical to bwwww.

Each category is more or less abundant, solely dependent on the abundance of black and white beads respectively. The relative abundances amount to 1 if summed:

I0 + I1 + I2 + I3 + I5 + ... = 1

After the necklaces are sorted, a subset of the first categories (containing least number of black beads; say category 0-3, or 0-2) are removed from the rest of the necklaces and each necklace is cut once at a random position, giving rise to a lot of smaller necklaces, that we will call fragments. These are again put in new bags depending on their new length and whether the fragment is the right or the left part of the original necklace. Each and every new bag will thus contain fragments of identical length, though still with different combinations of black and white beads. Consider a fragment of length four where a subset of category 0-2 was chosen earlier:

0: wwww
1: bwww, wbww, wwbw, wwwb
2: bbww, bwbw, bwwb, wbwb, wwbb, wbbw

Category 3 and 4 are not included, as these were not included in the chosen subset in this scenario.

Considering any of these bags with fragments, the question is: What are the relative abundances of the different categories? Are they equal to the relative abundances if one would just have chosen a necklace of the fragments's length and chosen the same subset?

For example:

1. A bag with necklaces of length 16 is chosen.
A subset of category 0-2 (0-2 black beads) is chosen.
The necklaces in the subset are fragmented.
For a specific fragment of length 6 the relative abundances between the 
catogories are I0, I1 and I2 (sum 1).

2. A bag with necklaces of length 6 is chosen.
A subset of category 0-2 (0-2 black beads) is chosen, which has the relative
abundances between the catogories I0', I1' and I2' (sum 1).

Is I0'=I0, I1'=I1, I'2=I2?

Let me know if you need anything else. I myself find it difficult to pose this question in a way that is easily understandable while still giving an answer to the real question. Any answer is greatly appreciated.

EDIT1: Bonus questions: What if we introduce more colors of beads? What if we introduce colors that count as double value regarding category (e.g. one of these beads on a necklace would raise the category by 2 instead of 1)?

Answer 1

For simplicity, I'm going to assume that the number of black beads in the bag is equal to the number of white beads. I think this technique could be extended to the case where the two types of beads have unequal probability, but I'm not 100% sure about that.

Suppose that the original chains are of length $N$, and they have no more than $n_{B}$ black beads; the fragments have $M$ beads. (In your example, $N = 5$, $M = 4$, and $n_{B} = 2$ or $3$.) We want to consider which original chains a fragment with $m_B$ black beads could have come from. For example, if $n_B = 2$ and $m_B = 1$ (as in your example), there are two options: the fragment BWWW could have arisen from either the chain BWWWW or BWWWB. However, if $n_B = 2$ and $m_B = 2$, there is only one option: the fragment BBWW could only have arisen from the chain BBWWW.

The probability of a given fragment of length $M$ having $m_B$ black beads is therefore the sum of all the probabilities of all of the possible "parent" chain, and the parent chain will have between $m_B$ and $n_B$ (inclusive) black beads. The probability of a given fragment with $m_B$ black beads arising is then proportional to the number possible "parent" chains. These "parent" chains can be formed by adding a sequence of $N - M$ beads to the given fragment, which have no more than $n_B - m_B$ black beads in them. The number of such sequences is $$ \sum_{k = 0}^{n_B - m_B} {N - M \choose k} $$ Finally, since there are ${M \choose m_B}$ fragments with $M$ beads & $m_B$, the overall probability of getting any such fragment is proportional to $$ \boxed{ \tilde{I}_{m_B} = {M \choose m_B} \sum_{k = 0}^{n_B - m_B} {N - M \choose k} .} $$ This will be a relative abundance rather than an overall abundance (i.e., the values of $\tilde{I}_{m_B}$ will not sum to 1), but we can normalize this by the appropriate sum of the $\tilde{I}_{m_B}$ values to get the absolute abundances.

Meanwhile, if we simply asked what the probability of getting any chain of $m_B$ black beads in a chain of $M$ beads by direct selection, this would be proportional to the number of sequences with $m_B$ black beads among $M$ total beads: $$ \boxed{ \tilde{I}'_{m_B} = {M \choose m_B} } $$ Again, this is a relative abundance that will have to be normalized to get an absolute abundance.

It seems fairly evident that these two equations will not return the same results. For example, with $M = 4$, $N = 5$, $n_B = 2$ and $p = 1/2$, we get

 m_B   I_m    I'_m
-------------------
  0    1/8    1/11
  1    1/2    4/11
  2    3/8    6/11

while for $N = 16$, $M = 6$, and $n_B = 2$ the numbers work out to be

 m_B         I_m            I'_m
--------------------------------------
  0    56/137 ≈ 0.409    1/22 ≈ 0.045
  1    66/137 ≈ 0.482    6/22 ≈ 0.273
  2    15/137 ≈ 0.109   15/22 ≈ 0.682

I was a little surprised by the large discrepancy in the second case, but I did a quick numerical simulation to confirm it. In retrospect, it should have been obvious. Among all of the necklaces of length 16 with no more than two of the beads black, a lot of them will have the first 6 beads all white (with the black beads later in the sequence). On the other hand, the probability of selecting 6 beads at random to be all white is fairly low, even if we only consider the necklaces with 2 black beads or fewer.