Алгоритм обрезки деревьев Фельзенштейна

В статистической генетике алгоритм обрезки деревьев Фельзенштейна (или алгоритм очистки деревьев Фельзенштейна ), приписываемый Джозефу Фельзенштейну , представляет собой алгоритм для эффективного расчета вероятности эволюционного дерева на основе данных о последовательностях нуклеиновых кислот .

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

Подробности

Простой пример филогенетического дерева, составленный на основе произвольных данных D

Вероятность появления дерева $T$ по определению, это вероятность наблюдения определенных данных $D$ ( $D$ например, выравнивание нуклеотидных последовательностей, т.е. последовательность $n$ сайт ДНК $s$) с учетом дерева. Часто пишут: $P(D|T)$.

Вот пример эволюционного дерева на данных произвольной последовательности. $D$:

Это ключевое значение, и его часто довольно сложно вычислить. Чтобы облегчить вычисления, Фельзенштейн и его коллеги использовали несколько предположений, которые широко используются и сегодня. Основное предположение состоит в том, что мутации между участками ДНК независимы друг от друга. Это позволяет вычислить вероятность как простое произведение вероятностей. Теперь вы можете разделить данные $D$ между несколькими $D_{s}$ для каждого нуклеотидного сайта $s$ внутри $D$. Глобальная вероятность дерева будет произведением вероятностей каждого сайта:

То же дерево, но сделанное из D1, состоящего из первых участков ДНК из D.

$P(D|T)=\prod _{s=1}^{n}{P(D_{s}|T)}$

Если я повторно использую приведенный выше пример, $D_{1}$ дерево будет:

Второе предположение касается моделей эволюции последовательностей ДНК . Для расчета вероятности необходимы частоты нуклеотидов, а также вероятности перехода (при возникновении мутации вероятность перехода от одного нуклеотида к другому). Простейшей моделью является модель Джукса-Кантора , предполагающая равные частоты нуклеотидов. $\left(\pi _{A}=\pi _{G}=\pi _{C}=\pi _{T}={1 \over 4}\right)$ и равные вероятности перехода от $X$ к $Y$ ( $p_{A\rightarrow T}=p_{A\rightarrow C}=p_{A\rightarrow G}={\frac {1}{4}}(1-e^{-\mu l})$ и $p_{A\rightarrow A}=e^{-\mu l}+{\frac {1}{4}}(1-e^{-\mu l})$) и то же самое для других оснований. Здесь $\mu$ — глобальная скорость мутаций модели.

Фельзенштейн предложил еще больше разложить вычисления, используя «частичные правдоподобия» при вычислении $P(D_{s}|T)$. Вот как это работает.

Предположим, мы находимся на узле $k$ на дереве $T$. $k$ имеет два дочерних узла $i$ и $j$ и для каждого основания ДНК $X=\{A,T,C,G\}$ присутствовать на $k$, мы можем определить частичную вероятность $w_{k}(X)$ такой как:

$w_{k}(X)=(\sum _{Y}p_{X\rightarrow Y}\centerdot w_{i}(Y))\centerdot (\sum _{Z}p_{X\rightarrow Z}\centerdot w_{j}(Z))$

где $Y$ и $Z$ также являются основаниями ДНК. $p_{X\rightarrow Y}$- вероятность перехода от нуклеотида $X$ в нуклеотид $Y$ (то же самое для $p_{X\rightarrow Z}$). $w_{i}(Y)$ это частичная вероятность дочернего узла $i$, оцененный по нуклеотиду $Y$ (то же самое для $w_{j}(Z)$).

Используя эту формулу, нужно начинать с кончиков дерева. $T$, затем двигаемся к корню и вычисляем частичные вероятности каждого необходимого узла на пути (4 частичных правдоподобия на узел). После завершения поиска в корне дерева вероятность дерева (для этого конкретного сайта) равна сумме частичных правдоподобий корня, умноженных на соответствующую частоту нуклеотидов.

$P(D_{s}|T)=\sum _{X}p_{X}\centerdot w_{r}(X)$

После этого для каждого сайта $s$, наконец, можно получить вероятность глобального эволюционного дерева, умножив каждую «субправдоподобие».