MUSCLE (программное обеспечение для выравнивания)
| Оригинальный автор(ы) | Роберт С. Эдгар |
|---|---|
| Разработчик(и) | диск5 |
| Первоначальный выпуск | 2004 г |
| Стабильная версия | 3.8.31 / 18 августа 2016 г |
| Репозиторий | github |
| Операционная система | Linux , MacOS , Windows |
| Платформа | ИА-32 , x86-64 |
| Доступно в | Английский |
| Тип | Множественное выравнивание последовательностей |
| Лицензия | Общественное достояние |
| Веб-сайт | диск5 |
Сравнение множественных последовательностей с помощью логарифмического ожидания ( MUSCLE это компьютерное программное обеспечение для множественного выравнивания белковых ) — и нуклеотидных последовательностей. Он лицензирован как общественное достояние . Этот метод был опубликован Робертом К. Эдгаром в двух статьях в 2004 году. В первой статье, опубликованной в журнале Nucleic Acids Research , был представлен алгоритм выравнивания последовательностей. [1] Вторая статья, опубликованная в BMC Bioinformatics , представила больше технических подробностей. [2]
Алгоритм [ править ]
Алгоритм MUSCLE работает в три этапа: черновой прогрессивный , улучшенный прогрессивный и этап уточнения .
Этап 1: Черновой прогрессивный вариант [ править ]
На этом первом этапе алгоритм производит множественное выравнивание, отдавая предпочтение скорости, а не точности. Этот шаг начинается с вычисления расстояния k-меров для каждой пары входных последовательностей для создания матрицы расстояний . UPGMA кластеризует матрицу расстояний для создания двоичного дерева . На основе этого дерева строится постепенное выравнивание, начиная с создания профилей для каждого листа дерева. Для каждого узла в дереве создается попарное выравнивание двух дочерних профилей, в результате чего создается новый профиль, который будет назначен этому узлу. Это продолжается до тех пор, пока не произойдет множественное выравнивание всех входных последовательностей в корне дерева. [1]
Этап 2: Улучшенный прогрессивный режим [ править ]
На этом этапе основное внимание уделяется получению более оптимального дерева путем расчета расстояния Кимуры для каждой пары входных последовательностей с использованием множественного выравнивания последовательностей, полученного на первом этапе, и создания второй матрицы расстояний. UPGMA кластеризует эту матрицу расстояний для получения второго двоичного дерева. Прогрессивное выравнивание выполняется для получения выравнивания множественных последовательностей, как на этапе 1, но оно оптимизируется только путем вычисления выравниваний в поддеревьях, порядок ветвления которых изменился по сравнению с первым двоичным деревом, что приводит к более точному выравниванию. [1]
Этап 3: Доработка [ править ]
На этом заключительном этапе из второго дерева выбирается ребро, при этом ребра посещаются на уменьшающемся расстоянии от корня. Выбранное ребро удаляется, дерево разделяется на два поддерева. Затем для каждого поддерева вычисляется профиль множественного выравнивания. Новое выравнивание множественных последовательностей производится путем повторного выравнивания профилей поддерева. Если показатель SP улучшается, новое мировоззрение сохраняется, в противном случае оно отбрасывается. Процесс удаления ребра и выравнивания повторяется до тех пор, пока не произойдет сходимость или не будет достигнут заданный пользователем предел. [1]
и сравнение Сложность
На первых двух этапах алгоритма временная сложность составляет O( N 2 Л + НЛ 2 ) , пространственная сложность O ( N 2 + НЛ + Л 2 ) . На этапе уточнения к временной сложности добавляется еще одно слагаемое, O( N 3 Л ) . [1] MUSCLE часто используется в качестве замены Clustal , поскольку он обычно (но не всегда) обеспечивает лучшее выравнивание последовательностей, в зависимости от выбранных опций. значительно быстрее, чем Clustal, особенно для более крупных выравниваний. [1] [2]
Блок-схема алгоритма [ править ]
Интеграция [ править ]
MUSCLE интегрирован в программное обеспечение Lasergene компании DNASTAR , Geneious и MacVector и доступен в Sequencher , MEGA и UGENE в качестве плагина . MUSCLE также доступен в виде веб-сервиса через Европейскую лабораторию молекулярной биологии (EMBL) и Европейский институт биоинформатики (EBI). [3] По состоянию на сентябрь 2016 года две статьи, описывающие MUSCLE, в общей сложности цитировались более 19 000 раз. [4]
См. также [ править ]
- Программное обеспечение для выравнивания последовательностей
- ДНКСТАР
- Кластал
- ПробКонс
- АМАП
- Т-КОФЕ
- МАФФТ
Ссылки [ править ]
- ^ Jump up to: Перейти обратно: а б с д и ж Эдгар Р.К. (2004). «MUSCLE: множественное выравнивание последовательностей с высокой точностью и высокой пропускной способностью» . Исследования нуклеиновых кислот . 32 (5): 1792–97. дои : 10.1093/nar/gkh340 . ПМК 390337 . ПМИД 15034147 .
- ^ Jump up to: Перейти обратно: а б Эдгар Р.К. (2004). «MUSCLE: метод множественного выравнивания последовательностей с уменьшенной сложностью времени и пространства» . БМК Биоинформатика . 5 (1): 113. дои : 10.1186/1471-2105-5-113 . ПМК 517706 . ПМИД 15318951 .
- ^ «MUSCLE <Выравнивание множественных последовательностей <EMBL-EBI» . Архивировано из оригинала 18 января 2015 года . Проверено 1 сентября 2014 г.
- ^ «Роберт С. Эдгар — цитаты из Google Scholar» . Архивировано из оригинала 24 сентября 2016 года . Проверено 1 сентября 2016 г.
