Из Википедии, бесплатной энциклопедии
  (Перенаправлено из ClustalO )
Перейти к навигации Перейти к поиску
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 / omega /

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

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

История [ править ]

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

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

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

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

Происхождение имени [ править ]

Руководство дерево исходных программ было построено с помощью UPGMA Clust эр в аль лиз попарных выравниваний, отсюда и название 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 , FASTA , EMBL / Swiss-Prot , Clustal, GCC / MSF, GCG9 RSF и GDE.

Формат вывода может быть одним или несколькими из следующих: Clustal, NBRF / PIR , GCG / MSF, PHYLIP , 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  nameoffile . seq

или же 

 clustalv  / infile = nameoffile . seq

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

ClustalW [ править ]

Краткое изложение [ править ]

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

ClustalW, как и другие инструменты Clustal, используется для эффективного выравнивания множественных нуклеотидных или белковых последовательностей. Он использует методы прогрессивного выравнивания, которые сначала выравнивают наиболее похожие последовательности и постепенно переходят к наименее похожим последовательностям, пока не будет создано глобальное выравнивание. ClustalW - это матричный алгоритм, тогда как такие инструменты, как T-Coffee и 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 ++, используемая для множественного выравнивания последовательностей . Он использует засеянные направляющие деревья и новый механизм HMM, который фокусируется на двух профилях для создания этих выравниваний. [19] [20] Программе требуются три или более последовательностей для вычисления множественного выравнивания последовательностей , для двух последовательностей используйте инструменты попарного выравнивания последовательностей ( EMBOSS , LALIGN). Clustal Omega основана на согласованности и широко рассматривается как одна из самых быстрых онлайн-реализаций всех инструментов множественного выравнивания последовательностей, и по-прежнему занимает высокие места по точности как среди алгоритмов, основанных на согласованности, так и среди алгоритмов на основе матрицы.

Алгоритм [ править ]

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

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

Сложность времени [ править ]

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

Точность и результаты [ править ]

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

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

В наборах данных с неконсервативными терминальными базами Clustal Omega может быть более точным, чем Probcons и T-Coffee, несмотря на то, что оба эти алгоритмы основаны на согласованности, в отличие от 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, отсюда она и получила свое название. Прошлые версии все еще можно найти на веб-сайте, однако теперь все предварительные компиляции обновлены.

См. Также [ править ]

  • Программное обеспечение для выравнивания последовательностей
  • ДНАСТАР
  • Последовательный майнинг
  • Т-кофе
  • Align-m
  • ДИАЛИН-Т
  • DIALIGN-TX
  • JAligner
  • MAFFT
  • МАВИД
  • МЫШЦЫ
  • ProbCons

Ссылки [ править ]

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

Внешние ссылки [ править ]

  • Домашняя страница Clustal (бесплатная загрузка для Unix / Linux, Mac и Windows)
  • Зеркало Clustal Omega на выставке EBI