Clustal - Clustal

CLUSTAL
Разработчики)
  • Де Хиггинс
  • Фабиан Сиверс
  • Дэвид Дайнин
  • Андреас Вильм (все в Институте Конвея, UCD )
Стабильный выпуск
1.2.2 / 1 июля 2016 г.; 4 года назад (2016-07-01)
Написано вC ++
Операционная системаUNIX, Linux, MacOS, MS-Windows, FreeBSD, Debian
ТипИнструмент биоинформатики
ЛицензияСтандартная общественная лицензия GNU, версия 2[1]
Интернет сайтwww.clustal.org/омега/

Clustal это серия широко используемых компьютерные программы используется в Биоинформатика за множественное выравнивание последовательностей.[2] При разработке алгоритма, перечисленного ниже, было много версий Clustal. Анализ каждого инструмента и его алгоритма также подробно описан в соответствующих категориях. Доступные операционные системы, перечисленные на боковой панели, представляют собой комбинацию доступности программного обеспечения и могут не поддерживаться для каждой текущей версии инструментов Clustal. Clustal Omega имеет самый широкий выбор операционных систем из всех инструментов Clustal.

Множественное выравнивание последовательностей белка CDK4, созданного с помощью ClustalW. Стрелки указывают на точечные мутации.

История

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

  • Clustal: Оригинальное программное обеспечение для множественного выравнивания последовательностей, созданное Де Хиггинсом в 1988 году, было основано на получении филогенетических деревьев из попарных последовательностей аминокислот или нуклеотидов.[3]
  • ClustalV: Второе поколение программного обеспечения Clustal было выпущено в 1992 году и представляло собой переработку исходного пакета Clustal. Он представил реконструкцию филогенетического дерева при окончательном выравнивании, возможность создавать выравнивания из существующих выравниваний и возможность создавать деревья из выравниваний с использованием метода, называемого Присоединение к соседу.[4]
  • ClustalW: Третье поколение, выпущенное в 1994 году, значительно улучшило предыдущие версии. Он улучшил алгоритм прогрессивного выравнивания различными способами, в том числе позволял взвешивать отдельные последовательности в сторону уменьшения или увеличения в зависимости от сходства или расхождения, соответственно, при частичном выравнивании. Он также включал возможность запускать программу в пакетном режиме из командной строки.[3]
  • ClustalX: Эта версия, выпущенная в 1997 году, была первой с графическим пользовательским интерфейсом.[5]
  • ClustalΩ (Омега): Текущая стандартная версия.[6][7]
  • Clustal2: Обновленные версии ClustalW и ClustalX с более высокой точностью и эффективностью.[8]

Статьи, описывающие программное обеспечение clustal, были очень цитируемыми, причем две из них были одними из самых цитируемых статей всех времен.[9]

Самая последняя версия программного обеспечения, доступная для Windows, Mac OS и Unix / Linux. Он также обычно используется через веб-интерфейс. домашняя страница или размещен Европейский институт биоинформатики.

Происхождение имени

Дерево направляющих в исходных программах было построено с помощью UPGMA кластьэээальysis парных выравниваний, отсюда и название CLUSTAL.[10]ср.[11] Первые четыре версии 1988 года имели арабские цифры (от 1 до 4), тогда как в пятой версии Де Хиггинс перешел на римскую цифру V в 1992 году.[10]ср.[12][4] В 1994 и 1997 годах для следующих двух версий буквы после буквы V использовались и соответствовали W для взвешенного и X для X Window.[10]ср.[13][5] Название «Омега» было выбрано, чтобы обозначить отличие от предыдущих.[10]

Функция

Все варианты программного обеспечения Clustal выравнивают последовательности с использованием эвристики, которая постепенно строит множественное выравнивание последовательностей из серии попарных выравниваний. Этот метод работает путем анализа последовательностей в целом, а затем использования метода UPGMA / Neighbor-joining для создания матрицы расстояний. Затем на основе оценок последовательностей в матрице вычисляется направляющее дерево, которое затем используется для построения множественного выравнивания последовательностей путем постепенного выравнивания последовательностей в порядке сходства.[14] По сути, Clustal создает несколько выравниваний последовательностей с помощью трех основных шагов:

  1. Сделать попарное выравнивание с использованием метода прогрессивного выравнивания
  2. Создать направляющее дерево (или используйте определяемое пользователем дерево)
  3. Используйте дерево направляющих для выполнения множественного выравнивания

Эти шаги выполняются автоматически, когда вы выбираете «Выполнить полное выравнивание». Другие варианты - «Выполнить выравнивание из направляющего дерева и филогении» и «Создать только направляющее дерево».

Ввод, вывод

Эта программа принимает широкий спектр входных форматов, включая NBRF /PIR, ФАСТА, EMBL /Swiss-Prot, Clustal, GCC / MSF, GCG9 RSF и GDE.

Формат вывода может быть одним или несколькими из следующих: Clustal, NBRF /PIR, GCG / MSF, ФИЛИП, GDE или NEXUS.

Чтение результатов выравнивания нескольких последовательностей
СимволОпределениеСмысл
*звездочкапозиции, которые имеют единственный и полностью консервативный остаток
:двоеточиесохранение между группами сильно похожих свойств

с результатом более 0,5 по матрице PAM 250

.периодсохранение между группами слабо подобных свойств

с результатом меньше или равным 0,5 по матрице PAM 250

Одни и те же символы показаны как для выравнивания ДНК / РНК, так и для выравнивания белков, поэтому, хотя символы * (звездочка) полезны для обоих, другие согласованные символы следует игнорировать при выравнивании ДНК / РНК.

Настройки

Многие настройки можно изменить, чтобы адаптировать алгоритм выравнивания к различным обстоятельствам. Основными параметрами являются штраф за открытие промежутка и штраф за расширение промежутка.

Clustal и ClustalV

Краткое содержание

Первоначальная программа из серии программ Clustal была разработана в 1988 году как способ генерации множественных выравниваний последовательностей на персональных компьютерах. ClustalV был выпущен 4 года спустя и значительно улучшил оригинал, добавив и изменив несколько ключевых функций, включая переход на C вместо Fortran, как его предшественник.

Алгоритм

Обе версии используют один и тот же быстрый приближенный алгоритм для вычисления оценок сходства между последовательностями, что, в свою очередь, производит попарные выравнивания. Алгоритм работает, вычисляя оценки сходства как количество совпадений k-кортежей между двумя последовательностями с учетом установленного штрафа за пропуски. Чем больше похожи последовательности, тем выше балл, чем больше расхождения, тем ниже баллы. После того, как последовательности оценены, дендрограмма генерируется посредством UPGMA для представления порядка множественного выравнивания последовательностей. Сначала выравниваются наборы последовательностей с более высоким порядком, а затем остальные в порядке убывания. Алгоритм позволяет обрабатывать очень большие наборы данных и работает быстро. Однако скорость зависит от диапазона совпадений k-кортежей, выбранных для конкретного типа последовательности.[15]

Заметные улучшения ClustalV

Некоторые из наиболее заметных дополнений в ClustalV - это выравнивание профилей и полные параметры интерфейса командной строки. Возможность использования профилей выравнивания позволяет пользователю выровнять два или более предыдущих выравнивания или последовательностей с новым выравниванием и перемещать неправильно выровненные последовательности (с низким баллом) дальше в порядке выравнивания. Это дает пользователю возможность постепенно и методично создавать множественные выравнивания последовательностей с большим контролем, чем базовый вариант.[14] Возможность запуска из командной строки значительно ускоряет процесс выравнивания нескольких последовательностей. Последовательности можно запускать с помощью простой команды,

 Clustalv имя.seq

или же 

 Clustalv /infile=имя.seq

и программа определит, какой тип последовательности она анализирует. Когда программа завершена, выходные данные множественного выравнивания последовательностей, а также дендрограмма попадают в файлы с расширениями .aln и .dnd соответственно. Интерфейс командной строки использует параметры по умолчанию и не допускает других параметров.[15]

ClustalW

Краткое содержание

Изображает шаги, которые алгоритм программного обеспечения ClustalW использует для глобального выравнивания.

ClustalW, как и другие инструменты Clustal, используется для эффективного выравнивания нескольких последовательностей нуклеотидов или белков. Он использует методы прогрессивного выравнивания, которые сначала выравнивают наиболее похожие последовательности и постепенно переходят к наименее похожим последовательностям, пока не будет создано глобальное выравнивание. ClustalW - это матричный алгоритм, тогда как такие инструменты, как Т-кофе и Dialign основаны на согласованности. ClustalW имеет довольно эффективный алгоритм, который хорошо конкурирует с другим программным обеспечением. Эта программа требует трех или более последовательностей для вычисления глобального выравнивания, для попарного выравнивания последовательностей (2 последовательности) используйте инструменты, подобные EMBOSS, LALIGN.

Схема, показывающая метод соединения соседей при выравнивании последовательностей для биоинформатики

Алгоритм

ClustalW использует методы прогрессивного выравнивания, как указано выше. В них сначала выравниваются последовательности с наилучшей оценкой выравнивания, затем выравниваются постепенно более отдаленные группы последовательностей. Этот эвристический подход необходим из-за того, что для поиска глобального оптимального решения требуется время и память. Первым шагом к алгоритму является вычисление приблизительной матрицы расстояний между каждой парой последовательностей, также известной как попарное выравнивание последовательностей. Следующий шаг - это метод соединения соседей который использует укоренение средней точки для создания общего направляющего дерева.[16] Процесс, который он использует для этого, показан на подробной диаграмме метода справа. Затем дерево направляющих используется в качестве приблизительного шаблона для генерации глобального выравнивания.

Сложность времени

ClustalW имеет временную сложность из-за использования метода объединения соседей. В обновленной версии (ClustalW2) есть опция, встроенная в программное обеспечение для использования UPGMA что быстрее при больших размерах ввода. Флаг командной строки, чтобы использовать его вместо объединения соседей:

-кластеризация=UPGMA

Например, на стандартном настольном компьютере запуск UPGMA для 10 000 последовательностей даст результаты менее чем за минуту, а объединение соседей займет более часа.[17] Запуск алгоритма ClustalW с этой настройкой значительно экономит время. ClustalW2 также имеет возможность использовать итеративное выравнивание для повышения точности выравнивания. Хотя это не обязательно быстрее или эффективнее с точки зрения сложности, повышение точности ценно и может быть полезно для данных меньшего размера. Для этого используются различные флаги командной строки:

-Итерация=Выравнивание-Итерация=Дерево-числа

Первый параметр командной строки уточняет окончательное выравнивание. Второй вариант включает схему в шаг последовательного выравнивания алгоритма. Третий определяет количество циклов итерации, где значение по умолчанию установлено на 3.[17]

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

Алгоритм, который использует ClustalW, почти всегда дает результат, близкий к оптимальному. Однако это исключительно хорошо, когда набор данных содержит последовательности с различной степенью расхождения. Это связано с тем, что в таком наборе данных дерево направляющих становится менее чувствительным к шуму. ClustalW был одним из первых алгоритмов, сочетающих попарное выравнивание и глобальное выравнивание в попытке повысить скорость, и он работал, но из-за этого наблюдается потеря точности, которой нет в другом программном обеспечении.

ClustalW, по сравнению с другими алгоритмами MSA, работает как один из самых быстрых, при этом сохраняя уровень точности.[18] Еще многое предстоит улучшить по сравнению с его конкурентами, основанными на консистенции, такими как T-Coffee. Точность ClustalW при тестировании с MAFFT, T-Coffee, Clustal Omega и другими реализациями MSA показала самую низкую точность для полноразмерных последовательностей. У него было меньше всего баран требующий памяти алгоритм из всех протестированных в исследовании.[18] Хотя ClustalW зафиксировал самый низкий уровень точности среди своих конкурентов, он все же сохранил то, что некоторые сочли бы приемлемым. В алгоритм, присутствующий в ClustalW2, были внесены обновления и улучшения, которые работают для повышения точности, сохраняя при этом столь ценную скорость.[17]

Clustal Omega

Краткое содержание

Блок-схема, изображающая пошаговый алгоритм, используемый в Clustal Omega.

ClustalΩ (альтернативно записывается как Clustal O и Clustal Omega) - это быстрая и масштабируемая программа, написанная на C и C ++, используемая для множественное выравнивание последовательностей. Он использует засеянные направляющие деревья и новый ХМ движок, который фокусируется на двух профилях для создания этих выравниваний.[19][20] Программе требуются три или более последовательностей для расчета множественное выравнивание последовательностей, для двух последовательностей используйте инструменты попарного выравнивания последовательностей (EMBOSS, LALIGN ). Clustal Omega основана на согласованности и широко рассматривается как одна из самых быстрых онлайн-реализаций всех инструментов множественного выравнивания последовательностей и по-прежнему занимает высокие места по точности как среди алгоритмов, основанных на согласованности, так и среди алгоритмов на основе матрицы.

Алгоритм

Здесь показана структура профиля HMM, используемого при реализации Clustal Omega.

Clustal Omega имеет пять основных шагов для создания множественное выравнивание последовательностей. Первый - это попарное выравнивание с использованием метода k-кортежей, также известного как метод слова. Таким образом, это эвристический метод, который не гарантирует нахождение оптимального решения для выравнивания, но значительно более эффективен, чем метод динамического программирования для выравнивания. После этого последовательности группируются с использованием модифицированного метода mBed.[21] Метод mBed вычисляет попарное расстояние, используя встраивание последовательности. За этим шагом следует метод кластеризации k-средних. Далее строится направляющее дерево с использованием Метод UPGMA. Это показано в виде нескольких шагов дерева направляющих, ведущих к одному окончательному построению дерева направляющих из-за того, как работает алгоритм UPGMA. На каждом шаге (каждый ромб на блок-схеме) два ближайших кластера объединяются и повторяются до тех пор, пока не будет оценено окончательное дерево. На последнем этапе множественное выравнивание последовательностей производится с использованием пакета HHAlign из HH-Люкс, который использует два профиля HMM's. Профиль HMM - это линейный конечный автомат, состоящий из серии узлов, каждый из которых примерно соответствует положению (столбцу) в выравнивании, из которого он был построен.[22]

Сложность времени

Точный способ вычисления оптимального выравнивания между N последовательности имеют вычислительную сложность за N последовательности длины L что делает его недопустимым даже для небольшого количества последовательностей. Clustal Omega использует модифицированную версию mBed, сложность которой составляет ,[21][23] и производит деревья направляющих, которые так же точны, как и деревья, полученные с помощью традиционных методов. Скорость и точность направляющих деревьев в Clustal Omega приписываются реализации модифицированного алгоритма mBed. Это также сокращает время вычислений и требования к памяти для выполнения выравнивания больших наборов данных.

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

Точность Clustal Omega в отношении небольшого количества последовательностей в среднем очень похожа на точность выравнивателей последовательностей высокого качества. Разница возникает при использовании больших наборов данных с сотнями тысяч последовательностей. В этих случаях Clustal Omega превосходит другие алгоритмы по всем параметрам. Его время завершения и общее качество неизменно лучше, чем у других программ.[24] Он способен обрабатывать более 100 000 последовательностей на одном процессоре за несколько часов.

Clustal Omega использует пакет HHAlign HH-Люкс, который выравнивает два профиля Скрытые марковские модели вместо сравнения профиля с профилем. Это значительно улучшает качество чувствительности и выравнивания.[24] В сочетании с методом mBed это дает Clustal Omega преимущество перед другими выравнивателями последовательностей. Результаты получаются очень точными и очень быстрыми, что является оптимальной ситуацией.

В наборах данных с несохраняемыми терминальными базами Clustal Omega может быть более точным, чем Пробконы и Т-кофе несмотря на то, что оба эти алгоритмы основаны на согласованности, в отличие от Clustal Omega. В тесте эффективности с программами, которые дают высокие показатели точности, MAFFT была самой быстрой, за ней следовала Clustal Omega. Оба были быстрее, чем T-Coffee, однако для работы MAFFT и Clustal Omega требовалось больше памяти.[18]

Clustal2 (ClustalW / ClustalX)

Clustal2 представляет собой упакованный выпуск командной строки ClustalW и графического Clustal X. Это не новые инструменты, а обновленные и улучшенные версии предыдущих реализаций, показанных выше. Обе загрузки предварительно скомпилированы для многих операционных систем, таких как Linux, Mac OS X и Windows (как XP, так и Vista). Этот выпуск был разработан для того, чтобы сделать веб-сайт более организованным и удобным для пользователя, а также для обновления исходных кодов до самых последних версий. Clustal2 - это версия 2 как ClustalW, так и ClustalX, отсюда она и получила свое название. Прошлые версии все еще можно найти на веб-сайте, однако теперь все предварительные компиляции обновлены.

Смотрите также

Рекомендации

  1. ^ Смотрите файл КОПИРОВАНИЕ в исходном архиве [1]. Проверено 15 января 2014 г.
  2. ^ Ченна Р., Сугавара Х, Коике Т., Лопес Р., Гибсон TJ, Хиггинс Д.Г., Томпсон Дж. Д. (июль 2003 г.). «Множественное выравнивание последовательностей с помощью программ серии Clustal». Исследования нуклеиновых кислот. 31 (13): 3497–500. Дои:10.1093 / нар / гкг500. ЧВК  168907. PMID  12824352.
  3. ^ а б Хиггинс Д.Г., Sharp PM (декабрь 1988 г.). «CLUSTAL: пакет для выполнения множественного выравнивания последовательностей на микрокомпьютере». Ген. 73 (1): 237–44. Дои:10.1016/0378-1119(88)90330-7. PMID  3243435.
  4. ^ а б Хиггинс Д.Г., Близби А.Дж., Фукс Р. (апрель 1992 г.). «CLUSTAL V: улучшенное программное обеспечение для множественного выравнивания последовательностей». Компьютерные приложения в биологических науках. 8 (2): 189–91. Дои:10.1093 / биоинформатика / 8.2.189. PMID  1591615.
  5. ^ а б Томпсон JD, Гибсон TJ, Plewniak F, Jeanmougin F, Higgins DG (декабрь 1997 г.). «Интерфейс Windows CLUSTAL_X: гибкие стратегии для множественного выравнивания последовательностей при помощи инструментов анализа качества». Исследования нуклеиновых кислот. 25 (24): 4876–82. Дои:10.1093 / nar / 25.24.4876. ЧВК  147148. PMID  9396791.
  6. ^ Сиверс Ф., Хиггинс Д.Г. (01.01.2014). Рассел DJ (ред.). Методы совмещения нескольких последовательностей. Методы молекулярной биологии. 1079. Humana Press. С. 105–116. Дои:10.1007/978-1-62703-646-7_6. ISBN  9781627036450. PMID  24170397.
  7. ^ Сиверс Ф., Хиггинс Д.Г. (01.01.2002). Clustal Omega. Текущие протоколы в биоинформатике. 48. John Wiley & Sons, Inc., стр. 3.13.1–16. Дои:10.1002 / 0471250953.bi0313s48. ISBN  9780471250951. PMID  25501942. S2CID  1762688.
  8. ^ Дайнин, Дэвид. «Множественное выравнивание последовательностей Clustal W и Clustal X». www.clustal.org. Получено 2018-04-24.
  9. ^ Ван Норден Р., Махер Б., Nuzzo R (Октябрь 2014 г.). «100 лучших работ». Природа. 514 (7524): 550–3. Bibcode:2014Натура.514..550В. Дои:10.1038 / 514550a. PMID  25355343.
  10. ^ а б c d Де Хиггинс, презентация на конференции SMBE 2012 в Дублине.
  11. ^ Хиггинс Д.Г., Sharp PM (Декабрь 1988 г.). «CLUSTAL: пакет для выполнения множественного выравнивания последовательностей на микрокомпьютере». Ген. 73 (1): 237–44. Дои:10.1016/0378-1119(88)90330-7. PMID  3243435.
  12. ^ Хиггинс Д.Г., Sharp PM (Апрель 1989 г.). «Быстрое и точное выравнивание нескольких последовательностей на микрокомпьютере». Компьютерные приложения в биологических науках. 5 (2): 151–3. Дои:10.1093 / биоинформатика / 5.2.151. PMID  2720464.
  13. ^ Томпсон Дж. Д., Хиггинс Д. Г., Гибсон TJ (Ноябрь 1994 г.). «CLUSTAL W: повышение чувствительности прогрессивного множественного выравнивания последовательностей за счет взвешивания последовательностей, штрафов за пропуски в зависимости от позиции и выбора весовой матрицы». Исследования нуклеиновых кислот. 22 (22): 4673–80. Дои:10.1093 / nar / 22.22.4673. ЧВК  308517. PMID  7984417.
  14. ^ а б "CLUSTAL W алгоритм". Архивировано из оригинал на 2016-12-01. Получено 2018-04-24.
  15. ^ а б https://www.aua.gr/~eliop/mathimata/molevol/Askhsh1/clustalv.htm
  16. ^ "О CLUSTALW". www.megasoftware.net. Получено 2018-04-24.
  17. ^ а б c Larkin, M.A .; Blackshields, G .; Brown, N.P .; Chenna, R .; McGettigan, P.A .; McWilliam, H .; Валентин, Ф .; Wallace, I.M .; Вильм, А. (10 сентября 2007 г.). «Clustal W и Clustal X версии 2.0». Биоинформатика. 23 (21): 2947–2948. Дои:10.1093 / биоинформатика / btm404. ISSN  1367-4803. PMID  17846036.
  18. ^ а б c Pais FS, Ruy PC, Oliveira G, Coimbra RS (март 2014 г.). «Оценка эффективности программ множественного выравнивания последовательностей». Алгоритмы молекулярной биологии. 9 (1): 4. Дои:10.1186/1748-7188-9-4. ЧВК  4015676. PMID  24602402.
  19. ^ EMBL-EBI. "Clustal Omega <Выравнивание множественных последовательностей . www.ebi.ac.uk. Получено 2018-04-18.
  20. ^ Дайнин, Дэвид. «Многопоследовательное выравнивание Clustal Omega, ClustalW и ClustalX». www.clustal.org. Получено 2018-04-18.
  21. ^ а б Блэкшилдс Дж., Сиверс Ф., Ши В., Вильм А., Хиггинс Д. Г. (май 2010 г.). «Встраивание последовательностей для быстрого построения направляющих деревьев для множественного выравнивания последовательностей». Алгоритмы молекулярной биологии. 5: 21. Дои:10.1186/1748-7188-5-21. ЧВК  2893182. PMID  20470396.
  22. ^ «Профильный анализ HMM». www.biology.wustl.edu. Архивировано из оригинал на 2019-07-24. Получено 2018-05-01.
  23. ^ Сиверс Ф., Вильм А., Динин Д., Гибсон Т. Дж., Карплус К., Ли В., Лопес Р., Мак-Вильям Х, Реммерт М., Сёдинг Дж., Томпсон Дж. Д., Хиггинс Д. Г. (октябрь 2011 г.). «Быстрое, масштабируемое создание высококачественного выравнивания множественных последовательностей белков с использованием Clustal Omega». Молекулярная системная биология. 7 (1): 539. Дои:10.1038 / msb.2011.75. ЧВК  3261699. PMID  21988835.
  24. ^ а б Даугелайте Дж., О 'Дрисколл А., Слейтор РД (2013). «Обзор множественных сопоставлений последовательностей и облачных вычислений в биоинформатике». ISRN Биоматематика. 2013: 1–14. Дои:10.1155/2013/615630. ISSN  2090-7702.

внешняя ссылка