Сравнение алгоритмов выравнивания
Для выполнения практикума были выбраны случайные последовательности белков, которые изучались в практикуме 11, из Swiss-Prot. Для сравнения выравниваний использовалась программа MACHO Виталия Гагарочкина, Всеволода Масленникова и Даниила Нагорного.
1. Сравнение MAFFT и Muscle
Таблица 1. Совпадающие блоки выравниваний MAFFT и Muscle
| Блок | MAFFT | Muscle | Длина блока |
| 1 | 92–145 | 87–140 | 54 |
| 2 | 175–178 | 170–173 | 4 |
| 3 | 271–289 | 260–278 | 19 |
| 4 | 296–344 | 285–333 | 49 |
| 5 | 346–347 | 335–336 | 2 |
| 6 | 368–599 | 350–581 | 232 |
Длина выравнивания MAFFT: 599
Длина выравнивания Muscle: 581
Совпадающих колонок: 360
% совпадающих колонок выравнивания MAFFT: 60.10%
% совпадающих колонок выравнивания Muscle: 61.96%
Всего блоков: 6
Максимальная длина блока: 232
2. Сравнение MAFFT и Probcons
Таблица 2. Совпадающие блоки выравниваний MAFFT и Probcons
| Блок | MAFFT | Probcons | Длина блока |
| 1 | 92–143 | 100–151 | 52 |
| 2 | 146–169 | 154–177 | 24 |
| 3 | 175–177 | 183–185 | 3 |
| 4 | 179–182 | 187–190 | 4 |
| 5 | 184–214 | 192–222 | 31 |
| 6 | 223–227 | 228–232 | 5 |
| 7 | 229–230 | 234–235 | 2 |
| 8 | 232–248 | 237–253 | 17 |
| 9 | 254–259 | 259–264 | 6 |
| 10 | 261–275 | 266–280 | 15 |
| 11 | 277–290 | 282–295 | 14 |
| 12 | 296–348 | 301–353 | 53 |
| 13 | 367–597 | 366–596 | 231 |
Длина выравнивания MAFFT: 599
Длина выравнивания Probcons: 598
Совпадающих колонок: 457
% совпадающих колонок выравнивания MAFFT: 76.29%
% совпадающих колонок выравнивания Probcons: 76.42%
Всего блоков: 13
Максимальная длина блока: 231
Выравнивания MAFFT и Probcons сходны между собой сильнее, чем MAFFT и Muscle: совпадает около 76% колонок против 60–62%. Во всех трёх выравниваниях одинаково выровнен длинный участок в конце (блоки 6 и 13 длиной 232 и 231 колонка), а основные расхождения приходятся на начало выравнивания: первые 91 колонка MAFFT не совпадают ни с одним из двух других выравниваний. У MAFFT и Probcons совпадений больше за счёт средней части (колонки 146–290 MAFFT), где MAFFT и Muscle почти не совпадают, хотя она и разбита на много коротких блоков.
Проект Jalview
Выравнивания: Mafft.fasta,
Muscle.fasta,
Probcons.fasta
Выдача MACHO: MM.txt (MAFFT и Muscle),
MP.txt (MAFFT и Probcons)
3. Сравнение множественного и структурного выравнивания
Для сравнения были взяты A-цепи трёх тропомиозинов с известной пространственной структурой: 3U59 (Gallus gallus), 7BJG (Drosophila melanogaster) и 8PV0 (Schizosaccharomyces pombe). Их множественное выравнивание (task3.fasta) сравнивалось со структурным выравниванием тех же белков (task3true.fa).
Таблица 3. Совпадающие блоки множественного и структурного выравниваний
| Блок | Множественное выравнивание | Структурное выравнивание | Длина блока |
| 1 | 32–52 | 35–55 | 21 |
| 2 | 170–172 | 162–164 | 3 |
Длина множественного выравнивания: 172
Длина структурного выравнивания: 164
Совпадающих колонок: 24
% совпадающих колонок множественного выравнивания: 13.95%
% совпадающих колонок структурного выравнивания: 14.63%
Всего блоков: 2
Максимальная длина блока: 21
Выравнивания практически не совпадают: все 24 «совпадающие» колонки содержат только остатки 8PV0, а колонок, где хотя бы два белка выровнены одинаково, нет ни одной. Причина в том, что тропомиозин — повторяющаяся α-спиральная суперспираль: MSA сдвигает последовательности на целое число гептад (сдвиги −56, −35, −21), а структурное совмещение — на целое число витков спирали (−18, −4), поэтому для таких белков оба метода не дают однозначного соответствия остатков.
Выравнивания: task3.fasta (множественное),
task3true.fa (структурное)
Выдача MACHO: TT.txt
4. Описание MAGUS
Основа алгоритма
Многие методы множественного выравнивания плохо справляются с большими наборами последовательностей. Для решения этой проблемы был разработан MAGUS [1].
MAGUS опирается на общую схему более раннего алгоритма PASTA [2]. Сначала набор последовательностей делится на подгруппы, каждая из которых выравнивается отдельно с помощью MAFFT-linsi [3]. Затем полученные выравнивания объединяются с помощью кластеризации графа (Graph Clustering Merger, GCM) [4].
Улучшения MAGUS
Чтобы повысить скорость и точность, в MAGUS введено несколько улучшений. Одно из них — рекурсия. Если после разбиения подгруппа содержит больше последовательностей, чем заданный порог, к ней снова применяется MAGUS. Если меньше, она выравнивается с помощью MAFFT.
Направляющее дерево (guide tree) можно построить четырьмя способами:
Как в PASTA: 300 случайно выбранных последовательностей выравниваются с помощью MAFFT, остальные добавляются к выравниванию с помощью HMMER, после чего по выравниванию строится дерево в FastTree.
Методом построения начального дерева из Clustal Omega.
Методом построения начального дерева MAFFT PartTree.
Методом минимальной эволюции в FastTree.
Кроме того, для ускорения работы MAGUS использует параллельные вычисления и сжатие данных.
Список литературы
[1] Smirnov V, Warnow T. MAGUS: Multiple sequence Alignment using Graph clUStering. Bioinformatics. 2021;37(12):1666–1672. doi: 10.1093/bioinformatics/btaa992
[2] Mirarab S, Nguyen N, Guo S, Wang LS, Kim J, Warnow T. PASTA: ultra-large multiple sequence alignment for nucleotide and amino-acid sequences. Journal of Computational Biology. 2015;22(5):377–386. doi: 10.1089/cmb.2014.0156
[3] Katoh K, Kuma K, Toh H, Miyata T. MAFFT version 5: improvement in accuracy of multiple sequence alignment. Nucleic Acids Res. 2005;33(2):511–518. doi: 10.1093/nar/gki198
[4] Репозиторий MAGUS: github.com/vlasmirnov/MAGUS