FASTA: Пакет программ для выравнивания последовательностей ДНК и белков

Введение

Пакет программ FASTA

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

История

Первоначальная программа FASTA была разработана для поиска сходства между последовательностями белков. В связи с экспоненциально растущим объемом генетической информации и ограниченными вычислительными мощностями компьютеров в 1980-х годах, для выравнивания запросной последовательности по целым базам данных стали использоваться эвристические методы. FASTA, опубликованная в 1987 году, добавила возможность поиска ДНК:ДНК, поиска белка, транслированного в ДНК, а также предоставила более совершенную программу перетасовки для оценки статистической значимости. В состав этого пакета входят несколько программ, позволяющих выравнивать последовательности белков и ДНК. В настоящее время возросшая производительность компьютеров позволяет выполнять поиск локальных выравниваний в базе данных с использованием алгоритма Смита–Уотермана. FASTA произносится как "фаст А" и расшифровывается как "FAST All" (Быстрый Все), поскольку работает с любым алфавитом, являясь расширением оригинальных инструментов выравнивания "FAST P" (белок) и "FAST N" (нуклеотид).

Применение

Нынешний пакет FASTA содержит программы для поиска белок-белок, ДНК-ДНК, белок-транслированная ДНК (с учетом сдвига рамки считывания) и упорядоченных или неупорядоченных пептидов. Новые версии пакета FASTA включают специальные алгоритмы поиска, которые корректно обрабатывают ошибки сдвига рамки считывания (что плохо удается шестирамковым поискам) при сравнении нуклеотидных и белковых последовательностей. Помимо быстрых эвристических методов поиска, пакет FASTA предоставляет SSEARCH – реализацию оптимального алгоритма Смита-Ватермана. Основное внимание в пакете уделяется вычислению точной статистики сходства, чтобы биологи могли оценить, является ли выравнивание результатом случайности или может быть использовано для установления гомологии. Пакет FASTA доступен в Университете Вирджинии и Европейском институте биоинформатики. Формат файла FASTA, используемый в качестве входных данных для этого программного обеспечения, широко применяется и другими инструментами поиска в базах данных последовательностей (например, BLAST) и программами выравнивания последовательностей (Clustal, T-Coffee и др.).

Метод поиска

FASTA принимает заданную нуклеотидную или аминокислотную последовательность и осуществляет поиск в соответствующей базе данных последовательностей, используя локальное выравнивание последовательностей для обнаружения совпадений с похожими последовательностями в базе данных. Программа FASTA в значительной степени использует эвристический метод, что способствует высокой скорости ее работы. Изначально она анализирует паттерн совпадений слов, то есть совпадений слов заданной длины, и отмечает потенциальные соответствия, прежде чем выполнять более трудоемкий оптимизированный поиск с использованием алгоритма, подобного алгоритму Смита-Ватермана. Размер слова, задаваемый параметром kmer, определяет чувствительность и скорость программы. Увеличение значения kmer уменьшает количество фоновых совпадений. Из найденных совпадений слов программа ищет сегменты, содержащие кластеры близлежащих совпадений. Затем она исследует эти сегменты на предмет возможного соответствия. Существуют некоторые различия между fastn и fastp, связанные с типом используемых последовательностей, но обе программы используют четыре этапа и вычисляют три оценки для описания и форматирования результатов сходства последовательностей. Это:

– определение областей с наибольшей плотностью в каждом сравнении последовательностей, принимая kmer равным 1 или 2. На этом этапе все или группа идентичностей между двумя последовательностями находятся с использованием таблицы поиска. Значение kmer определяет, сколько последовательных идентичностей требуется для объявления совпадения. Таким образом, чем меньше значение kmer, тем чувствительнее поиск. Значение kmer=2 часто используется для белковых последовательностей, а kmer=4 или 6 – для нуклеотидных последовательностей. Короткие олигонуклеотиды обычно запускаются со значением kmer=1. Затем программа находит все похожие локальные области, представленные диагоналями определенной длины на точечном графике, между двумя последовательностями, подсчитывая совпадения kmer и наказывая за промежуточные несовпадения. Таким образом, локальные области с наибольшей плотностью совпадений на диагонали выделяются из фоновых совпадений. Для оценки совпадений kmer для белковых последовательностей используются значения BLOSUM50. Это гарантирует, что группы идентичностей с высокими показателями сходства вносят больший вклад в диагональную оценку, чем идентичности с низкими показателями сходства. Нуклеотидные последовательности используют матрицу идентичности для той же цели. Затем сохраняются 10 лучших локальных областей, отобранных из всех диагоналей. Повторное сканирование областей с использованием оценочных матриц и обрезка концов области, чтобы включить только те участки, которые вносят наибольший вклад в оценку. Повторное сканирование 10 выбранных областей, на этот раз используя соответствующую оценочную матрицу при повторной оценке, чтобы разрешить серии идентичностей короче значения kmer. Также при повторной оценке учитываются консервативные замены, которые вносят вклад в оценку сходства. Хотя для белковых последовательностей используется матрица BLOSUM50, в программе также могут использоваться оценочные матрицы, основанные на минимальном количестве изменений оснований, необходимых для конкретной замены, на идентичности или на альтернативной мере сходства, такой как PAM. Для каждого из диагональных регионов, просканированных таким образом, определяется подрегион с максимальной оценкой. Начальные оценки, полученные на этапе 1, используются для ранжирования последовательностей библиотеки. Наивысшая оценка называется init1. Если в выравнивании обнаружено несколько начальных регионов с оценками, превышающими значение CUTOFF, проверяется, можно ли объединить урезанные начальные регионы для формирования приблизительного выравнивания с пробелами. Вычисляется оценка сходства, которая является суммой объединенных регионов с вычетом 20 баллов за каждый пробел. Эта начальная оценка сходства (initn) используется для ранжирования последовательностей библиотеки. Сообщается оценка наилучшего начального региона, найденного на этапе 2 (init1). Здесь программа вычисляет оптимальное выравнивание начальных регионов как комбинацию совместимых регионов с максимальной оценкой. Это оптимальное выравнивание начальных регионов может быть быстро вычислено с использованием алгоритма динамического программирования. Полученная оценка initn используется для ранжирования последовательностей библиотеки. Этот процесс объединения повышает чувствительность, но снижает селективность. Поэтому используется тщательно рассчитанное пороговое значение для контроля реализации этого этапа, значение, которое примерно на одно стандартное отклонение выше среднего балла, ожидаемого от неродственных последовательностей в библиотеке. Для запросной последовательности длиной 200 остатков с kmer 2 используется значение 28. Используется алгоритм полосного выравнивания Смита-Ватермана для вычисления оптимальной оценки выравнивания. На этом этапе используется алгоритм полосного выравнивания Смита-Ватермана для создания оптимизированной оценки (opt) для каждого выравнивания запросной последовательности с последовательностью базы данных (библиотеки). Для вычисления оптимального выравнивания используется полоса шириной 32 остатка, центрированная вокруг региона init1 на этапе 2. После поиска всех последовательностей программа строит гистограмму начальных оценок каждой последовательности базы данных и вычисляет статистическую значимость оценки "opt". Для белковых последовательностей окончательное выравнивание выполняется с использованием полного выравнивания Смита-Ватермана. Для ДНК-последовательностей предоставляется полосное выравнивание. FASTA может удалять сложные регионы перед выравниванием последовательностей, кодируя регионы низкой сложности строчными буквами и используя опцию S. Однако программа BLAST предлагает больше возможностей для коррекции смещенной статистики состава. Поэтому в пакет распространения FASTA добавлена программа PRSS. PRSS перемешивает соответствующие последовательности в базе данных либо на уровне одной буквы, либо перемешивает короткие сегменты, длину которых может определить пользователь. Перемешанные последовательности снова выравниваются, и если оценка все еще выше ожидаемой, это вызвано тем, что регионы низкой сложности все еще отображаются на запрос. По величине оценки, которую все еще получают перемешанные последовательности, PRSS теперь может предсказать значимость оценки исходных последовательностей. Чем выше оценка перемешанных последовательностей, тем менее значимы совпадения, найденные между исходной базой данных и запросной последовательностью. Программы FASTA находят области локального или глобального сходства между белковыми или ДНК-последовательностями, либо путем поиска в белковых или ДНК-базах данных, либо путем идентификации локальных дупликаций внутри последовательности. Другие программы предоставляют информацию о статистической значимости выравнивания. Как и BLAST, FASTA можно использовать для вывода функциональных и эволюционных взаимосвязей между последовательностями, а также для помощи в идентификации членов семейств генов.

Identify regions of highest density in each sequence comparison. Taking a k mer to equal 1 or 2. In this step all or a group of the identities between two sequences are found using a look up table. The k mer value determines how many consecutive identities are required for a match to be declared. Thus the lesser the k mer value: the more sensitive the search. k mer=2 is frequently taken by users for protein sequences and kmer=4 or 6 for nucleotide sequences. Short oligonucleotides are usually run with k mer= 1. The program then finds all similar local regions, represented as diagonals of a certain length in a dot plot, between the two sequences by counting k mer matches and penalizing for intervening mismatches. This way, local regions of highest density matches in a diagonal are isolated from background hits. For protein sequences BLOSUM50 values are used for scoring k mer matches. This ensures that groups of identities with high similarity scores contribute more to the local diagonal score than to identities with low similarity scores. Nucleotide sequences use the identity matrix for the same purpose. The best 10 local regions selected from all the diagonals put together are then saved. Rescan the regions taken using the scoring matrices. trimming the ends of the region to include only those contributing to the highest score. Rescan the 10 regions taken. This time use the relevant scoring matrix while rescoring to allow runs of identities shorter than the k mer value. Also while rescoring conservative replacements that contribute to the similarity score are taken. Though protein sequences use the BLOSUM50 matrix, scoring matrices based on the minimum number of base changes required for a specific replacement, on identities alone, or on an alternative measure of similarity such as PAM, can also be used with the program. For each of the diagonal regions rescanned this way, a subregion with the maximum score is identified. The initial scores found in step1 are used to rank the library sequences. The highest score is referred to as init1 score. In an alignment if several initial regions with scores greater than a CUTOFF value are found, check whether the trimmed initial regions can be joined to form an approximate alignment with gaps. Calculate a similarity score that is the sum of the joined regions penalising for each gap 20 points. This initial similarity score (initn) is used to rank the library sequences. The score of the single best initial region found in step 2 is reported (init1). Here the program calculates an optimal alignment of initial regions as a combination of compatible regions with maximal score. This optimal alignment of initial regions can be rapidly calculated using a dynamic programming algorithm. The resulting score initn is used to rank the library sequences. This joining process increases sensitivity but decreases selectivity. A carefully calculated cut off value is thus used to control where this step is implemented, a value that is approximately one standard deviation above the average score expected from unrelated sequences in the library. A 200 residue query sequence with k mer 2 uses a value 28. Use a banded Smith–Waterman algorithm to calculate an optimal score for alignment. This step uses a banded Smith–Waterman algorithm to create an optimised score (opt) for each alignment of query sequence to a database(library) sequence. It takes a band of 32 residues centered on the init1 region of step2 for calculating the optimal alignment. After all sequences are searched the program plots the initial scores of each database sequence in a histogram, and calculates the statistical significance of the "opt" score. For protein sequences, the final alignment is produced using a full Smith–Waterman alignment. For DNA sequences, a banded alignment is provided. FASTA can remove complexity regions before aligning the sequences by encoding low complexity regions in lower case and using the S option. However, the BLAST program offers more options for correcting for biased composition statistics. Therefore, the program PRSS is added in the FASTA distribution package. PRSS shuffles the matching sequences in the database either on the one letter level or it shuffles short segments which length the user can determine. The shuffled sequences are now aligned again and if the score is still higher than expected this is caused by the low complexity regions being mixed up still mapping to the query. By the amount of the score the shuffled sequences still attain PRSS now can predict the significance of the score of the original sequences. The higher the score of the shuffled sequences the less significant the matches found between original database and query sequence. The FASTA programs find regions of local or global similarity between Protein or DNA sequences, either by searching Protein or DNA databases, or by identifying local duplications within a sequence. Other programs provide information on the statistical significance of an alignment. Like BLAST, FASTA can be used to infer functional and evolutionary relationships between sequences as well as help identify members of gene families.