4
$\begingroup$

Is their an efficient mathematical way to estimate the distribution of minimal hamming distances for a set of random strings of length 8 over a 4-letter alphabet? E.g. given a set of 100-10,000 strings of length 8 over a 4-letter alphabet, determine for each sequence the minimal distance from the rest of the set and construct the overall distribution.

The motivation is bioinformatic e.g. comparing the observed vs. expected distributions to learn about the point-mutation rate. The observed distribution is calculated explicitly from the data but it would be nice to estimate the expected distribution mathematically. I assume that any deviation from a random distribution is caused by point mutations.

This is very related to a previous post which spoke about the expected minimal hamming distance but not the distribution itself.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ By random, do you mean independent and uniformly random, or a more complicated model that would agree more with observed DNA? $\endgroup$
    – Douglas Zare
    Apr 3, 2015 at 21:51
  • $\begingroup$ Independent and uniformly random. This isn't really DNA, it's a synthetic random sequence appended to individual molecules before exponential amplification (PCR) and used to correct for stochastic biases. In reality due to sequencing quirks I doubt it's quite literally uniform+random but I have no better model... $\endgroup$
    – queryous
    Apr 4, 2015 at 21:16
  • $\begingroup$ Isn't there a standard statistical tool in bioinformatics based on extreme value theory and the Gumbel distribution? I realise this isn't exactly an answer but I wanted to check you knew about it. See en.wikipedia.org/wiki/Gumbel_distribution for example. $\endgroup$
    – Simd
    Apr 5, 2015 at 18:07
  • $\begingroup$ @felix - how would you use the Gumbel here? I wasn't familiar with it btw so thanks for mentioning. $\endgroup$
    – queryous
    Apr 6, 2015 at 6:36

1 Answer 1

Reset to default
3
$\begingroup$

There are two natural meanings for the distribution of minimum distances. One is the probability distribution for the minimum distance to one point. Another is the multiset of minimum distances to each point. They are related. This answer addresses the first sense of distribution. For a partial answer to the second, see Minimum Hamming Distance Distribution in a Random Subset of Binary Vectors+.

The cumulative distribution of the minimum of $s$ IID random variables satisfies

$$1-\operatorname{CDF}_s(d) = (1-\operatorname{CDF}_1(d))^s$$

since each side is the probability that all $s$ variables are greater than $d$.

If you assume that the symbols are uniformly random and independent, then the distance of a given string to a fixed string follows a binomial distribution. The probability that a particular string will be within a distance $d$ is the cumulative distribution function for the binomial distribution,

$$\operatorname{CDF}_1(d) = \sum_{k=0}^d {n\choose k}p^k (1-p)^{n-k}$$

where $n$ is the length of the string, and $p$ is $3/4$ or $1-\frac{1}{|\textrm{alphabet}|}$.

There isn't a closed form expression for this, but you can estimate it in many ways. Some techniques are better at estimating the cumulative distribution function near the median, and some are better for the tails. See Lower bound for sum of binomial coefficients? and the techniques in Sum of 'the first k' binomial coefficients for fixed n . For many particular values, you can use an exact computation of the distribution rather than estimating it. For example, for $s=1000, n=8,p=3/4,$ here is some code that computes the cumulative distribution function values: 

cdf1[d_, n_, p_] := Sum[Binomial[n, k] p^k (1 - p)^(n - k), {k, 0, d}]
cdfs[d_, n_, p_, s_] := 1 - (1 - cdf1[d, n, p])^s
Table[N[cdfs[d, 8, 3/4, 1000]], {d, 0, 8}]

$0.01514,0.3172,0.9855,1.0000,1.0000,...$.

Improve this answer
$\endgroup$
7
  • $\begingroup$ Thanks! Can I extend your answer to calculate the probability of a given distribution with the multinomial formula? E.g. use the CDF from above to calculate p for each distance and plug these values into the multinomial variance to get a 'p-value-like' estimate for each distance. (Where the 'expected counts' are the null hypothesis and the 'observed counts' are the 'test case') $\endgroup$
    – queryous
    Apr 6, 2015 at 7:47
  • $\begingroup$ * by 'p-value like' I mean looking at the number of standard deviations separating the expected from the observed counts in each bin. Sorry for lack of clarity. $\endgroup$
    – queryous
    Apr 6, 2015 at 8:00
  • $\begingroup$ In a multinomial distribution, the draws are independent. With $s+1$ points, you have $s+1 \choose 2$ pairwise independent distances, but they are not fully independent. If you choose one point, the distances to the other $s$ are independent so you can compare these distances to a multinomial distribution with $s$ draws, but it isn't fair to compare all $s+1 \choose 2$ distances to a multinomial distribution with $s+1$ draws from the distance distribution. If the distance from $A$ to $B$ is small, and the distance from $B$ to $C$ is small, then the distance from $A$ to $C$ must be small. $\endgroup$
    – Douglas Zare
    Apr 6, 2015 at 12:59
  • $\begingroup$ Whether the lack of full independence makes a noticeable difference, I'm not sure. My guess is that in many settings it would not make a difference, but it might when you are looking at small $p$ values. $\endgroup$
    – Douglas Zare
    Apr 6, 2015 at 13:01
  • $\begingroup$ I feel like I might be making a 'Monty Hall' type error. Correct me if I'm wrong.. The CDF above is relevant for any random point in comparison to the other s, correct? Yet all points are chosen randomly, independently of each other and 'without order'='simultaneously' so, without additional information, I would expect each to have the same CDF. So then their aggregate should also have the same CDF. If this makes sense and it makes sense to look at a 'simultaneous multinomial sampling' without order such that no additional information exists I don't see where the dependence comes into play $\endgroup$
    – queryous
    Apr 6, 2015 at 14:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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