Probalign

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

Алгоритм [ править ]

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

Оценка соответствия [ править ]

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

• функция подобия (например, PAM , BLOSUM , ...)${\ Displaystyle \ sigma (х, у)}$
• Штраф за аффинный пробел: ${\ Displaystyle г (К) = \ альфа + \ бета к}$

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

${\ displaystyle S (a) = \ sum _ {x_ {i} -y_ {j} \ in a} \ sigma (x_ {i}, y_ {j}) + {\ text {стоимость разрыва}}}$

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

${\ displaystyle e ^ {\ frac {S (a)} {T}} = e ^ {\ frac {\ sum _ {x_ {i} -y_ {j} \ in a} \ sigma (x_ {i}, y_ {j}) + {\ text {стоимость разрыва}}} {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
• Выравнивание нескольких последовательностей

Ссылки [ править ]

Внешние ссылки [ править ]

• Probalign Webservice