Задача построения множественного выравнивания. Последовательности в Fasta формате (вход) >sw|P04252|BAHG-VITST Bacterial hemoglobin. MLDQQTINIIKATVPVLKEHGVTITTTFYKNLF. - презентация

1 Задача построения множественного выравнивания

2 Последовательности в Fasta формате (вход) >sw|P04252|BAHG-VITST Bacterial hemoglobin. MLDQQTINIIKATVPVLKEHGVTITTTFYKNLF >sw|Q8UUR3|CYGB1-DANRE Cytoglobin-1. MEGDGGVQLTQSPDSLTEEDVCVIQDTWKPVYAERDNA GVAVLVRFFTNFPSAKQ >sw|Q575T0|CYGB1-ORYLA Cytoglobin-1. MERKQGEVDHLERSRPLTDKERVMIQDSWAKVYQNCDD AGVAILVRLFVNFPSSKQY >sw|Q575S8|CYGB2-DANRE Cytoglobin-2. MEKEREDEETEGRERPEPLTDVERGIIKDTWARVYASC EDVGVTILIRFFVNFPSAKQY

3 Выравнивание (выход) MLDQQTINIIKAT-VPVLKEH---GVTITTTFYKNL------F ---MEGDGGVQLTQSPDSLTEEDVCVIQDTWKPVYAERDNAGVAVLVRFFTNFPSAKQY --MERKQGEVDHLERSRPLTDKERVMIQDSWAKVYQNCDDAGVAILVRLFVNFPSSKQY MEKEREDEETEGRERPEPLTDVERGIIKDTWARVYASCEDVGVTILIRFFVNFPSAKQY В последовательности вставляются специальные пробельные символы «indel» Цель минимизировать число пробелов, при максимизации числа «одинаковых» символов в столбце. По выравниваниям исследуется эволюция геномов и протеомов.

4 Некоторые известные алгоритмы множественного выравнивания Последовательные MAFFT T-COFFE ClustalW MUSCLE Dialign Параллельные (реализация для кластера) ClustalW-MPI Pdialign MUSCLE (Модификация для кластеров ВМК МГУ)

5 Параллельная реализация MUSCLE В исходном алгоритме модифицирована стадия стадия построения промежуточных выравниваний по бинарному кластерному дереву Параллелизм за счёт параллельного обхода дерева от листьев к корню. Программа реализована с использованием языка «PARUS» ( Язык описывает параллельную программу как граф потока данных.

6 Эффективность алгоритма исследована на выравнивании последовательностей LTR (Long Terminal Repeat) класса 5 в геноме человека, класс 5 (LTR5) содержит приблизительно 1500 последовательностей по 1200 нуклеотидов. 13 семейств 1011 аминокислотных последовательностей приблизительно по 300 аминокислотных остатков каждая. Максимально удалось использовать 500 процессоров машины МВС-100к.

7 Результаты запуска на Чебышев-МГУ (последовательности LTR5)

8 Результаты запуска на Чебышев-МГУ семейства белков

9 Интернет-сервис создан для повышения доступности использования многопроцессорной техники при решении задачи построения множественного выравнивания. В текущий момент поддерживает Параллельный MUSCLE и ClustalW- MPI. Веб-интерфейс

10 Граф изменения статуса задачи поставленной через веб- интерфейс ready задача готова к запуску на кластере submited запущена на кластере finished корректно завершена можно скачать ответ

11 Биоинформатические HPC ресурсы с факультета ВМК

12 Наличие программного обеспечения на вычислительных кластерах МГУ