Пробалин - Википедия - Probalign

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

Алгоритм

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

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

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

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

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

${ 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}}$ . Рассмотрены три разных случая:

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

Тогда у нас есть: ${ 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_ {я, 0} ^ {I} = 0}$

Рекурсия

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

${ Displaystyle Z_ {я, j} ^ {M} = Z_ {i-1, j-1} cdot e ^ { frac { sigma (x_ {i}, y_ {j})} {T}} }$
${ Displaystyle Z_ {я, 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}$ с перевернутыми строками пары оснований.

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

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

Probalign Webservice

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

[2] Лекция «Биоинформатика II» в Университете Фрайбурга.

[1]

[2]