Пробалайн

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

Алгоритм

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

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

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

• функция сходства $\sigma (x,y)$ (например , ПАМ , БЛОСУМ ,...)
• Штраф за аффинный разрыв: $g(k)=\alpha +\beta k$

Оценка $S(a)$ трассы a определяется как:

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

Теперь взвешенная оценка Больцмана трассы a равна:

$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}}$

Где $T$ является коэффициентом масштабирования.

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

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

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

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

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

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

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

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

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

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

Рекурсия

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

• $Z_{i,j}^{M}=Z_{i-1,j-1}\cdot e^{\frac {\sigma (x_{i},y_{j})}{T}}$
• $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}}$
• $Z_{i,j}^{I}$ аналогично

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

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

$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|}}}$

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

См. также

• ПробКонс
• Множественное выравнивание последовательностей

Внешние ссылки

• Веб-сервис Probalign