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