stringtranslate.com

Кластал

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

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

История

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

The papers describing the Clustal software have been very highly cited, with two of them amongst the most cited papers of all time.[10]

The most recent version of the software is available for Windows, Mac OS, and Unix/Linux. It is also commonly used via a web interface on its home page or hosted by the European Bioinformatics Institute.

Name origin

The guide tree in the initial programs was constructed via a UPGMA cluster analysis of the pairwise alignments, hence the name CLUSTAL.[11]cf.[12] The first four versions in 1988 had Arabic numerals (1 to 4), whereas with the fifth version Des Higgins switched to Roman numeral V in 1992.[11]cf.[13][4] In 1994 and in 1997, for the next two versions, the letters after the letter V were used and made to correspond to W for Weighted and X for X Window.[11]cf.[14][6] The name omega was chosen to mark a change from the previous ones.[11]

Function

All variations of the Clustal software align sequences using a heuristic that progressively builds a multiple sequence alignment from a series of pairwise alignments. This method works by analyzing the sequences as a whole, then utilizing the UPGMA/Neighbor-joining method to generate a distance matrix. A guide tree is then calculated from the scores of the sequences in the matrix, then subsequently used to build the multiple sequence alignment by progressively aligning the sequences in order of similarity.[15] Essentially, Clustal creates multiple sequence alignments through three main steps:

  1. Do a pairwise alignment using the progressive alignment method
  2. Create a guide tree (or use a user-defined tree)
  3. Use the guide tree to carry out a multiple alignment

These steps are carried out automatically when you select "Do Complete Alignment". Other options are "Do Alignment from guide tree and phylogeny" and "Produce guide tree only".

Input/Output

This program accepts a wide range of input formats, including NBRF/PIR, FASTA, EMBL/Swiss-Prot, Clustal, GCC/MSF, GCG9 RSF, and GDE.

The output format can be one or many of the following: Clustal, NBRF/PIR, GCG/MSF, PHYLIP, GDE, or 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

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

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

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

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

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

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

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

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

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

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

Алгоритм

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

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

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

Точный способ вычисления оптимального выравнивания между N последовательностями имеет вычислительную сложность для N последовательностей длины L , что делает его невозможным даже для небольшого числа последовательностей. 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. ^ Хиггинс Д.Г., Sharp PM (декабрь 1988 г.). «CLUSTAL: пакет для выполнения множественного выравнивания последовательностей на микрокомпьютере». Джин . 73 (1): 237–44. дои : 10.1016/0378-1119(88)90330-7. ПМИД  3243435.
  4. ^ аб Хиггинс Д.Г., Блисби А.Дж., Фукс Р. (апрель 1992 г.). «CLUSTAL V: улучшенное программное обеспечение для множественного выравнивания последовательностей». Компьютерные приложения в биологических науках . 8 (2): 189–91. doi : 10.1093/биоинформатика/8.2.189. ПМИД  1591615.
  5. ^ Томпсон, JD; Хиггинс, Д.Г.; Гибсон, Ти Джей (11 ноября 1994 г.). «CLUSTAL W: повышение чувствительности прогрессивного выравнивания множественных последовательностей за счет взвешивания последовательностей, штрафов за пробелы для конкретной позиции и выбора весовой матрицы». Исследования нуклеиновых кислот . 22 (22): 4673–4680. дои : 10.1093/нар/22.22.4673. ISSN  0305-1048. ПМЦ 308517 . ПМИД  7984417. 
  6. ^ Аб Томпсон Дж.Д., Гибсон Т.Дж. , Плевняк Ф., Жанмуген Ф., Хиггинс Д.Г. (декабрь 1997 г.). «Интерфейс окон CLUSTAL_X: гибкие стратегии выравнивания множественных последовательностей с помощью инструментов анализа качества». Исследования нуклеиновых кислот . 25 (24): 4876–82. дои : 10.1093/нар/25.24.4876. ПМК 147148 . ПМИД  9396791. 
  7. ^ Дайнин, Дэвид. «Выравнивание множественных последовательностей Clustal W и Clustal X». www.clustal.org . Архивировано из оригинала 16 апреля 2018 г. Проверено 24 апреля 2018 г.
  8. ^ Сиверс Ф., Хиггинс Д.Г. (1 января 2014 г.). «Кластальная омега, точное выравнивание очень большого количества последовательностей». У Рассела DJ (ред.). Множественные методы выравнивания последовательностей . Методы молекулярной биологии. Том. 1079. Хумана Пресс. стр. 105–116. дои : 10.1007/978-1-62703-646-7_6. ISBN 9781627036450. ПМИД  24170397.
  9. ^ Сиверс Ф., Хиггинс Д.Г. (1 января 2002 г.). Кластал Омега . Том. 48. John Wiley & Sons, Inc., стр. 3.13.1–16. дои : 10.1002/0471250953.bi0313s48. ISBN 9780471250951. PMID  25501942. S2CID  1762688. {{cite book}}: |journal=игнорируется ( помощь )
  10. ^ Ван Ноорден Р., Махер Б., Нуццо Р. (октябрь 2014 г.). «100 лучших статей». Природа . 514 (7524): 550–3. Бибкод : 2014Natur.514..550V. дои : 10.1038/514550a . ПМИД  25355343.
  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. ^ abc Ларкин, Массачусетс; Блэкшилдс, Г.; Браун, Северная Каролина; Ченна, Р.; МакГеттиган, Пенсильвания; Маквильям, Х.; Валентин, Ф.; Уоллес, ИМ; Уилм, А. (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.

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