Clustal - Clustal

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

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

История

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

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

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

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

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

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

Функция

Все варианты программного обеспечения Clustal выравнивают последовательности с использованием эвристики, которая постепенно строит множественное выравнивание последовательностей из серии попарных выравниваний. Этот метод работает путем анализа последовательностей в целом, а затем использования метода UPGMA / Neighbor-joining для создания матрицы расстояний. Затем на основе оценок последовательностей в матрице вычисляется направляющее дерево, которое затем используется для построения множественного выравнивания последовательностей путем постепенного выравнивания последовательностей в порядке сходства. По сути, 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 и ClustalV

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

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

Алгоритм

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

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

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

 clustalv nameoffile.seq

или же

 clustalv /infile=nameoffile.seq

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

ClustalW

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

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

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

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

Алгоритм

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

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

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

-clustering=UPGMA

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

-Iteration=Alignment
-Iteration=Tree
-numiters

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

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

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

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

Clustal Omega

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

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

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

Алгоритм

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

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

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

Точный способ вычисления оптимального выравнивания между N последовательностями имеет вычислительную сложность для N последовательностей длиной L, что делает его недопустимым даже для небольшого числа последовательностей. Clustal Omega использует модифицированную версию mBed, которая имеет сложность и создает направляющие деревья, столь же точные, как и при использовании традиционных методов. Скорость и точность направляющих деревьев в Clustal Omega приписываются реализации модифицированного алгоритма mBed. Это также сокращает вычислительное время и требования к памяти для выполнения выравнивания больших наборов данных. ${\ Displaystyle O (L ^ {N})}$${\ Displaystyle О (Н \ журнал N)}$

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

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

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

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

Clustal2 (ClustalW / ClustalX)

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

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

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

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

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