Вероятность нахождения конкретной последовательности пар оснований

10

Размышления о вероятности всегда заставляют меня понять, насколько я плох в подсчете ...

Рассмотрим последовательность из базовых букв , каждый из которых имеет одинаковую вероятность. Какова вероятность того, что эта последовательность содержит конкретную последовательность пар оснований, представляющих интерес длины ? $n$ $A,\; T, \; C, \text{ and } G$ $r\leq n$

Возможны различных (одинаково вероятных) последовательностей. Начните с интересующей последовательности в начале полной последовательности; последовательности, подобные этой, возможны. Мы можем начать нашу последовательность интересов в разных местах. Следовательно, мой ответ . $4^n$ $4^{n-r}$ $n+1 -r$ $(n+1-r)/4^r$

Эта вероятность увеличивается в , что имеет смысл для меня. Но эта вероятность превышает 1, когда . Но этого не может быть. Вероятность должна приближаться к 1 в пределе (мне кажется), но не превышать его. $n$ $n>4^r +r-1$

Я предполагаю, что я что-то считаю дважды. Что мне не хватает? Спасибо.

(К вашему сведению, не домашняя работа, просто игрушечный пример для подготовки к экзаменам. Вопрос, заданный моим другом-молекулярным биологом.)

probability combinatorics Чарли
источник

Это правильно, не должно превышать единицу, поскольку это нарушит аксиомы вероятности: books.google.com/…

Крис Симокат,

1

(Смутно) связано: stats.stackexchange.com/questions/12174/…

кардинал

5

Давайте рассмотрим небольшую версию этой проблемы с . Какова вероятность того, что последовательность из пяти букв будет содержать целевой файл ? Это легко: всех последовательностей начинаются с этой строки, еще заканчиваются ею, и никакая последовательность не начинается и не заканчивается этой строкой. Следовательно, шанс равен . $n=5$ $\ldots A C G T\ldots$ $4^{-4}$ $4^{-4}$ $2 \times 4^{-4}$

С другой стороны, какова вероятность ? Еще раз, последовательностей начинаются с этой строки, та же самая пропорция заканчивается этой строкой, и всех последовательностей делают оба . Поэтому, согласно принципу включения-исключения, ответ будет . $\ldots A A A A \ldots$ $4^{-4}$ $4^{-5}$ $2 \times 4^{-4} - 4^{-5}$

В общем случае ответ зависит от структуры подстроки. Чтобы быть более конкретным, когда вы сканируете строку (слева направо, скажем) для , вы игнорируете все символы до тех пор , пока не увидите , что первоначальный . После этого, есть три возможности: следующий символ является матчем для , следующий один не является матч для , но это не (так что вы вернулись в годов- поживет для- состояние), или следующий один не является матч еще что это , помещая вас в точно пилообразной ап- состояние. Напротив, рассмотрим поиск . Предположим, вы видели префикс $ACGT$ $A$ $C$ $C$ $A$ $A$ $A$ $A$ $ACTACG$ $ACTAC$ , Следующий символ будет соответствовать , если это . Когда это не соответствует, (i) переводит вас в начальное состояние ожидания , (ii) заставляет вас следить за , и (iii) означает, что вы уже видели и вы уже на полпути к матчу (и ищете второй ). Соответствующая «структура», очевидно, состоит из шаблонов подстрок в цели, которые соответствуют префиксу цели. Вот почему шансы зависят от целевой строки. $G$ $C$ $A$ $A$ $C$ $T$ $\ldots ACT$ $A$

Диаграммы FSA, которые я защищаю в ответе в « Времени», взятом для того, чтобы нанести удар головой и хвостом в серии бросков, могут помочь в понимании этого явления.

Whuber
источник

3

Грубое приближение было бы . Вы берете вероятность того, что ваша последовательность не встречается в определенном месте, приравниваете ее к степени количества местоположений (ложно предполагая независимость), которая равна , а не , и это является приближением ее отсутствия поэтому вам нужно вычесть это из . $1-(1-1/4^r)^{n-r+1}$ $n-r+1$ $n-r$ $1$

Точный расчет будет зависеть от того, какой именно шаблон вы ищете. , скорее всего, не произойдет, чем . $AAAAA$ $ATCGT$

Генри
источник

Может быть, это только я, но кажется немного более ясным с точки зрения понимания того, как было построено уравнение.

1 - (1 - (1 / 4)^{r})^{n - (r - 1)}

$1-(1-(1/4)^r)^{n-(r-1)}$

@JoeRocc - Я подозреваю, что это личное. Если вы читаете со страницы до страницы книги, читали ли вы страница или страница?

300

$300$

400

$400$

400 - 300 + 1 = 101

$400-300+1=101$

400 - (300 - 1) = 101

$400-(300-1)=101$

Генри

Не беспокойтесь, я исходил из своей интуиции проблемы. Если мы интуитивно выведем уравнение, которое будет , то, пытаясь объяснить это кому-то, я думаю, что лучше оставить его таким, а не упрощать его до (хотя это, безусловно, может оказаться более интуитивным при рассмотрении). Ваша интуиция может быть другой в любом случае :)

(a - (b - (c - 1 + d)))

$(a-(b-(c-1+d)))$

a - b + c - 1 + d

$a-b+c-1+d$

2

Вы дважды подсчитываете последовательности, которые в несколько раз включают вашу целевую подпоследовательность, например, как в позиции A, так и в позиции B! = A. Вот почему ваша ошибочная вероятность может превышать 1

user145136
источник

Очень хорошо сделано ! +1

Михаил Р. Черник

1

Можно получить точную вероятность конкретной подпоследовательности, используя цепную марковскую задачу. Особенности построения цепочки зависят от конкретной интересующей подпоследовательности, но я приведу несколько примеров того, как это сделать.

Точная вероятность по цепочке Маркова. Рассмотрим дискретную последовательность результатов где результаты в последовательности являются взаимозаменяемыми, и предположим, что нас интересует некоторая подстрока длины . Для любого заданного значения , пусть будет событием, когда возникает интересующая подстрока, и пусть будет событием, когда последними результатами являются первые символов в подстроке интерес (но не более того). Мы используем эти события, чтобы дать следующий раздел возможных состояний интереса: $A,T,C,G$ $k$ $n$ $\mathscr{W}$ $\mathscr{H}_a$ $a$ $a < k$ $k+1$

\begin{matrix} State 0 & \bar{W} \cap H_{0}, \\ State 1 & \bar{W} \cap H_{1}, \\ State 2 & \bar{W} \cap H_{2}, \\ State 3 & \bar{W} \cap H_{3}, \\ ⋮ & ⋮ \\ State k - 1 & \bar{W} \cap H_{k - 1}, \\ State k & W . \end{matrix}

$\begin{matrix} \text{State 0} & & & \bar{\mathscr{W}} \cap \mathscr{H_0}, \text{ } \text{ } \text{ } \\[6pt] \text{State 1} & & & \bar{\mathscr{W}} \cap \mathscr{H_1}, \text{ } \text{ } \text{ } \\[6pt] \text{State 2} & & & \bar{\mathscr{W}} \cap \mathscr{H_2}, \text{ } \text{ } \text{ } \\[6pt] \text{State 3} & & & \bar{\mathscr{W}} \cap \mathscr{H_3}, \text{ } \text{ } \text{ } \\[6pt] \vdots & & & \vdots \\[6pt] \text{State }k-1 & & & \bar{\mathscr{W}} \cap \mathscr{H_{k-1}}, \\[6pt] \text{State }k & & & \mathscr{W}. \quad \quad \quad \text{ } \text{ } \\[6pt] \\[6pt] \end{matrix}$

Поскольку предполагается, что последовательность результатов является у нас есть независимые результаты, зависящие от их соответствующих вероятностей . Интересующий вас процесс может быть представлен в виде цепей Маркова с дискретным временем, которые начинаются в при и переходят в соответствии с матрицей вероятности, которая зависит от конкретной интересующей подстроки. Матрица перехода всегда будет $\theta_A + \theta_T + \theta_C + \theta_G = 1$ $\text{State 0}$ $n=0$ $(k+1) \times (k+1)$ матрица, представляющая вероятности перехода с использованием вышеуказанных состояний. Если интересующая подстрока не была достигнута, то каждый переход может либо приблизить вас на один шаг к подстроке, либо вернуть вас в предыдущее состояние, которое зависит от конкретной подстроки. Как только подстрока достигнута, это поглощающее состояние цепи, представляющее тот факт, что произошло интересующее событие.

Например, если интересующей подстрокой является тогда матрица перехода: $AAAAAA$

P = [\begin{matrix} 1 - θ_{A} & θ_{A} & 0 & 0 & 0 & 0 & 0 \\ 1 - θ_{A} & 0 & θ_{A} & 0 & 0 & 0 & 0 \\ 1 - θ_{A} & 0 & 0 & θ_{A} & 0 & 0 & 0 \\ 1 - θ_{A} & 0 & 0 & 0 & θ_{A} & 0 & 0 \\ 1 - θ_{A} & 0 & 0 & 0 & 0 & θ_{A} & 0 \\ 1 - θ_{A} & 0 & 0 & 0 & 0 & 0 & θ_{A} \\ 0 & 0 & 0 & 0 & 0 & 0 & 1. \end{matrix}]

$\mathbf{P} = \begin{bmatrix} 1-\theta_A & \theta_A & 0 & 0 & 0 & 0 & 0 \\[6pt] 1-\theta_A & 0 & \theta_A & 0 & 0 & 0 & 0 \\[6pt] 1-\theta_A & 0 & 0 & \theta_A & 0 & 0 & 0 \\[6pt] 1-\theta_A & 0 & 0 & 0 & \theta_A & 0 & 0 \\[6pt] 1-\theta_A & 0 & 0 & 0 & 0 & \theta_A & 0 \\[6pt] 1-\theta_A & 0 & 0 & 0 & 0 & 0 & \theta_A \\[6pt] 0 & 0 & 0 & 0 & 0 & 0 & 1. \\[6pt] \end{bmatrix}$

И наоборот, если интересующей подстрокой является тогда матрица перехода: $ACTAGC$

P = [\begin{matrix} 1 - θ_{A} & θ_{A} & 0 & 0 & 0 & 0 \\ 1 - θ_{A} - θ_{C} & θ_{A} & θ_{C} & 0 & 0 & 0 & 0 \\ 1 - θ_{A} - θ_{T} & θ_{A} & 0 & θ_{T} & 0 & 0 & 0 \\ 1 - θ_{A} & 0 & 0 & 0 & θ_{A} & 0 & 0 \\ 1 - θ_{A} - θ_{C} - θ_{G} & θ_{A} & θ_{C} & 0 & 0 & θ_{G} & 0 \\ 1 - θ_{A} - θ_{C} & θ_{A} & 0 & 0 & 0 & 0 & θ_{C} \\ 0 & 0 & 0 & 0 & 0 & 0 & 1. \end{matrix}]

$\mathbf{P} = \begin{bmatrix} 1-\theta_A & \theta_A & 0 & 0 & 0 & 0 \\[6pt] 1-\theta_A-\theta_C & \theta_A & \theta_C & 0 & 0 & 0 & 0 \\[6pt] 1-\theta_A-\theta_T & \theta_A & 0 & \theta_T & 0 & 0 & 0 \\[6pt] 1-\theta_A & 0 & 0 & 0 & \theta_A & 0 & 0 \\[6pt] 1-\theta_A-\theta_C-\theta_G & \theta_A & \theta_C & 0 & 0 & \theta_G & 0 \\[6pt] 1-\theta_A-\theta_C & \theta_A & 0 & 0 & 0 & 0 & \theta_C \\[6pt] 0 & 0 & 0 & 0 & 0 & 0 & 1. \\[6pt] \end{bmatrix}$

Как видно выше, построение матрицы перехода требует внимания к конкретной подстроке. Неправильный результат возвращает вас к предыдущему состоянию в строке, которое зависит от конкретной интересующей подстроки. Как только матрица перехода построена, для данного значения вероятность наличия подстроки в цепочке равна . (Эта вероятность равна нулю для всех .) $n$ $\mathbb{P}(\mathscr{W} | n) = \{ \mathbf{P}^n \}_{0,k}$ $n<k$

Программирование этого в R: Вы можете запрограммировать это как функцию R, создав функцию, которая генерирует матрицу переходов для цепи Маркова и массив ее степеней вплоть до некоторого желаемого количества испытаний. Затем вы можете прочитать соответствующую вероятность перехода для значения которое представляет интерес. Вот пример кода для этого: $n$

#Create function to give n-step transition matrix for n = 1...N
#We will use the example of the substring of interest "AAAAAA"

#a is the probability of A
#t is the probability of T
#c is the probability of C
#g is the probability of G
#N is the last value of n
PROB <- function(N,a,t,c,g) { TOT <- a+t+c+g;
                              a <- a/TOT; 
                              t <- t/TOT; 
                              c <- c/TOT; 
                              g <- g/TOT; 

                              P <- matrix(c(1-a, a, 0, 0, 0, 0, 0,
                                            1-a, 0, a, 0, 0, 0, 0,
                                            1-a, 0, 0, a, 0, 0, 0,
                                            1-a, 0, 0, 0, a, 0, 0,
                                            1-a, 0, 0, 0, 0, a, 0,
                                            1-a, 0, 0, 0, 0, 0, a,
                                              0, 0, 0, 0, 0, 0, 1),
                                          nrow = 7, ncol = 7, 
                                          byrow = TRUE);
                              PPP <- array(0, dim = c(7,7,N));
                              PPP[,,1] <- P;
                              for (n in 2:N) { PPP[,,n] <- PPP[,,n-1] %*% P; } 
                              PPP }

#Calculate probability for N = 100 for equiprobable outcomes
N <- 100;
a <- 1/4;
t <- 1/4;
c <- 1/4;
g <- 1/4;
PROB(N,a,t,c,g)[1,7,N];

[1] 0.01732435

Как вы можете видеть из этого расчета, вероятность получения подстроки в бросков с равновероятными результатами составляет . Это всего лишь один пример, использующий конкретную подстроку и заданное количество испытаний, но его можно варьировать для получения вероятностей относительно других подстрок, представляющих интерес. $AAAAAA$ $n=100$ $0.01732435$

Бен - Восстановить Монику
источник

Вероятность нахождения конкретной последовательности пар оснований

Ответы: