Probalign - Probalign - Wikipedia

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

Алгоритм

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

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

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

  • функция подобия (например. PAM, BLOSUM,...)
  • штраф за аффинный пробел:

Очки трассы a определяется как:

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

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

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

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

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

Позволять обозначают статистическую сумму префиксов и . Рассмотрены три разных случая:

  1. функция распределения всех выравниваний двух префиксов, заканчивающихся совпадением.
  2. функция распределения всех выравниваний двух префиксов, заканчивающихся вставкой .
  3. функция распределения всех выравниваний двух префиксов, заканчивающихся удалением .

Тогда у нас есть:

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

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

Рекурсия

Статистическая функция для выравнивания двух последовательностей и дан кем-то , который можно вычислить рекурсивно:

  • аналогично

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

Наконец, вероятность того, что позиции и образуют базовую пару:

соответствующие значения для пересчитанного с перевернутыми строками пары оснований.

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

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

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

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