МАФФТ

МАФФТ
Разработчик(и)	Казутака Като
Стабильная версия	7.475 / 23 ноября 2020 г .; 3 года назад
Написано в	С
Операционная система	UNIX , Linux , Mac , MS-Windows
Тип	Инструмент биоинформатики
Лицензия	БСД
Веб-сайт	маффт .cbrc .jp /выравнивание /программное обеспечение /

В биоинформатике создания MAFFT ( множественное выравнивание множественных с использованием быстрого преобразования Фурье ) . это программа, используемая для выравниваний аминокислотных — или нуклеотидных последовательностей Опубликованная в 2002 году первая версия MAFFT использовала алгоритм, основанный на прогрессивном выравнивании , в котором последовательности кластеризовались с помощью быстрого преобразования Фурье . ^[2] В последующих версиях MAFFT были добавлены другие алгоритмы и режимы работы. ^[3] включая опции для более быстрого выравнивания большого количества последовательностей, ^[4] более высокая точность выравнивания, ^[5] выравнивание некодирующих последовательностей РНК, ^[6] и добавление новых последовательностей к существующим выравниваниям. ^[7]

История

Существует множество вариантов программного обеспечения MAFFT, некоторые из которых перечислены ниже:

MAFFT : Первая версия MAFFT, созданная Казутакой Като в 2002 году, использовала алгоритм, основанный на прогрессивном выравнивании , в котором последовательности группировались с помощью быстрого преобразования Фурье . ^[2]
MAFFT v5 : второе поколение программного обеспечения MAFFT было выпущено в 2005 году и представляло собой переписывание исходного программного обеспечения MAFFT. ^[3] В этом поколении появилась упрощенная система оценки, которая хорошо работает для сокращения времени процессора и повышения точности выравнивания даже для последовательностей, имеющих большие вставки или расширения, а также для отдаленно связанных последовательностей одинаковой длины. ^[2]
MAFFT v6 : третье поколение, выпущенное в 2006 году, снова усовершенствовало предыдущие версии. ^[3] Он реализовал выравнивание между группами, направляющие деревья, которые имели приблизительный, но более быстрый алгоритм построения дерева O ( N log N ), а также сделал версию применимой к более крупным наборам данных с ~ 50 000 последовательностями.
MAFFT v7 : четвертое поколение, выпущенное в 2012 году, существенно улучшило скорость и точность MAFFT. ^[3]
MAFFT v7.511 : самая последняя версия MAFFT, выпущенная в декабре 2022 года, представляет собой усовершенствованную версию MAFFT v7 с различными исправлениями ошибок. Одним из наиболее заметных является капитальный ремонт --merge опция, которая теперь включает в себя возможность итеративного уточнения, создание одного MSA из нескольких суб-MSA, а также комбинацию --merge и --seed. Также было внесено несколько незначительных улучшений в скорость и точность MAFFT v7.

Алгоритм

Алгоритм MAFFT работает следующим образом: попарное выравнивание, расчет расстояния, построение направляющего дерева, прогрессивное выравнивание, итеративное уточнение. ^[8]

Попарное выравнивание : этот шаг используется для определения схожих областей между введенными последовательностями. Алгоритм начинается с использования введенных последовательностей и выполнения попарного выравнивания по всем последовательностям. Временная сложность этого шага равна O(L^2), где L — последовательность. ^[9]

Матрица расстояний : с использованием рассчитанных парных выравниваний выполняется расчет матрицы расстояний для оценки различий между выравниваниями на основе их оценок выравнивания. ^[9] Шаг расчета расстояния помогает организовать последовательности на основе их сходства. Временная сложность матрицы расстояний равна O(N^2L^2). ^[9] где N — количество последовательностей, а L — длина последовательности. Эта временная сложность связана с тем, что вычисление расстояния между парами последовательностей требует сравнения каждой позиции каждой последовательности.

Дерево направляющих : с использованием матрицы расстояний строится направляющее дерево, в котором существует иерархическое представление кластеров (каждый узел является кластером), а включенные ветки представляют собой расстояние между кластерами. О(Н^2Л) ^[10] – временная сложность построения направляющего дерева, где N – количество последовательностей.

Прогрессивное выравнивание дерева направляющих. : использование прогрессивного выравнивания ^[9] выполняется от листьев к корню. Алгоритм использует введенные последовательности и выравнивает дочерние узлы для расчета консенсусного выравнивания для родительского узла. Этот шаг выполняется до тех пор, пока не будет пройдено все дерево и получено окончательное выравнивание множественных последовательностей. Временная сложность метода прогрессивного выравнивания составляет O(N^2L) + O(NL^2). ^[10] Это связано с тем, что первый член соответствует расчету направляющего дерева, указанному ранее, а второй член соответствует выравниванию групп между группами.

Итеративное выравнивание : шаг итеративного уточнения повторяет весь процесс с корректировкой положений промежутков и вставок для повышения точности выравнивания. ^[9] Временная сложность итеративного выравнивания зависит от количества происходящих итераций. Но обычно временная сложность этого метода составляет O(N2L) + O(NL2). ^[10] где N — количество последовательностей, а L — длина последовательности.

Ввод/вывод

Веб-форма

Вход

Эта программа может принимать в качестве входных данных несколько последовательностей, которые можно ввести двумя способами:

Окно ввода последовательности

Пользователь может напрямую ввести в окно ввода три или более последовательностей в любом из следующих форматов: GCG , FASTA , EMBL (только нуклеотиды), GenBank , PIR , NBRF , PHYLIP или UniProtKB/Swiss-Prot (только белок). Важно отметить, что частично отформатированные последовательности не принимаются, и добавление возврата в конец последовательности может помочь некоторым приложениям понять ввод. Также рекомендуется избегать использования данных из текстовых процессоров, поскольку могут присутствовать скрытые/управляющие символы. ^[11]

Загрузка файла последовательности

Пользователь может загрузить файл, содержащий три или более действительных последовательностей в любом формате, упомянутом выше. Файлы текстового процессора могут давать непредсказуемые результаты из-за присутствия скрытых/управляющих символов, поэтому лучше сохранять файлы в формате Unix , чтобы избежать скрытых символов Windows . После загрузки файла его можно использовать в качестве входных данных для множественного выравнивания последовательностей. ^[11]

Текстовые файлы, сохраненные в формате DOS/Windows, имеют другие окончания строк, чем файлы, сохраненные в Unix/Linux . DOS/Windows использует комбинацию символов возврата каретки и перевода строки («\r\n») для обозначения конца строки, тогда как системы Unix/Linux используют только символ перевода строки («\n») . ^[12]

При передаче файлов между системами Windows и Unix важно учитывать эти различия, чтобы обеспечить правильный перевод концов строк. В противном случае скрытые символы возврата каретки в файлах в формате Windows могут вызвать проблемы при просмотре или редактировании в системах на базе Unix, и наоборот. ^[12]

Выход

Пользователь будет иметь возможность запросить создание множественного выравнивания последовательностей (MSA) в одном из двух доступных форматов:


Формат вывода	Описание	Аббревиатура
Пирсон/ФАСТА	Формат последовательности Pearson или FASTA	пост
КласталВ	Формат выравнивания ClustalW без нумерации оснований/остатков	кластер

Значение по умолчанию: Pearson/FASTA [fasta]

Понимание вывода ClustalW:
Символ	Определение	Значение
*	звездочка	Консервативная последовательность (идентичная)
:	толстая кишка	Консервативная мутация
.	период	Полуконсервативная мутация
( )	пустой	Неконсервативная мутация
-	бросаться	Зазор

Настройки

Существует множество настроек, влияющих на работу алгоритма MAFFT. Настройка параметров в соответствии с вашими потребностями — лучший способ получить точные и значимые результаты. Наиболее важными настройками, которые необходимо понять, являются: матрица оценок, штраф за открытие пробела и штраф за расширение пробела.

Матрица оценки: «Программы поиска сходства белковых последовательностей, такие как BLASTP, SSEARCH (UNIT 3.10) и FASTA, используют матрицы оценки, предназначенные для выявления отдаленных эволюционных связей (BLOSUM62 для BLAST, BLOSUM50 для SEARCH и FASTA). Наиболее эффективны различные матрицы оценки сходства. на разных эволюционных дистанциях «глубокие» матрицы оценки, такие как BLOSUM62 и BLOSUM50, целевые совпадения с идентичностью 20–30%, в то время как «поверхностные» матрицы оценки (например, VTML10 – VTML80) – целевые совпадения, которые имеют идентичность на 90–50%, что отражает гораздо меньшую эволюционность. изменять." ^[13] В оригинальном MAFFT уравнение подсчета очков показано ниже.

Штраф за разрыв: Штраф за разрыв — это отрицательная оценка, назначаемая за пробел в трассе. Она может быть постоянной, когда за пробел взимается фиксированная стоимость, или линейной, когда фиксированная стоимость взимается за каждый вставленный или удаленный символ. Штраф за аффинный пробел объединяет эти два показателя, взимая постоянный штраф за первый символ пробела и другой постоянный штраф за каждый вставленный или удаленный дополнительный символ. ^[14]

Штраф за расширение пробела: Штраф за расширение пробела представляет собой оценку стоимости, назначаемую для каждого дополнительного символа пробела в области пробела при выравнивании последовательности. Он используется для предотвращения образования областей с длинным разрывом. Обычно он меньше штрафа за открытие гэпа. ^[15]

Точность и результаты

MAFFT широко считается одним из наиболее точных и универсальных инструментов для множественного выравнивания последовательностей в биоинформатике . Фактически, исследования показали, что MAFFT работает исключительно хорошо по сравнению с другими популярными алгоритмами, такими как ClustalW и T-Coffee , особенно для больших наборов данных и последовательностей с высокой степенью расхождения. ^[16] Например, в исследовании, сравнивающем производительность различных алгоритмов выравнивания при увеличении длины последовательности, алгоритм MAFFT FFT-NS-2 оказался самой быстрой программой для всех протестированных размеров последовательностей. Это связано с использованием алгоритмов быстрого преобразования Фурье (БПФ), которые обеспечивают быстрое и точное выравнивание даже сильно расходящихся последовательностей. Из-за использования быстрого преобразования Фурье (БПФ) алгоритм работает либо за O(n^2), либо за O(n) в зависимости от заданного набора данных. MAFFT требует меньше времени работы ЦП, чем другие алгоритмы, имеющие одинаковую или подобную точность, особенно T-Coffee, ClustalW и Needleman-Wunsch . ^[2]

В последующих версиях MAFFT были добавлены другие алгоритмы и режимы работы, включая возможности более быстрого выравнивания большого количества последовательностей. ^[9] более высокая точность выравнивания, ^[17] выравнивание некодирующих последовательностей РНК, ^[18] и добавление новых последовательностей к существующим выравниваниям. ^[19]

MAFFT выделяется среди других популярных алгоритмов, таких как ClustalW и T-Coffee, благодаря своей высокой точности, универсальности и набору функций. Он предлагает различные методы и стратегии выравнивания, включая итерационное уточнение и подходы, основанные на согласованности, которые еще больше повышают точность и надежность выравнивания. В результате MAFFT широко признан как мощный инструмент для множественного выравнивания последовательностей и высоко оценен научным сообществом. ^[20]

См. также

Ссылки

^ Базовое программное обеспечение MAFFT распространяется по лицензии BSD , а версии для Microsoft Windows лицензируются по лицензии GNU General Public License . Некоторые дистрибутивы MAFFT содержат программное обеспечение, лицензированное по другим лицензиям https://mafft.cbrc.jp/alignment/software/
^ Jump up to: ^а ^б ^с ^д Като, Казутака; Мисава, Кадзухару; Кума, Кей-ичи; Мията, Такаши (2002). «MAFFT: новый метод быстрого выравнивания множественных последовательностей на основе быстрого преобразования Фурье» . Исследования нуклеиновых кислот . 30 (14): 3059–66. дои : 10.1093/nar/gkf436 . ПМК 135756 . ПМИД 12136088 .
^ Jump up to: ^а ^б ^с ^д «MAFFT ver.7 — программа множественного выравнивания последовательностей» . mafft.cbrc.jp . Проверено 28 апреля 2021 г.
^ Като, К; Тох, Х (2006). «PartTree: алгоритм построения приблизительного дерева из большого количества невыровненных последовательностей» . Биоинформатика . 23 (3): 372–4. doi : 10.1093/биоинформатика/btl592 . ПМИД 17118958 .
^ Като, К; Кума, К; Мията, Т; Тох, Х (2005). «Повышение точности программы множественного выравнивания последовательностей MAFFT». Геномная информатика. Международная конференция по геномной информатике . 16 (1): 22–33. ПМИД 16362903 .
^ Като, Казутака; То, Хироюки (2008). «Повышена точность выравнивания множественных нкРНК за счет включения структурной информации в структуру на основе MAFFT» . БМК Биоинформатика . 9 : 212. дои : 10.1186/1471-2105-9-212 . ПМК 2387179 . ПМИД 18439255 .
^ Като, Казутака; Фрит, Мартин С. (2012). «Добавление невыровненных последовательностей в существующее выравнивание с использованием MAFFT и LAST» . Биоинформатика . 28 (23): 3144–6. doi : 10.1093/биоинформатика/bts578 . ПМК 3516148 . ПМИД 23023983 .
^ Базовое программное обеспечение MAFFT распространяется по лицензии BSD , а версии для Microsoft Windows лицензируются по лицензии GNU General Public License . Некоторые дистрибутивы MAFFT содержат программное обеспечение, лицензированное по другим лицензиям https://mafft.cbrc.jp/alignment/software/
^ Jump up to: ^а ^б ^с ^д ^и ^ж Като, К.; Стэндли, DM (апрель 2013 г.). «Программное обеспечение для множественного выравнивания последовательностей MAFFT, версия 7: улучшения производительности и удобства использования» . Молекулярная биология и эволюция . 30 (4): 772–780. дои : 10.1093/molbev/mst010 . ПМК 3603318 . ПМИД 23329690 .
^ Jump up to: ^а ^б ^с Като, Казутака; То, Хироюки (июль 2008 г.). «Последние разработки в программе выравнивания множественных последовательностей MAFFT» . Брифинги по биоинформатике . 9 (4): 286–298. дои : 10.1093/нагрудник/bbn013 . ПМИД 18372315 .
^ Jump up to: ^а ^б «Справка и документация MAFFT — Инструменты анализа последовательностей диспетчера заданий — EMBL-EBI» . www.ebi.ac.uk. Проверено 24 апреля 2023 г.
^ Jump up to: ^а ^б «Windows и Unix-окончания строк» . www.cs.toronto.edu . Проверено 27 апреля 2023 г.
^ Пирсон, Уильям Р. (октябрь 2013 г.). «Выбор правильной матрицы оценки сходства» . Современные протоколы в биоинформатике . 43 (1): 3.5.1–3.5.9. дои : 10.1002/0471250953.bi0305s43 . ПМЦ 3848038 . ПМИД 24509512 .
^ «РОЗАЛИНДА | Глоссарий | Штраф за пробел» .
^ Кэрролл, Хайрам; Клемент, Марк; Ридж, Перри; Снелл, Куинн (октябрь 2006 г.). «Последствия штрафов за открытие и расширение разрыва» . Издания факультета .
^ Эдгар, Роберт; Бацоглу, Серафим (июнь 2006 г.). «Множественное выравнивание последовательностей». Современное мнение в области структурной биологии . 16 (3): 368–373. дои : 10.1016/j.sbi.2006.04.004 . ПМИД 16679011 .
^ Като, Казутака (28 апреля 2010 г.). «Распараллеливание программы множественного выравнивания последовательностей MAFFT» . Биоинформатика . 26 (15): 1899–1900. doi : 10.1093/биоинформатика/btq224 . ПМЦ 2905546 . ПМИД 20427515 .
^ Казунори, Ямада (4 июля 2016 г.). «Применение программы выравнивания последовательностей MAFFT к большим данным — пересмотр полезности цепных направляющих деревьев» . Биоинформатика . 32 (21): 3246–3251. doi : 10.1093/биоинформатика/btw412 . ПМК 5079479 . ПМИД 27378296 .
^ Казутака, Като (27 сентября 2012 г.). «Добавление невыровненных последовательностей в существующее выравнивание с использованием MAFFT и LAST» . Биоинформатика . 28 (23): 3144–3146. doi : 10.1093/биоинформатика/bts578 . ПМК 3516148 . ПМИД 23023983 .
^ Эдгар, RC (8 марта 2004 г.). «MUSCLE: множественное выравнивание последовательностей с высокой точностью и высокой пропускной способностью» . Исследования нуклеиновых кислот . 32 (5): 1792–1797. дои : 10.1093/nar/gkh340 . ПМК 390337 . ПМИД 15034147 .

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

Официальный сайт
Онлайн-сервер МАФФТ
Сервер MAFFT в EBI
ClustalW / MAFFT / PRRN в GenomeNet
ClustalW / TCoffee / MAFFT в MyHits, SIB

[1] Базовое программное обеспечение MAFFT распространяется по лицензии BSD , а версии для Microsoft Windows лицензируются по лицензии GNU General Public License . Некоторые дистрибутивы MAFFT содержат программное обеспечение, лицензированное по другим лицензиям https://mafft.cbrc.jp/alignment/software/

[pmid12136088-2] Jump up to: ^а ^б ^с ^д Като, Казутака; Мисава, Кадзухару; Кума, Кей-ичи; Мията, Такаши (2002). «MAFFT: новый метод быстрого выравнивания множественных последовательностей на основе быстрого преобразования Фурье» . Исследования нуклеиновых кислот . 30 (14): 3059–66. дои : 10.1093/nar/gkf436 . ПМК 135756 . ПМИД 12136088 .

[mafft-algorithms-3] Jump up to: ^а ^б ^с ^д «MAFFT ver.7 — программа множественного выравнивания последовательностей» . mafft.cbrc.jp . Проверено 28 апреля 2021 г.

[pmid17118958-4] Като, К; Тох, Х (2006). «PartTree: алгоритм построения приблизительного дерева из большого количества невыровненных последовательностей» . Биоинформатика . 23 (3): 372–4. doi : 10.1093/биоинформатика/btl592 . ПМИД 17118958 .

[pmid16362903-5] Като, К; Кума, К; Мията, Т; Тох, Х (2005). «Повышение точности программы множественного выравнивания последовательностей MAFFT». Геномная информатика. Международная конференция по геномной информатике . 16 (1): 22–33. ПМИД 16362903 .

[pmid18439255-6] Като, Казутака; То, Хироюки (2008). «Повышена точность выравнивания множественных нкРНК за счет включения структурной информации в структуру на основе MAFFT» . БМК Биоинформатика . 9 : 212. дои : 10.1186/1471-2105-9-212 . ПМК 2387179 . ПМИД 18439255 .

[pmid23023983-7] Като, Казутака; Фрит, Мартин С. (2012). «Добавление невыровненных последовательностей в существующее выравнивание с использованием MAFFT и LAST» . Биоинформатика . 28 (23): 3144–6. doi : 10.1093/биоинформатика/bts578 . ПМК 3516148 . ПМИД 23023983 .

[8] Базовое программное обеспечение MAFFT распространяется по лицензии BSD , а версии для Microsoft Windows лицензируются по лицензии GNU General Public License . Некоторые дистрибутивы MAFFT содержат программное обеспечение, лицензированное по другим лицензиям https://mafft.cbrc.jp/alignment/software/

[Katoh_&_Standley_2013-9] Jump up to: ^а ^б ^с ^д ^и ^ж Като, К.; Стэндли, DM (апрель 2013 г.). «Программное обеспечение для множественного выравнивания последовательностей MAFFT, версия 7: улучшения производительности и удобства использования» . Молекулярная биология и эволюция . 30 (4): 772–780. дои : 10.1093/molbev/mst010 . ПМК 3603318 . ПМИД 23329690 .

[Katoh_Toh_2008-10] Jump up to: ^а ^б ^с Като, Казутака; То, Хироюки (июль 2008 г.). «Последние разработки в программе выравнивания множественных последовательностей MAFFT» . Брифинги по биоинформатике . 9 (4): 286–298. дои : 10.1093/нагрудник/bbn013 . ПМИД 18372315 .

[:0-11] Jump up to: ^а ^б «Справка и документация MAFFT — Инструменты анализа последовательностей диспетчера заданий — EMBL-EBI» . www.ebi.ac.uk. Проверено 24 апреля 2023 г.

[:1-12] Jump up to: ^а ^б «Windows и Unix-окончания строк» . www.cs.toronto.edu . Проверено 27 апреля 2023 г.

[Selecting_the_Right_Similarity-Scoring_Matrix-13] Пирсон, Уильям Р. (октябрь 2013 г.). «Выбор правильной матрицы оценки сходства» . Современные протоколы в биоинформатике . 43 (1): 3.5.1–3.5.9. дои : 10.1002/0471250953.bi0305s43 . ПМЦ 3848038 . ПМИД 24509512 .

[Glossary-14] «РОЗАЛИНДА | Глоссарий | Штраф за пробел» .

[Effects_of_Gap_Open_and_Gap_Extension_Penalties-15] Кэрролл, Хайрам; Клемент, Марк; Ридж, Перри; Снелл, Куинн (октябрь 2006 г.). «Последствия штрафов за открытие и расширение разрыва» . Издания факультета .

[16] Эдгар, Роберт; Бацоглу, Серафим (июнь 2006 г.). «Множественное выравнивание последовательностей». Современное мнение в области структурной биологии . 16 (3): 368–373. дои : 10.1016/j.sbi.2006.04.004 . ПМИД 16679011 .

[17] Като, Казутака (28 апреля 2010 г.). «Распараллеливание программы множественного выравнивания последовательностей MAFFT» . Биоинформатика . 26 (15): 1899–1900. doi : 10.1093/биоинформатика/btq224 . ПМЦ 2905546 . ПМИД 20427515 .

[18] Казунори, Ямада (4 июля 2016 г.). «Применение программы выравнивания последовательностей MAFFT к большим данным — пересмотр полезности цепных направляющих деревьев» . Биоинформатика . 32 (21): 3246–3251. doi : 10.1093/биоинформатика/btw412 . ПМК 5079479 . ПМИД 27378296 .

[19] Казутака, Като (27 сентября 2012 г.). «Добавление невыровненных последовательностей в существующее выравнивание с использованием MAFFT и LAST» . Биоинформатика . 28 (23): 3144–3146. doi : 10.1093/биоинформатика/bts578 . ПМК 3516148 . ПМИД 23023983 .

[20] Эдгар, RC (8 марта 2004 г.). «MUSCLE: множественное выравнивание последовательностей с высокой точностью и высокой пропускной способностью» . Исследования нуклеиновых кислот . 32 (5): 1792–1797. дои : 10.1093/nar/gkh340 . ПМК 390337 . ПМИД 15034147 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]