Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This question will sound oddly specific like it's my homework but it's not. It's my research and I could use some help thinking about it.

A person has 20 amino acids to choose from in constructing a protein. Given a sequence that is 30 amino acids long, what is the odds of two to 64 people sharing the same sequence if each amino acid is random.

Here are the parameters.

  1. We have read 64 patients

  2. Among the 64 patients we have 373,334 reads all of the length of 30, you can think about these as 373,334 different genes, not to confuse things.

  3. Of those reads 250,802 are shared among at least 2 or more patients.

I know that for any given sequence, if it is random, the probability of seeing that sequence is
$$\rho_x = {1\over{20}^{30}}$$

but what is the probability of seeing that sequence $\rho_x $ in two patients. What is the probability of seeing it three patients...and so on? Is there a general formula I can use if change the amount of reads and read length?

I appreciate the help, J

share|cite|improve this question
This might help. – polkjh Jan 18 '13 at 2:38
up vote 3 down vote accepted

Assume that the sequences of the patients are independent and identically distributed random variables, and that the distribution is uniform. Let $N$ be the number of possible sequences, so the probability of seeing a particular one in a particular patient is $1/N$. Here $N = 20^{30}$.

Let $P$ be the number of patients. Here $P = 64$.

Because $N$ is very large (compared to everything else we might consider) we can use the following approximation. The number of unordered pairs of patients is given by the binomial coefficient $\binom{P}{2}$, and for each one of these pairs the odds of the sequence being the same is $1/N$. So the probability that some pair shares a sequence is less than $\binom{P}{2} / N$. The reason that the probability is less than this figure and not equal to it is that the figure over-counts the event that three people have the same sequence. However, the odds of three people sharing a sequence is even more astronomically unlikely, so the figure above gives a good approximation.

To get the exact answer, it is easiest to first calculate the probability that no two patients have the same sequence, and then subtract this from 1. The number of ways to achieve this event is $\frac{N!}{(N-P)!}$, and the total number of choices of sequences is $N^P$, so $\frac{N!}{(N-P)!} / N^P$. So the exact probability that some sequence is shared by at least two patients is $1-\frac{N!}{(N-P)!} / N^P$.

share|cite|improve this answer

Your Answer


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.