Быстрое статистическое выравнивание или FSA — это программа множественного выравнивания последовательностей для выравнивания множества белков, РНК или длинных геномных последовательностей ДНК . Наряду с MUSCLE и MAFFT , FSA — одна из немногих программ выравнивания последовательностей, которая может выравнивать наборы данных из сотен или тысяч последовательностей. FSA использует другой критерий оптимизации, который позволяет ей более надежно идентифицировать негомологичные последовательности, чем эти другие программы, хотя эта повышенная точность достигается за счет снижения скорости.
В настоящее время FSA используется в нескольких проектах, включая секвенирование новых геномов червей и анализ связывания факторов транскрипции in vivo у мух.
Эта программа принимает последовательности в формате FASTA и выводит выравнивания в формате FASTA или Стокгольмском формате .
Алгоритм выравнивания входных последовательностей состоит из 4 основных компонентов.
Алгоритм начинается с определения апостериорных вероятностей выравнивания между любыми двумя случайными последовательностями из пула выравниваемых последовательностей. Апостериорные вероятности для каждого столбца усиливают прогноз вероятности выравнивания между парой последовательностей, а также отфильтровывают столбцы, которые могут быть ненадежно выровнены. Эти вероятности также позволяют прогнозировать и оценивать гомологию между любой парой последовательностей. Стандартная пятисостоянная парная скрытая марковская модель (Pair HMM) используется для определения этих апостериорных вероятностей выравнивания для любых двух входных последовательностей. Модель Pair HMM использует два набора состояний Delete (D) и Insert (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 (использующие 3-ступенчатую HMM и с отключенным итеративным уточнением) были следующими по скорости программами.
Брэдли РК, Робертс А, Смут М, Ювекар С, До Дж, Дьюи К, Холмс И, Пахтер Л (2009). "Быстрое статистическое выравнивание". PLOS Computational Biology . 5 (5): e1000392. Bibcode : 2009PLSCB...5E0392B. doi : 10.1371/journal.pcbi.1000392 . PMC 2684580. PMID 19478997 .
Шварц АС, Пахтер Л (2007) Множественное выравнивание с помощью отжига последовательностей. Биоинформатика 23: e24-9.
Eddy SR. Множественное выравнивание с использованием скрытых марковских моделей. Proc Int Conf Intell Syst Mol Biol. 1995;3:114-20. PMID 7584426.
