ПробКонс

ProbCons — это вероятностная система множественного выравнивания аминокислотных последовательностей с открытым исходным кодом, основанная на вероятностной согласованности. Это одна из наиболее эффективных программ выравнивания множественных последовательностей белков , поскольку она неоднократно демонстрировала статистически значимое преимущество в точности по сравнению с аналогичными инструментами, включая Clustal и MAFFT .

Алгоритм

Ниже описывается базовая схема алгоритма ProbCons.

Шаг 1: Надежность выравнивающей кромки

Для каждой пары последовательностей вычислите вероятность того, что буквы $x_{i}$ и $y_{i}$ в паре $a^{*}$ выравнивание, созданное моделью.

${\begin{aligned}P(x_{i}\sim y_{i}|x,y)&{\stackrel {def}{=}}Pr[x_{i}\sim y_{i}{\text{ in some a }}|x,y]\\&=\sum _{{\text{alignment a with }}x_{i}-y_{i}}Pr[a|x,y]\\&=\sum _{\text{alignment a}}\mathbf {1} \{x_{i}-y_{i}\in a\}Pr[a|x,y]\end{aligned}}$

(Где $\mathbf {1} \{x_{i}\sim y_{i}\in a\}$ равен 1, если $x_{i}$ и $y_{i}$ находятся в выравнивании и 0 в противном случае.)

Шаг 2. Максимальная ожидаемая точность

Точность выравнивания $a^{*}$ относительно другого расклада $a$ определяется как количество общих выровненных пар, деленное на длину более короткой последовательности.

Рассчитайте ожидаемую точность каждой последовательности:

${\begin{aligned}E_{Pr[a|x,y]}(acc(a^{*},a))&=\sum _{a}Pr[a|x,y]acc(a^{*},a)\\&={\frac {1}{min(|x|,|y|)}}\cdot \sum _{a}\mathbf {1} \{x_{i}\sim y_{i}\in a\}Pr[a|x,y]\\&={\frac {1}{min(|x|,|y|)}}\cdot \sum _{x_{i}-y_{i}}P(x_{i}\sim y_{j}|x,y)\end{aligned}}$

Это дает выравнивание с максимальной ожидаемой точностью (MEA):

$E(x,y)=\arg \max _{a^{*}}\;E_{Pr[a|x,y]}(acc(a^{*},a))$

Шаг 3: Преобразование вероятностной согласованности

Все пары последовательностей x,y из множества всех последовательностей ${\mathcal {S}}$ теперь переоцениваются с использованием всех промежуточных последовательностей z:

$P'(x_{i}-y_{i}|x,y)={\frac {1}{|{\mathcal {S}}|}}\sum _{z}\sum _{1\leq k\leq |z|}P(x_{i}\sim z_{i}|x,z)\cdot P(z_{i}\sim y_{i}|z,y)$

Этот шаг можно повторять.

Шаг 4: Расчет направляющего дерева

Постройте направляющее дерево с помощью иерархической кластеризации, используя оценку MEA в качестве оценки сходства последовательностей. Сходство кластера определяется с использованием средневзвешенного значения по сходству парных последовательностей.

Шаг 5. Вычислите MSA

Наконец, вычислите MSA, используя прогрессивное выравнивание или итеративное выравнивание.

См. также

• Программное обеспечение для выравнивания последовательностей
• Кластал
• МЫШЦЫ
• АМАП
• Т-Кофе
• Пробалайн

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

• Официальный сайт