東京大学 新領域創成科学研究科 メディカル情報生命専攻 2022年8月実施 問題12

标签：

• Tokyo-University
• Pattern-Occurrence-Probability
• Pattern-Occurrence-in-Independent-Identically-Distributed-Sequence

Author

zephyr, 祭音Myyura

Description

We would like to know the probability that the string $\mathbf{FRED}$ appears in a random protein sequence. Assume the sequence has random independent letters from the protein alphabet $A$, and letter $a \in A$ has probability $p(a)$. Define $Q(i, X)$ to be the probability that $\mathbf{FRED}$ appears in a random sequence of length $i$, given that the sequence ends with $X$, where $X$ is a length-4 string.

(1) What is $Q(4, X)$ when $X \neq \mathbf{FRED}$?

(2) What is $Q(4, X)$ when $X = \mathbf{FRED}$?

Define $X'$ to be $X$ without its final letter. Define $a \cdot X$ to be $X$ with letter $a$ prepended to it. These definitions may be useful to answer the following questions.

(3) What is $Q(i + 1, X)$, in terms of $Q(i, Y)$, where $Y$ is any length-4 string, when $X \neq \mathbf{FRED}$?

(4) What is $Q(i + 1, X)$ when $X = \mathbf{FRED}$?

Define $P(X)$ to be the product of the probabilities of the letters in $X$. Define $A^4$ to be the set of all possible length-4 strings. These definitions may be useful to answer the following question.

(5) What is the probability that $\mathbf{FRED}$ appears in a random sequence of length $n$, in terms of $Q(n, X)$?

题目描述

蛋白质字母表为 $A$，随机序列各位置独立同分布，字母 $a\in A$ 出现的概率为 $p(a)$。目标是计算连续字符串 FRED 在随机蛋白质序列中至少出现一次的概率。对任意长度为 4 的字符串 $X$，定义

$$Q(i,X)=P(\text{长度 }i\text{ 的随机序列中出现过 `FRED`}\mid \text{末四个字母为 }X).$$

回答下列问题：

1. 当 $X\ne\mathrm{FRED}$ 时求 $Q(4,X)$。

2. 当 $X=\mathrm{FRED}$ 时求 $Q(4,X)$。

3. 令 $X'$ 为删去 $X$ 最后一个字母所得的长度 3 字符串，$a\cdot X'$ 表示在其前端添加字母 $a$。当 $X\ne\mathrm{FRED}$ 时，用所有长度 4 字符串 $Y$ 对应的 $Q(i,Y)$ 表示 $Q(i+1,X)$。

4. 当 $X=\mathrm{FRED}$ 时求 $Q(i+1,X)$。

5. 定义

   $$P(X)=\prod_{\text{字母 }a\text{ 出现在 }X\text{ 的各位置}}p(a),$$

   并令 $A^4$ 为全部长度 4 字符串的集合。用 $Q(n,X)$、$P(X)$ 对 $X\in A^4$ 的加权和表示长度 $n$ 随机序列中 FRED 出现的无条件概率。

Kai

Conditional probabilities below are used for suffixes with $P(X)>0$. Suffixes with zero probability are omitted from the weighted sum. If any of F, R, E or D has probability zero, the unconditional occurrence probability is zero.

(1)

$Q(4, X)$ when $X \neq \mathbf{FRED}$:

If $X \neq \mathbf{FRED}$, then $\mathbf{FRED}$ has not appeared by the time the sequence reaches length 4 with ending $X$. Therefore, the probability $Q(4, X) = 0$.

$$Q(4, X) = 0 \quad \text{for} \quad X \neq \mathbf{FRED}$$

(2)

$Q(4, X)$ when $X = \mathbf{FRED}$:

If $X = \mathbf{FRED}$, then the sequence exactly matches $\mathbf{FRED}$, meaning $\mathbf{FRED}$ has appeared. Therefore, the probability $Q(4, \mathbf{FRED}) = 1$.

$$Q(4, \mathbf{FRED}) = 1$$

(3)

$Q(i + 1, X)$ in terms of $Q(i, Y)$ when $X \neq \mathbf{FRED}$:

To find $Q(i + 1, X)$, we need to consider all possible sequences of length $i$ that could lead to a sequence ending with $X$ when an additional letter is appended. Specifically, $Q(i + 1, X)$ depends on $Q(i, a \cdot X')$ for all possible letters $a \in A$.

Since $X \neq \mathbf{FRED}$, we have:

$$Q(i + 1, X) = \sum_{a \in A} p(a) Q(i, a \cdot X')$$

(4)

$Q(i + 1, X)$ when $X = \mathbf{FRED}$:

If the sequence ends in $\mathbf{FRED}$ at length $i+1$, then $\mathbf{FRED}$ has appeared, so $Q(i + 1, \mathbf{FRED}) = 1$.

$$Q(i + 1, \mathbf{FRED}) = 1$$

(5)

The probability that $\mathbf{FRED}$ appears in a random sequence of length $n$:

To find the total probability that $\mathbf{FRED}$ appears in a sequence of length $n$, we will consider 3 cases:

1. $n < 4$: In this case, $\mathbf{FRED}$ cannot appear, so the probability is 0.

2. $n = 4$: Only the ending $X=\mathbf{FRED}$ contributes, so the probability is $P(\mathbf{FRED})Q(4,\mathbf{FRED})=p(F)p(R)p(E)p(D)$.

3. $n > 4$: The probability that $\mathbf{FRED}$ appears in a sequence of length $n$ is given by:

$$\Pr\{\mathbf{FRED}\text{ appears}\}=\sum_{X \in A^4}P(X)Q(n,X)$$

where $P(X)$ is the product of the probabilities of the letters in $X$.

Therefore, the probability that $\mathbf{FRED}$ appears in a random sequence of length $n$ can be concluded as follows:

$$\Pr\{\mathbf{FRED}\text{ appears in length }n\} = \begin{cases} 0 & \text{if} \quad n < 4 \\ p(F) \cdot p(R) \cdot p(E) \cdot p(D) & \text{if} \quad n = 4 \\ \sum_{X \in A^4}P(X)Q(n,X) & \text{if} \quad n > 4 \end{cases}$$

Knowledge

概率论 随机序列 字符串出现概率

难点解题思路

对于随机序列中特定字符串的出现概率问题，关键在于递推关系的构建以及边界条件的处理。通过定义恰当的递推公式，可以逐步推导出所需概率。

解题技巧和信息

1. 构建递推关系，考虑当前状态如何从前一个状态转移。
2. 确定边界条件，并基于这些条件初始化递推公式。
3. 注意概率的加总，确保所有可能的转移情况都被考虑在内。

重点词汇

• Probability: 概率
• Sequence: 序列
• Random: 随机的
• Independent: 独立的
• Recurrence relation: 递推关系

参考资料

1. Introduction to Probability Models, Chapter 3
2. Probability and Statistics for Engineers and Scientists, Chapter 5