Probalign - Probalign

Probalign это инструмент для выравнивания последовательностей, который вычисляет максимальное ожидаемая точность выравнивание с использованием апостериорных вероятностей статистической суммы.^[1] Вероятности пары оснований оцениваются с использованием оценки, аналогичной оценке Распределение Больцмана. Статистическая сумма вычисляется с использованием динамическое программирование подход.

Алгоритм

Ниже описан алгоритм, используемый probalign для определения вероятностей пары оснований.^[2]

Оценка соответствия

Чтобы оценить выравнивание двух последовательностей, необходимы две вещи:

• функция подобия ${\displaystyle \sigma (x,y)}$ (например. PAM, BLOSUM,...)
• штраф за аффинный пробел: ${\displaystyle g(k)=\alpha +\beta k}$

Очки ${\displaystyle S(a)}$ трассы a определяется как:

${\displaystyle S(a)=\sum _{x_{i}-y_{j}\in a}\sigma (x_{i},y_{j})+{\text{gap cost}}}$

Теперь взвешенный балл по Больцману для раскладки a равен:

${\displaystyle e^{\frac {S(a)}{T}}=e^{\frac {\sum _{x_{i}-y_{j}\in a}\sigma (x_{i},y_{j})+{\text{gap cost}}}{T}}=\left(\prod _{x_{i}-y_{i}\in a}e^{\frac {\sigma (x_{i},y_{j})}{T}}\right)\cdot e^{\frac {gapcost}{T}}}$

Где ${\displaystyle T}$ - коэффициент масштабирования.

Вероятность совмещения в предположении распределения Больцмана определяется выражением

${\displaystyle Pr[a|x,y]={\frac {e^{\frac {S(a)}{T}}}{Z}}}$

Где ${\displaystyle Z}$ - статистическая сумма, т.е. сумма весов Больцмана всех выравниваний.

Динамическое программирование

Позволять ${\displaystyle Z_{i,j}}$ обозначают статистическую сумму префиксов ${\displaystyle x_{0},x_{1},...,x_{i}}$ и ${\displaystyle y_{0},y_{1},...,y_{j}}$. Рассмотрены три разных случая:

1. ${\displaystyle Z_{i,j}^{M}:}$ функция распределения всех выравниваний двух префиксов, заканчивающихся совпадением.
2. ${\displaystyle Z_{i,j}^{I}:}$ функция распределения всех выравниваний двух префиксов, заканчивающихся вставкой ${\displaystyle (-,y_{j})}$.
3. ${\displaystyle Z_{i,j}^{D}:}$ функция распределения всех выравниваний двух префиксов, заканчивающихся удалением ${\displaystyle (x_{i},-)}$.

Тогда у нас есть: ${\displaystyle Z_{i,j}=Z_{i,j}^{M}+Z_{i,j}^{D}+Z_{i,j}^{I}}$

Инициализация

Матрицы инициализируются следующим образом:

• ${\displaystyle Z_{0,j}^{M}=Z_{i,0}^{M}=0}$
• ${\displaystyle Z_{0,0}^{M}=1}$
• ${\displaystyle Z_{0,j}^{D}=0}$
• ${\displaystyle Z_{i,0}^{I}=0}$

Рекурсия

Статистическая функция для выравнивания двух последовательностей ${\displaystyle x}$ и ${\displaystyle y}$ дан кем-то ${\displaystyle Z_{|x|,|y|}}$, который можно вычислить рекурсивно:

• ${\displaystyle Z_{i,j}^{M}=Z_{i-1,j-1}\cdot e^{\frac {\sigma (x_{i},y_{j})}{T}}}$
• ${\displaystyle Z_{i,j}^{D}=Z_{i-1,j}^{D}\cdot e^{\frac {\beta }{T}}+Z_{i-1,j}^{M}\cdot e^{\frac {g(1)}{T}}+Z_{i-1,j}^{I}\cdot e^{\frac {g(1)}{T}}}$
• ${\displaystyle Z_{i,j}^{I}}$ аналогично

Вероятность пары оснований

Наконец, вероятность того, что позиции ${\displaystyle x_{i}}$ и ${\displaystyle y_{j}}$ образуют базовую пару:

${\displaystyle P(x_{i}-y_{j}|x,y)={\frac {Z_{i-1,j-1}\cdot e^{\frac {\sigma (x_{i},y_{j})}{T}}\cdot Z'_{i',j'}}{Z_{|x|,|y|}}}}$

${\displaystyle Z',i',j'}$ соответствующие значения для пересчитанного ${\displaystyle Z}$ с перевернутыми строками пары оснований.

Смотрите также

• ProbCons
• Выравнивание нескольких последовательностей

Рекомендации

1. У. Рошан и Д. Р. Ливси, Probalign: множественное выравнивание последовательностей с использованием апостериорных вероятностей функции распределения, Bioinformatics, 22 (22): 2715-21, 2006 (PDF )
2. Лекция «Биоинформатика II» в Университете Фрайбурга.

внешняя ссылка

• Probalign Webservice