Быстрое статистическое выравнивание

ФСА
Разработчик(и)	Роберт Брэдли ( Калифорнийский университет в Беркли ), Колин Дьюи ( Калифорнийский университет в Мэдисоне ), Лиор Пэчтер ( Калифорнийский университет в Беркли )
Стабильная версия	1.5.2
Операционная система	UNIX , Linux , Mac
Тип	Инструмент биоинформатики
Лицензия	Открытый исходный код

Быстрое статистическое выравнивание или FSA — это программа выравнивания нескольких последовательностей для выравнивания многих белков, РНК или длинных последовательностей геномной ДНК . Наряду с MUSCLE и MAFFT , FSA является одной из немногих программ выравнивания последовательностей, которая может выравнивать наборы данных, состоящие из сотен или тысяч последовательностей. FSA использует другой критерий оптимизации, который позволяет ему более надежно идентифицировать негомологичные последовательности, чем другие программы, хотя эта повышенная точность достигается за счет снижения скорости.

FSA в настоящее время используется для нескольких проектов, включая секвенирование новых геномов червей и анализ связывания транскрипционных факторов in vivo у мух.

Ввод/вывод

Эта программа принимает последовательности в формате FASTA и выводит результаты выравнивания в формате FASTA или Стокгольмском формате .

Алгоритм

Алгоритм выравнивания входных последовательностей состоит из 4 основных компонентов.

Парная скрытая марковская модель для генерации апостериорных вероятностей

Алгоритм начинается сначала с определения апостериорных вероятностей выравнивания. $\mathbb {P} (A|X,Y)$ между любыми двумя случайными последовательностями из пула выравниваемых последовательностей. Апостериорные вероятности для каждого столбца усиливают прогноз вероятности выравнивания между парой последовательностей, а также отфильтровывают столбцы, которые могут быть ненадежно выровнены. Эти вероятности также позволяют прогнозировать и оценивать гомологию между любой парой последовательностей. Стандартная скрытая модель Маркова с парой пяти состояний (Пара HMM) используется для определения этих апостериорных вероятностей выравнивания для любых двух входных последовательностей. Модель Pair HMM использует два набора состояний «Удалить» (D) и «Вставить» (I) для учета удаления и вставки символов между двумя выровненными последовательностями, но она также может иметь три состояния без значительной потери точности.

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

Объединение вероятностей

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

Последовательный отжиг

Большинство существующих программ, использующих несколько алгоритмов выравнивания последовательностей, основаны на прогрессивном выравнивании, при котором процесс начинается с «нулевого выравнивания», состояния, когда ни одна из последовательностей не была выровнена. Затем пул последовательностей выравнивается либо посредством парных сравнений, либо посредством выравнивания пары частичных выравниваний подпоследовательностей. Этот процесс может вызвать проблемы с выравниванием, поскольку результирующее множественное выравнивание последовательностей может и будет сильно зависеть от последовательностей, которые выровнены в начале. Не существует перестройки ранее выровненных последовательностей, которая могла бы исправить MSA.

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

Метод отжига последовательностей, определяя выравнивание с минимальным ожидаемым расстоянием до истины, наоборот, находит выравнивание с максимальной ожидаемой точностью. Точность выравнивания зависит от «истинного» выравнивания в качестве эталона и указывает долю столбцов, в которых последовательности гомологичны. Эта точность затем используется как целевая функция, которая начинается с невыровненных последовательностей (нулевое выравнивание) и выравнивает символы в разных столбцах на основе возрастающей точности выравнивания.

Заказ выравнивания

FSA выравнивает несколько последовательностей на основе гомологии внутри столбцов, а не строго с учетом делений и замен. Таким образом, FSA считает выравнивания эквивалентными, если для каждой позиции последовательностей в обоих выравниваниях можно сделать одно и то же утверждение о гомологии. Например, при рассмотрении парных сравнений, если в определенном положении в двух выравниваниях имеется пробел, можно сказать, что две сравниваемые последовательности не являются гомологичными в указанном положении. Это может привести к совпадению, при котором события открытия разрыва могут различаться, но при этом считаться эквивалентными. Таким образом, FSA предпочитает выводить трассу, в которой имеется минимальное количество «зазоров».

Распараллеливание

Для обработки слишком больших наборов данных FSA может разделить работу по выполнению всех необходимых парных сравнений и выравниваний на разные процессоры. Это решается с помощью стратегии «фрагментирования фиксированного размера», которая распределяет попарные сравнения по каждому доступному процессору по частям. Таким образом, каждый процессор может выполнить вычисление апостериорной вероятности для фрагмента парных сравнений перед объединением собранных данных обратно в один процессор для отжига последовательности.

Визуализация

Результаты множественного выравнивания последовательностей с помощью FSA могут отображаться в собственном графическом интерфейсе FSA. Графический интерфейс может отображать и помечать цветом различные показатели качества выравнивания в столбцах символов внутри самого выравнивания. Пять различных показателей, которые можно наблюдать и аппроксимировать в рамках модели FSA, включают точность, чувствительность, достоверность, специфичность и последовательность.

Сравнение с другими программами

FSA сравнивался с многочисленными базами данных выравнивания белков (SABmark 1.65 и BAliBASE 3), РНК (BRAliBase 2.1 и Consanmix80) и последовательностей ДНК. Эти тесты проводились наряду с другими популярными программами выравнивания, такими как ClustalW, MAFFT, MUSCLE, T-Coffee и так далее. В целом, на момент получения реферата и исследовательской работы FSA для рассмотрения FSA превзошла большинство программ выравнивания по точности и положительной прогностической ценности, а чувствительность была на одном уровне с более эффективными программами, такими как MAFFT и ProbConsRNA. Также проводились сравнения времени выполнения путем сравнения времени выравнивания рибосомных последовательностей 16S. MAFFT выполнил выравнивание быстрее, чем другие программы выравнивания, в то время как MUSCLE и FSA (с использованием HMM с 3 состояниями и с отключенным итеративным уточнением) были следующими по скорости программами.

Ссылки

Брэдли Р.К., Робертс А., Смут М., Ювекар С., До Дж., Дьюи С., Холмс И., Пахтер Л. (2009). «Быстрое статистическое выравнивание» . PLOS Вычислительная биология . 5 (5): e1000392. Бибкод : 2009PLSCB...5E0392B . дои : 10.1371/journal.pcbi.1000392 . ПМЦ 2684580 . ПМИД 19478997 .

Шварц А.С., Пахтер Л. (2007)Множественное выравнивание путем отжига последовательностей. Биоинформатика 23: e24-9.

Эдди С.Р. Множественное выравнивание с использованием скрытых марковских моделей. Proc Int Conf Intell Syst Mol Biol. 1995;3:114-20. ПМИД 7584426.

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