Python 3.10-скрипт для сравнительного анализа двух выравниваний написан и протестирован Георгием Малаховым в соавторстве со мной, Яковом Коробицыным и Артёмом Тюкаевым. Я участвовал в разработке идеи алгоритма, и в его тестировании.
Как входные данные программа принимает пути для двух выравнивний, каждое в формате .fasta или .fa
Я участвовал в разработке идеи алгоритма, и в его тестировании.
Тестирование этого скрипта осуществлено на нескольких парах выравниваний. В каждой выравнивания сделаны с применением различных алгоритмов. Приведу пример одного такого теста.
Выровнены аминокислотные последовательности аполипопротеина Е представителей различных отрядов млекопитающих. Для двух выравниваний использованы алгоритмы MUSCLE и CLUSTALO. Скачать Jalview-проект
В результате работы скрипта пользователь получает два столбца числовых промежутков, соответствующих позициям двух выравниваний. В этой таблице горизонтально сопоставлены совпадающие участки.
Output скрипта для исследуемой пары выравниваний; первый набор данных — выравнивание MUSCLE, второй — CLUSTALO.
F1-L1 F2-L2
1-19 1-19
52-221 52-221
227-227 227-227
233-322 233-322
В этом примере позиции 52-221 в первом выравнивании (MUSCLE) соответствуют позициям 52-221 второго (CLUSTALO). По свидетельству программы, символы с этими координатами совпадают по индексам.
И это действительно так. В доказательство приведу скриншот:
Заметное различие обнаруживается в позициях 30-40 обоих выравниваний. Видимо, всё дело в повторяющихся P, E, L.
Для выравнивания взяты последовательности белков из предыдущего задания, за исключением P0DUZ6 (Onychomys torridus), т. к. мне не удалось нигде найти PDB-файл для этого белка.
Выравнивание осуществлено с помощью инструмента align в Pymol. Для меньшей загруженности изображения на иллюстрации ниже показана лишь часть: выравненные первые 50 аминокислотных остатков в каждом белке.
Бросается в глаза структурная гетероморфность этого участка у разных млекопитающих.
Источник — Edgar, 2004
Расшифровка аббревиатуры: множественное сравнение последовательностей с помощью логарифмического ожидания (MUltiple Sequence Comparison by Log-Expectation).
Схематично алгоритм показан на рисунке ниже.
Концептуально же он работает следующим образом:
1) Вычисление матрицы расстояний между попарно между k-мерами последовательностей;
2) Разбиение массива последовательностей по кластерам и построение дерева по полученной матрице с помощью UPGMA;
3) Построение прогрессивных (progressive) выравниваний с помощью алгоритма Нидлмана-Вунша;
4) Вычисление матрицы расстояний между каждыми двумя последовательностями в выравниваниях из предыдущего пункта. За основу берётся модель Kimura, 1983;
5) Вновь построение прогрессивного выравнивания по полученной в предыдущем пункте матрицы.
Уже на стадии 5 алгоритм можно завершать, т. к. пользователь к этому моменту уже получает искомое множественное выравнивание. Однако дальнейшие действия позволяют повысить вероятность получить наиболее корректное выравнивание из возможных.
6) Построение дерева по последнему выравниванию. Затем последовательно убирается по ветке от этого дерева, начиная с наиболее удалённой от корня;
7) Сравниваются выравнивания с удалением ветки и без него. Сохраняется то, SP score которого больше (см. рис. 3).
SP score (от англ. «sum of pair») - сумма значений оценок лучших выравниваний (alignment score) для каждой пары последовательностей в массиве.
1. Edgar, R. C. (2004). MUSCLE: multiple sequence alignment with high accuracy and high throughput. Nucleic Acids Research, 32(5), 1792–1797.
2. Kimura M. (1983). The Neutral Theory of Molecular Evolution. Cambridge University Press.