FASTA - это программный пакет для выравнивания последовательностей ДНК и белков, впервые описанный Дэвидом Дж. Липманом и Уильямом Р. Пирсоном в 1985 году. [1] Его наследием является формат FASTA, который теперь повсеместно используется в биоинформатике .
Разработчики) | |
---|---|
Стабильный выпуск | 36 |
Репозиторий | |
Операционная система | |
Тип | Биоинформатика |
Лицензия | apache2.0 |
Веб-сайт |
История
Первоначальная программа FASTP была разработана для поиска сходства последовательностей белков. Из-за экспоненциально расширяющейся генетической информации и ограниченной скорости и памяти компьютеров в 1980-х годах были введены эвристические методы для согласования последовательности запроса со всеми базами данных. FASTA, опубликованная в 1987 году, добавила возможность выполнять поиск ДНК: ДНК, транслированный белок: поиск ДНК, а также предоставила более сложную программу перетасовки для оценки статистической значимости. [2] В этом пакете есть несколько программ, которые позволяют выравнивать последовательности белков и последовательностей ДНК. В настоящее время повышенная производительность компьютера позволяет выполнять поиск по обнаружению локального выравнивания в базе данных с использованием алгоритма Смита – Уотермана .
FASTA произносится как «быстрый 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-мер. Это гарантирует, что группы идентичностей с высокими оценками сходства вносят больший вклад в локальную диагональную оценку, чем в идентичности с низкими оценками сходства. Нуклеотидные последовательности используют матрицу идентичности для той же цели. Затем сохраняются 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 не может удалить области низкой сложности перед выравниванием последовательностей, как это возможно с помощью BLAST. Это может быть проблематично, поскольку, когда последовательность запроса содержит такие области, например мини- или микросателлиты, часто повторяющие одну и ту же короткую последовательность, это увеличивает количество незнакомых последовательностей в базе данных, которые совпадают только в этих повторах, которые встречаются довольно часто. Поэтому программа PRSS добавлена в дистрибутив FASTA. PRSS перемешивает совпадающие последовательности в базе данных либо на однобуквенном уровне, либо перемешивает короткие сегменты, длину которых может определить пользователь. Перетасованные последовательности теперь снова выровнены, и если оценка все еще выше, чем ожидалось, это вызвано тем, что области низкой сложности перемешаны, все еще отображаются в запросе. По количеству баллов перемешанные последовательности все еще достигают PRSS, теперь можно предсказать значимость баллов исходных последовательностей. Чем выше оценка перетасованных последовательностей, тем менее значимы совпадения, найденные между исходной базой данных и последовательностью запроса. [5]
Программы FASTA находят области локального или глобального сходства между последовательностями белков или ДНК либо путем поиска в базах данных белков или ДНК, либо путем выявления локальных дупликаций в последовательности. Другие программы предоставляют информацию о статистической значимости выравнивания. Подобно BLAST, FASTA может использоваться для вывода функциональных и эволюционных отношений между последовательностями, а также для помощи в идентификации членов семейств генов.
Смотрите также
- ВЗРЫВ
- Формат FASTA
- Выравнивание последовательности
- Программное обеспечение для выравнивания последовательностей
- Инструмент профилирования последовательности
Рекомендации
- ^ Липман, DJ; Пирсон, WR (1985). «Быстрые и чувствительные поиски сходства белков». Наука . 227 (4693): 1435–41. Bibcode : 1985Sci ... 227.1435L . DOI : 10.1126 / science.2983426 . PMID 2983426 .
- ^ Пирсон, WR; Липман, DJ (1988). «Улучшенные инструменты для сравнения биологических последовательностей» . Труды Национальной академии наук Соединенных Штатов Америки . 85 (8): 2444–8. Bibcode : 1988PNAS ... 85.2444P . DOI : 10.1073 / pnas.85.8.2444 . PMC 280013 . PMID 3162770 .
- ^ http://fasta.bioch.virginia.edu
- ^ https://www.ebi.ac.uk/Tools/fasta
- ^ Дэвид В. Маунт: Биоинформатический анализ последовательности и генома , издание 1, издательство Cold Spring Harbor Laboratory Press, 2001, стр. 295–297.