stringtranslate.com

Кластал

Clustal — это компьютерная программа , используемая для множественного выравнивания последовательностей в биоинформатике . [2] Программное обеспечение (и алгоритмы) претерпело несколько итераций, последней версией по состоянию на 2011 год является ClustalΩ (Omega) . Оно доступно как автономное программное обеспечение, через веб-интерфейс и через сервер, размещенный Европейским институтом биоинформатики .

Clustal является важным биоинформатическим программным обеспечением: две его научные публикации вошли в число 100 лучших цитируемых статей всех времен по версии журнала Nature в 2014 году. [3]

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

История

За прошедшие годы Clustal претерпел несколько итераций:

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

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

Функция

Clustal выравнивает последовательности, используя эвристику , которая постепенно строит множественное выравнивание последовательностей из набора парных выравниваний. Этот метод работает путем анализа последовательностей в целом и использования метода UPGMA/соединения соседей для создания матрицы расстояний . Направляющее дерево рассчитывается на основе оценок последовательностей в матрице, а затем используется для построения множественного выравнивания последовательностей путем постепенного выравнивания последовательностей в порядке сходства. [15]

По сути, Clustal создает множественные выравнивания последовательностей за три основных этапа:

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

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

Ввод, вывод

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

Выходной формат может быть одним или несколькими из следующих: Clustal, NBRF/ PIR , GCG /MSF, PHYLIP , GDE или NEXUS.

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

Настройки

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

Кластал и КласталВ

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

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

Алгоритм

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

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

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

 clustalv имя_файла . последовательность

или

 clustalv / infile = nameoffile . последовательность

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

КласталВ

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

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

ClustalW, как и другие версии Clustal, используется для эффективного выравнивания нескольких нуклеотидных или белковых последовательностей. Он использует методы прогрессивного выравнивания, которые определяют приоритет последовательностей для выравнивания на основе сходства до тех пор, пока не будет получено глобальное выравнивание. ClustalW — это алгоритм , основанный на матрицах , тогда как такие инструменты, как T-Coffee и Dialign, основаны на согласованности . ClustalW эффективен и конкурентоспособен по сравнению с аналогичным программным обеспечением. [ нужна цитация ] Эта программа требует трех или более последовательностей для расчета глобального выравнивания. Для выравнивания двоичной последовательности следует использовать другие инструменты, такие как EMBOSS или LALIGN.

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

Алгоритм

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

Сначала алгоритм вычисляет матрицу попарных расстояний между всеми парами последовательностей ( попарное выравнивание последовательностей ). Затем метод соединения соседей использует укоренение средней точки для создания общего направляющего дерева. [17] Схема этого метода показана справа. Наконец, направляющее дерево используется в качестве приблизительного шаблона для создания глобального выравнивания.

Временная сложность

ClustalW имеет временную сложность из- за использования метода соединения соседей.

В ClustalW2 добавлена ​​возможность использовать вместо этого UPGMA, что быстрее при больших размерах входных данных. Флаг командной строки, позволяющий использовать его вместо присоединения к соседям:

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

В качестве приблизительного примера: хотя ввод 10 000 последовательностей займет более часа для объединения соседей, UPGMA завершится менее чем за минуту.

В ClustalW2 также добавлена ​​итеративная точность выравнивания. Эта опция не повышает эффективность, но дает возможность повысить точность выравнивания. Это может быть особенно полезно для небольших наборов данных.

Следующие флаги активируют итеративное выравнивание:

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

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

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

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

Когда в 2014 году сравнивалось несколько алгоритмов выравнивания последовательностей, ClustalW оказался одним из самых быстрых, способных давать результаты с желаемым уровнем точности. Тем не менее, сравнения с конкурентами, основанными на постоянстве (такими как T-Coffee), показывают, что существуют возможности для улучшения. [19] Из MAFFT, T-Coffee и Clustal Omega, ClustalW имеет самую низкую точность для полноразмерных последовательностей. Тем не менее, его точность по-прежнему считается приемлемой. Кроме того, ClustalW оказался наиболее эффективным с точки зрения использования памяти алгоритмом из изученных. [19] Постоянные обновления программного обеспечения сделали ClustalW2 более точным, сохраняя при этом эту скорость. [18]

Кластал Омега

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

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

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

Алгоритм

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

Clustal Omega состоит из пяти основных этапов для создания множественного выравнивания последовательностей .

  1. Попарное выравнивание производится с использованием метода k-кортежей. Это эвристический метод, который не гарантирует нахождение оптимального решения, но он более эффективен, чем использование динамического программирования .
  2. Последовательности кластеризуются с использованием модифицированного метода mBed. [22] Метод mBed рассчитывает попарное расстояние с использованием встраивания последовательности.
  3. Применяется метод кластеризации k-средних .
  4. Направляющее дерево строится методом UPGMA . На рисунке справа это показано как несколько шагов направляющего дерева, ведущих к одному окончательному построению направляющего дерева из-за агломеративного характера UPGMA. На каждом шаге (ромбы на схеме) объединяются два ближайших кластера. Это повторяется до тех пор, пока не будет получено окончательное глобальное дерево.
  5. Окончательное выравнивание множественных последовательностей производится с помощью пакета HHAlign из HH-Suite с использованием двух профилей HMM . Профиль HMM — это линейный конечный автомат, состоящий из ряда узлов, каждый из которых примерно соответствует позиции (столбцу) в выравнивании, из которого он был построен. [23]

Временная сложность

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

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

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

Clustal Omega использует пакет HHAlign из HH-Suite, который выравнивает два профиля скрытых марковских моделей вместо сравнения профилей. Это значительно улучшает качество чувствительности и выравнивания. [25] Это, в сочетании с методом mBed, дает Clustal Omega преимущество перед другими выравнивателями последовательностей.

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

Кластал2 (КлусталВ/КлусталХ)

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

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

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

  1. ^ См. файл COPYING в исходном архиве [1]. Архивировано 12 июня 2021 г. на Wayback Machine . По состоянию на 15 января 2014 г.
  2. ^ Ченна Р., Сугавара Х., Койке Т., Лопес Р., Гибсон Т.Дж. , Хиггинс Д.Г. , Томпсон Дж.Д. (июль 2003 г.). «Множественное выравнивание последовательностей с помощью программ серии Clustal». Исследования нуклеиновых кислот . 31 (13): 3497–500. дои : 10.1093/nar/gkg500. ПМК  168907 . ПМИД  12824352.
  3. ^ Ван Ноорден Р., Махер Б., Нуццо Р. (октябрь 2014 г.). «100 лучших статей». Природа . 514 (7524): 550–3. Бибкод : 2014Natur.514..550V. дои : 10.1038/514550a . ПМИД  25355343.
  4. ^ Хиггинс Д.Г., Sharp PM (декабрь 1988 г.). «CLUSTAL: пакет для выполнения множественного выравнивания последовательностей на микрокомпьютере». Джин . 73 (1): 237–44. дои : 10.1016/0378-1119(88)90330-7. ПМИД  3243435.
  5. ^ аб Хиггинс Д.Г., Блисби А.Дж., Фукс Р. (апрель 1992 г.). «CLUSTAL V: улучшенное программное обеспечение для множественного выравнивания последовательностей». Компьютерные приложения в биологических науках . 8 (2): 189–91. doi : 10.1093/биоинформатика/8.2.189. ПМИД  1591615.
  6. ^ Томпсон, JD; Хиггинс, Д.Г.; Гибсон, Ти Джей (11 ноября 1994 г.). «CLUSTAL W: повышение чувствительности прогрессивного выравнивания множественных последовательностей за счет взвешивания последовательностей, штрафов за пробелы для конкретной позиции и выбора весовой матрицы». Исследования нуклеиновых кислот . 22 (22): 4673–4680. дои : 10.1093/нар/22.22.4673. ISSN  0305-1048. ПМК 308517 . ПМИД  7984417. 
  7. ^ Аб Томпсон Дж.Д., Гибсон Т.Дж. , Плевняк Ф., Жанмуген Ф., Хиггинс Д.Г. (декабрь 1997 г.). «Интерфейс окон CLUSTAL_X: гибкие стратегии выравнивания множественных последовательностей с помощью инструментов анализа качества». Исследования нуклеиновых кислот . 25 (24): 4876–82. дои : 10.1093/нар/25.24.4876. ПМК 147148 . ПМИД  9396791. 
  8. ^ Дайнин, Дэвид. «Выравнивание множественных последовательностей Clustal W и Clustal X». www.clustal.org . Архивировано из оригинала 16 апреля 2018 г. Проверено 24 апреля 2018 г.
  9. ^ Сиверс Ф., Хиггинс Д.Г. (1 января 2014 г.). «Кластальная омега, точное выравнивание очень большого количества последовательностей». У Рассела DJ (ред.). Множественные методы выравнивания последовательностей . Методы молекулярной биологии. Том. 1079. Хумана Пресс. стр. 105–116. дои : 10.1007/978-1-62703-646-7_6. ISBN 9781627036450. ПМИД  24170397.
  10. ^ Сиверс Ф., Хиггинс Д.Г. (1 января 2002 г.). Кластал Омега . Том. 48. John Wiley & Sons, Inc., стр. 3.13.1–16. дои : 10.1002/0471250953.bi0313s48. ISBN 9780471250951. PMID  25501942. S2CID  1762688. {{cite book}}: |journal=игнорируется ( помощь )
  11. ^ abcd Дес Хиггинс, презентация на конференции SMBE 2012 в Дублине.
  12. ^ Хиггинс Д.Г., Sharp PM (декабрь 1988 г.). «CLUSTAL: пакет для выполнения множественного выравнивания последовательностей на микрокомпьютере». Джин . 73 (1): 237–44. дои : 10.1016/0378-1119(88)90330-7. ПМИД  3243435.
  13. ^ Хиггинс Д.Г., Sharp PM (апрель 1989 г.). «Быстрое и чувствительное выравнивание множественных последовательностей на микрокомпьютере». Компьютерные приложения в биологических науках . 5 (2): 151–3. doi : 10.1093/биоинформатика/5.2.151. ПМИД  2720464.
  14. ^ Томпсон Дж.Д., Хиггинс Д.Г., Гибсон Т.Дж. (ноябрь 1994 г.). «CLUSTAL W: повышение чувствительности прогрессивного множественного выравнивания последовательностей за счет взвешивания последовательностей, штрафов за пробелы для конкретной позиции и выбора весовой матрицы». Исследования нуклеиновых кислот . 22 (22): 4673–80. дои : 10.1093/нар/22.22.4673. ПМЦ 308517 . ПМИД  7984417. 
  15. ^ ab «Алгоритм CLUSTAL W». Архивировано из оригинала 1 декабря 2016 г. Проверено 24 апреля 2018 г.
  16. ^ аб Хиггинс, Дес (июнь 1991 г.). «Выравнивание множественных последовательностей Clustal V. Документация (установка и использование)». www.aua.gr. ​Архивировано из оригинала 12 апреля 2023 г. Проверено 27 августа 2022 г.
  17. ^ «О CLUSTALW». www.megasoftware.net . Архивировано из оригинала 24 апреля 2018 г. Проверено 24 апреля 2018 г.
  18. ^ Аб Ларкин, Массачусетс; Блэкшилдс, Г.; Браун, Северная Каролина; Ченна, Р.; МакГеттиган, Пенсильвания; Маквильям, Х.; Валентин, Ф.; Уоллес, ИМ; Уилм, А. (10 сентября 2007 г.). «Clustal W и Clustal X версии 2.0». Биоинформатика . 23 (21): 2947–2948. doi : 10.1093/биоинформатика/btm404 . ISSN  1367-4803. ПМИД  17846036.
  19. ^ abc Pais FS, Ruy PC, Oliveira G, Coimbra RS (март 2014 г.). «Оценка эффективности программ множественного выравнивания последовательностей». Алгоритмы молекулярной биологии . 9 (1): 4. дои : 10.1186/1748-7188-9-4 . ПМК 4015676 . ПМИД  24602402. 
  20. ^ EMBL-EBI. «Кластальная омега <Выравнивание множественных последовательностей <EMBL-EBI». www.ebi.ac.uk. ​Архивировано из оригинала 29 апреля 2018 г. Проверено 18 апреля 2018 г.
  21. ^ Дайнин, Дэвид. «Выравнивание множественных последовательностей Clustal Omega, ClustalW и ClustalX». www.clustal.org . Архивировано из оригинала 29 мая 2010 г. Проверено 18 апреля 2018 г.
  22. ^ ab Blackshields G, Сиверс Ф, Ши В, Уилм А, Хиггинс Д.Г. (май 2010 г.). «Встраивание последовательностей для быстрого построения направляющих деревьев для множественного выравнивания последовательностей». Алгоритмы молекулярной биологии . 5:21 . дои : 10.1186/1748-7188-5-21 . ПМК 2893182 . ПМИД  20470396. 
  23. ^ "Профильный анализ HMM" . www.biology.wustl.edu . Архивировано из оригинала 24 июля 2019 г. Проверено 1 мая 2018 г.
  24. ^ Сиверс Ф., Уилм А., Дайнин Д., Гибсон Т.Дж., Карплюс К., Ли В., Лопес Р., Маквильям Х., Реммерт М., Сёдинг Дж., Томпсон Дж.Д., Хиггинс Д.Г. (октябрь 2011 г.). «Быстрое и масштабируемое создание высококачественных выравниваний множественных последовательностей белков с использованием Clustal Omega». Молекулярная системная биология . 7 (1): 539. doi :10.1038/msb.2011.75. ПМЦ 3261699 . ПМИД  21988835. 
  25. ^ аб Даугелайте Дж., О'Дрисколл А., Слиатор Р.Д. (2013). «Обзор множественного выравнивания последовательностей и облачных вычислений в биоинформатике». ISRN Биоматематика . 2013 : 1–14. дои : 10.1155/2013/615630 . ISSN  2090-7702.

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