ФАСТ

FASTA — это программный пакет для выравнивания последовательностей ДНК и белков , впервые описанный Дэвидом Дж. Липманом и Уильямом Р. Пирсоном в 1985 году. ^[1] Его наследием является формат FASTA , который в настоящее время повсеместно используется в биоинформатике .

Первоначальная программа FASTA была разработана для поиска сходства последовательностей белков. Из-за экспоненциально расширяющейся генетической информации и ограниченной скорости и памяти компьютеров в 1980-х годах были введены эвристические методы выравнивания последовательности запроса ко всем базам данных. FASTA, опубликованная в 1987 году, добавила возможность выполнять поиск ДНК:ДНК, транслировать поиски белок:ДНК, а также предоставила более сложную программу перетасовки для оценки статистической значимости. ^[2] В этом пакете есть несколько программ, которые позволяют выравнивать последовательности белков и последовательности ДНК. В настоящее время возросшая производительность компьютеров позволяет выполнять поиск для обнаружения локального выравнивания в базе данных с использованием алгоритма Смита-Уотермана .

FASTA произносится как «fast A» и расшифровывается как «FAST-All», поскольку работает с любым алфавитом, являясь расширением оригинальных инструментов выравнивания «FAST-P» (белок) и «FAST-N» (нуклеотид).

Текущий пакет FASTA содержит программы для поиска белок:белок, ДНК:ДНК, белок:транслированная ДНК (со сдвигами рамок) и упорядоченных или неупорядоченных пептидов. Последние версии пакета FASTA включают специальные алгоритмы транслируемого поиска, которые правильно обрабатывают ошибки сдвига рамок (которые не очень хорошо обрабатываются шестикадровыми транслируемыми поисками) при сравнении данных последовательности нуклеотида с данными последовательности белка.

Помимо методов быстрого эвристического поиска, пакет FASTA предоставляет SSEARCH — реализацию оптимального алгоритма Смита–Уотермана .

Основной упор в пакете делается на расчет точной статистики сходства, чтобы биологи могли судить, произошло ли выравнивание случайно или его можно использовать для вывода гомологии . Пакет FASTA доступен в Университете Вирджинии ^[3] и Европейском институте биоинформатики ^[4] .

Формат файла FASTA, используемый в качестве входных данных для этого программного обеспечения, в настоящее время широко используется другими инструментами поиска в базах данных последовательностей (такими как BLAST ) и программами выравнивания последовательностей ( Clustal , T-Coffee и т. д.).

FASTA берет заданную последовательность нуклеотидов или аминокислот и выполняет поиск в соответствующей базе данных последовательностей, используя локальное выравнивание последовательностей для поиска совпадений с похожими последовательностями в базе данных.

Программа FASTA следует в значительной степени эвристическому методу, который способствует высокой скорости ее выполнения. Сначала она наблюдает за шаблоном словесных совпадений, словесных совпадений заданной длины и отмечает потенциальные совпадения перед выполнением более трудоемкого оптимизированного поиска с использованием алгоритма типа Смита-Уотермана .

Размер, принимаемый за слово, заданный параметром kmer, управляет чувствительностью и скоростью программы. Увеличение значения k-mer уменьшает количество фоновых совпадений, которые находятся. Из возвращаемых словесных совпадений программа ищет сегменты, которые содержат кластер соседних совпадений. Затем она исследует эти сегменты на предмет возможного совпадения.

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

• Определите области с наибольшей плотностью в каждом сравнении последовательностей. Принимая k-мер равным 1 или 2.

На этом этапе все или группа идентичностей между двумя последовательностями находятся с помощью таблицы поиска. Значение k-mer определяет, сколько последовательных идентичностей требуется для объявления соответствия. Таким образом, чем меньше значение k-mer, тем чувствительнее поиск. k-mer=2 часто используется пользователями для последовательностей белков, а kmer=4 или 6 для последовательностей нуклеотидов. Короткие олигонуклеотиды обычно запускаются с k-mer= 1. Затем программа находит все похожие локальные области , представленные в виде диагоналей определенной длины на точечной диаграмме, между двумя последовательностями, подсчитывая совпадения k-mer и штрафуя за промежуточные несовпадения. Таким образом, локальные области с самой высокой плотностью совпадений в диагонали изолируются от фоновых совпадений. Для последовательностей белков значения BLOSUM50 используются для оценки совпадений k-mer. Это гарантирует, что группы идентичностей с высокими оценками сходства вносят больший вклад в локальную диагональную оценку, чем идентичности с низкими оценками сходства. Нуклеотидные последовательности используют матрицу идентичности для той же цели. Лучшие 10 локальных регионов, выбранных из всех диагоналей, объединенных вместе, затем сохраняются.

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

Повторно просканируйте 10 взятых регионов. На этот раз используйте соответствующую матрицу оценок при повторной оценке, чтобы разрешить прогоны идентичностей короче значения k-mer. Также при повторной оценке берутся консервативные замены, которые вносят вклад в оценку сходства. Хотя белковые последовательности используют матрицу BLOSUM50 , матрицы оценок, основанные на минимальном количестве изменений оснований, необходимых для конкретной замены, только на идентичностях или на альтернативной мере сходства, такой как PAM , также могут использоваться с программой. Для каждой из диагональных областей, повторно просканированных таким образом, определяется подрегион с максимальной оценкой. Начальные оценки, найденные на шаге 1, используются для ранжирования последовательностей библиотеки. Наивысшая оценка называется оценкой init1 .

• Если при выравнивании найдено несколько начальных регионов с оценками, превышающими значение CUTOFF, проверьте, можно ли объединить обрезанные начальные регионы для формирования приблизительного выравнивания с пробелами. Рассчитайте оценку сходства, которая является суммой объединенных регионов, штрафуя за каждый пробел 20 баллов. Эта начальная оценка сходства ( initn ) используется для ранжирования последовательностей библиотеки. Сообщается оценка единственного лучшего начального региона, найденного на шаге 2 ( init1 ).

Здесь программа вычисляет оптимальное выравнивание начальных регионов как комбинацию совместимых регионов с максимальным счетом. Это оптимальное выравнивание начальных регионов можно быстро вычислить с помощью алгоритма динамического программирования. Полученный счет initn используется для ранжирования последовательностей библиотеки. Этот процесс объединения увеличивает чувствительность, но снижает селективность. Таким образом, тщательно рассчитанное пороговое значение используется для управления тем, где этот шаг реализуется, значение, которое примерно на одно стандартное отклонение выше среднего счета, ожидаемого от неродственных последовательностей в библиотеке. Последовательность запроса из 200 остатков с k-mer 2 использует значение 28.

• Используйте алгоритм Смита-Уотермана с полосами для расчета оптимальной оценки выравнивания.

Этот шаг использует алгоритм Смита-Уотермана с полосами для создания оптимизированной оценки ( opt ) для каждого выравнивания последовательности запроса с последовательностью базы данных (библиотеки). Для расчета оптимального выравнивания берется полоса из 32 остатков, центрированная на области init1 шага 2. После поиска по всем последовательностям программа строит гистограмму начальных оценок каждой последовательности базы данных и вычисляет статистическую значимость оценки "opt". Для последовательностей белков окончательное выравнивание производится с использованием полного выравнивания Смита-Уотермана . Для последовательностей ДНК предоставляется выравнивание с полосами.

FASTA может удалять области сложности перед выравниванием последовательностей, кодируя области низкой сложности в нижнем регистре и используя опцию -S. Однако программа BLAST предлагает больше возможностей для исправления смещенной статистики состава. Поэтому программа PRSS добавлена ​​в дистрибутив FASTA. PRSS перемешивает совпадающие последовательности в базе данных либо на уровне одной буквы, либо перемешивает короткие сегменты, длину которых может определить пользователь. Перемешанные последовательности теперь снова выровнены, и если оценка все еще выше ожидаемой, это вызвано тем, что области низкой сложности смешиваются, все еще отображаясь на запрос. По величине оценки перемешанные последовательности все еще достигают PRSS теперь может предсказать значимость оценки исходных последовательностей. Чем выше оценка перемешанных последовательностей, тем менее значимы совпадения, найденные между исходной базой данных и последовательностью запроса. ^[5]

Программы FASTA находят области локального или глобального сходства между последовательностями белков или ДНК, либо путем поиска в базах данных белков или ДНК, либо путем выявления локальных дупликаций в последовательности. Другие программы предоставляют информацию о статистической значимости выравнивания. Как и BLAST, FASTA может использоваться для вывода функциональных и эволюционных связей между последовательностями, а также для помощи в идентификации членов семейств генов.

• ВЗРЫВ
• Формат FASTA
• Выравнивание последовательности
• Программное обеспечение для выравнивания последовательностей
• Инструмент профилирования последовательностей