字符串中k-mer子串零出现概率的求解问题

First, let's clarify the problem setup to ensure we're aligned:

• We have an alphabet of 20 distinct characters, each with a unique probability of occurrence (denoted ( p_c ) for each character ( c ), where ( \sum_{c} p_c = 1 )).
• ( S ) is a random string of length ( n ), where each position is independently sampled from the alphabet according to these probabilities.
• ( s ) is a fixed k-mer (substring of length ( k < n )), and we want to find the probability that ( s ) does NOT appear anywhere in ( S ).

Exact Calculation Using Inclusion-Exclusion #

The most rigorous way to compute this probability uses the inclusion-exclusion principle, which accounts for overlapping occurrences of the k-mer (since overlapping k-mers are not independent events).

Step 1: Define Events #

Let ( A_i ) be the event that the k-mer ( s ) starts at position ( i ) in ( S ) (where ( 1 \leq i \leq n - k + 1 )). We want the probability that none of these events occur:
[
P(\text{no } s \text{ in } S) = P\left( \overline{A_1 \cup A_2 \cup \dots \cup A_{n-k+1}} \right)
]

Step 2: Inclusion-Exclusion Expansion #

By inclusion-exclusion, this probability expands to:
[
\sum_{m=0}^{n-k+1} (-1)^m \cdot \sum_{1 \leq i_1 < i_2 < \dots < i_m \leq n-k+1} P(A_{i_1} \cap A_{i_2} \cap \dots \cap A_{i_m})
]

• The ( m=0 ) term is simply ( 1 ) (the empty product).
• For ( m \geq 1 ), we need to calculate the probability that ( m ) specific starting positions all contain the k-mer ( s ).

Step 3: Handling Overlapping Events #

The probability ( P(A_{i_1} \cap \dots \cap A_{i_m}) ) depends on how the k-mers overlap:

1. Non-overlapping k-mers: If the distance between any two starting positions is at least ( k ), the events are independent, so the probability is ( q^m ), where ( q = \prod_{t=0}^{k-1} p_{s[t]} ) (the probability of ( s ) occurring in any single set of ( k ) consecutive positions).
2. Overlapping k-mers: For overlapping positions, first check if the overlapping segments of ( s ) are consistent. Define the autocorrelation function for ( s ): for ( 0 \leq t < k ), ( r_t = 1 ) if the first ( k-t ) characters of ( s ) equal the last ( k-t ) characters of ( s ); otherwise ( r_t = 0 ).
   • If overlapping k-mers are inconsistent (( r_t = 0 )), their joint occurrence is impossible, so the probability is ( 0 ).
   • If consistent (( r_t = 1 )), the joint probability is the product of probabilities for the combined unique characters in the merged substring (e.g., if ( s = "ABA" ) and starts at positions ( i ) and ( i+2 ), the merged substring is "ABABA", so the probability is ( p_A p_B p_A p_B p_A )).

Approximations for Large ( n ) or Rare k-mers #

Exact inclusion-exclusion can be computationally expensive for large ( n ). Here are two practical approximations:

1. Poisson Approximation #

If the k-mer ( s ) is rare (( q ) is small) and ( n ) is large, the number of occurrences of ( s ) approximates a Poisson distribution with parameter ( \lambda = (n - k + 1)q \approx nq ). The probability of zero occurrences is:
[
P(\text{no } s \text{ in } S) \approx e^{-\lambda} = e^{-nq}
]
This is highly accurate when ( \lambda \ll 1 ) (i.e., the expected number of occurrences is small).

2. First-Order Inclusion-Exclusion #

If overlaps are impossible (e.g., ( k=1 ) or ( s ) has no self-overlaps) or we want a quick rough estimate, we can ignore higher-order terms:
[
P(\text{no } s \text{ in } S) \approx 1 - (n - k + 1)q
]
This works well when ( (n - k +1)q \ll 1 ).

Example #

Suppose we have an alphabet where ( A ) has probability ( 0.1 ), ( B ) has probability ( 0.05 ), and 18 other characters have distinct probabilities. Let ( s = "AB" ) (k=2), ( n=100 ):

• ( q = p_A \cdot p_B = 0.1 \times 0.05 = 0.005 )
• Expected occurrences ( \lambda = (100-1) \times 0.005 = 0.495 )
• Poisson approximation: ( e^{-0.495} \approx 0.609 )
• Exact value (since ( s = "AB" ) can't overlap with itself): ( (1 - q)^{99} = (0.995)^{99} \approx 0.607 ), which is nearly identical to the Poisson result.

内容的提问来源于stack exchange，提问作者gkoul