BLAST (биотехнология) - BLAST (biotechnology)

Эта статья о программном инструменте биоинформатики. Для использования в других целях см. Взрыв (значения).

ВЗРЫВ

Оригинальный автор (ы)	Стивен Альтшул, Уоррен Гиш, Уэбб Миллер, Юджин Майерс, и Дэвид Липман
Разработчики)	NCBI
Стабильный выпуск	2.11.0+ / 3 ноября 2020; 30 дней назад (2020-11-03)
Написано в	C и C ++[1]
Операционная система	UNIX, Linux, Mac, MS-Windows
Тип	Биоинформатика орудие труда
Лицензия	Всеобщее достояние
Интернет сайт	взрыв.ncbi.nlm.Национальные институты здравоохранения США.gov/ Взрыв.cgi

В биоинформатика, ВЗРЫВ (базовый инструмент поиска местного выравнивания)^[2] является алгоритм и программа для сравнения первичный информация о биологической последовательности, такая как аминокислота последовательности белки или нуклеотиды из ДНК и / или РНК последовательности. Поиск BLAST позволяет исследователю сравнить исследуемый белок или нуклеотидную последовательность (называемую запросом) с библиотекой или база данных последовательностей и идентифицируют библиотечные последовательности, которые напоминают последовательность запроса выше определенного порога.

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

Задний план

BLAST, который Нью-Йорк Таймс называется Google биологических исследований,^[2] - одна из наиболее широко используемых программ биоинформатики для поиска последовательностей.^[3] Он обращается к фундаментальной проблеме исследований в области биоинформатики. В эвристический алгоритм, который он использует, намного быстрее, чем другие подходы, такие как расчет оптимального выравнивания. Этот акцент на скорости жизненно важен для практического использования алгоритма в огромных базах данных генома, доступных в настоящее время, хотя последующие алгоритмы могут быть даже быстрее.

Перед BLAST, FASTA был разработан Дэвидом Дж. Липманом и Уильямом Р. Пирсоном в 1985 году.^[4]

До появления быстрых алгоритмов, таких как BLAST и FASTA были разработаны, поиск в базах данных белковых или нуклеиновых последовательностей занимал очень много времени, потому что процедура полного выравнивания (например, Алгоритм Смита – Уотермана ) было использовано.

BLAST произошел от стохастической модели 1990 г. Сэмюэл Карлин и Стивен Альтшул^[5] Они «предложили метод оценки сходства между известной последовательностью ДНК одного организма и другой»,^[2] и их работа была описана как «статистическая основа для BLAST».^[6] Впоследствии Альтшул вместе с Уоррен Гиш, Уэбб Миллер, Юджин Майерс, и Дэвид Дж. Липман на Национальные институты здоровья разработал алгоритм BLAST, который был опубликован в Журнал молекулярной биологии в 1990 г. и цитировалось более 75 000 раз.^[7]

Хотя BLAST в большинстве случаев быстрее, чем любая реализация Смита-Ватермана, он не может «гарантировать оптимальное выравнивание последовательностей запроса и базы данных», как это делает алгоритм Смита-Ватермана. Оптимальность Smith-Waterman «обеспечила наилучшие характеристики точности и самые точные результаты» за счет времени и мощности компьютера.

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

Примеры других вопросов, на которые исследователи используют BLAST, чтобы ответить:

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

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

BLAST доступен в Интернете на сайте NCBI. Альтернативные реализации включают AB-BLAST (ранее известный как WU-BLAST), FSA-BLAST (последнее обновление в 2006 г.) и ScalaBLAST.^[8][9]

Оригинальная статья Альтшула, и другие.^[7] была самой цитируемой статьей, опубликованной в 1990-х годах.^[10]

Ввод

Входные последовательности (в FASTA или Генбанк формат) и весовая матрица.

Вывод

Выходные данные BLAST могут быть предоставлены в различных форматах. Эти форматы включают HTML, простой текст, и XML форматирование. Для веб-страницы NCBI формат вывода по умолчанию - HTML. При выполнении BLAST на NCBI результаты выдаются в графическом формате, показывающем найденные совпадения, таблица, показывающая идентификаторы последовательностей для совпадений с оценочными данными, а также сопоставления для интересующей последовательности и полученных совпадений с соответствующими оценками BLAST. для этих. Самым простым для чтения и наиболее информативным из них, вероятно, является таблица.

Если кто-то пытается найти проприетарную последовательность или просто ту, которая недоступна в базах данных, доступных для широкой публики из таких источников, как NCBI, существует программа BLAST, доступная для загрузки на любой компьютер бесплатно. Это можно найти в исполняемых файлах BLAST +. Есть также коммерческие программы, доступные для покупки. Базы данных можно найти на сайте NCBI, а также в Индексе баз данных BLAST (FTP).

Обработать

С помощью эвристический BLAST находит похожие последовательности, обнаруживая короткие совпадения между двумя последовательностями. Этот процесс поиска похожих последовательностей называется раздачей. Именно после этого первого совпадения BLAST начинает выполнять локальные выравнивания. При попытке найти сходство в последовательностях очень важны наборы общих букв, известные как слова. Например, предположим, что последовательность содержит следующий отрезок букв GLKFA. Если ВЗРЫВ при нормальных условиях, размер слова - 3 буквы. В этом случае при использовании данного набора букв искомыми словами будут GLK, LKF, KFA. Эвристический алгоритм BLAST находит все общие трехбуквенные слова между интересующей последовательностью и последовательностью совпадений или последовательностями из базы данных. Этот результат затем будет использован для построения трассы. После составления слов для интересующей последовательности, остальные слова также собираются. Эти слова должны соответствовать требованию иметь оценку не ниже порога. Тпри сравнении с использованием оценочной матрицы.

Одна из часто используемых оценочных матриц для поиска BLAST - BLOSUM62,^[11] хотя оптимальная матрица оценок зависит от сходства последовательностей. Когда и слова, и соседние слова собраны и скомпилированы, они сравниваются с последовательностями в базе данных, чтобы найти совпадения. Пороговая оценка Т определяет, будет ли включено в выравнивание определенное слово. После того, как посев был проведен, выравнивание длиной всего 3 остатка расширяется в обоих направлениях с помощью алгоритма, используемого BLAST. Каждое расширение влияет на оценку выравнивания, увеличивая или уменьшая ее. Если этот балл выше заранее определенного Т, выравнивание будет включено в результаты, предоставленные BLAST. Однако, если этот балл ниже заранее определенного Т, выравнивание перестанет расширяться, предотвращая включение областей с плохим выравниванием в результаты BLAST. Обратите внимание, что увеличение Т оценка ограничивает объем пространства, доступного для поиска, уменьшая количество соседних слов, в то же время ускоряя процесс BLAST

Алгоритм

Для запуска программного обеспечения BLAST требуется последовательность запроса для поиска и последовательность для поиска (также называемая целевой последовательностью) или база данных последовательностей, содержащая несколько таких последовательностей. BLAST найдет в базе данных подпоследовательности, похожие на подпоследовательности в запросе. В типичном использовании последовательность запроса намного меньше, чем база данных, например, запрос может содержать тысячу нуклеотидов, а база данных - несколько миллиардов нуклеотидов.

Основная идея BLAST заключается в том, что часто в статистически значимом выравнивании содержатся пары сегментов с высокими показателями (HSP). BLAST ищет высокие баллы выравнивание последовательностей между последовательностью запроса и существующими последовательностями в базе данных с использованием эвристического подхода, который приближает Алгоритм Смита-Уотермана. Однако исчерпывающий подход Смита-Уотермана слишком медленный для поиска в больших геномных базах данных, таких как GenBank. Следовательно, алгоритм BLAST использует эвристический подход, который менее точен, чем алгоритм Смита-Уотермана, но более чем в 50 раз быстрее. [8] Скорость и относительно хорошая точность BLAST являются одними из ключевых технических новшеств программ BLAST.

Обзор алгоритма BLAST (поиск белка в белок) выглядит следующим образом:^[12]

1. Удалите повторы области или последовательности низкой сложности в последовательности запроса.

   «Область низкой сложности» означает область последовательности, состоящую из нескольких видов элементов. Эти области могут дать высокие баллы, которые запутают программу при поиске фактических значимых последовательностей в базе данных, поэтому их следует отфильтровать. Области будут помечены X (последовательности белка) или N (последовательности нуклеиновой кислоты), а затем будут проигнорированы программой BLAST. Чтобы отфильтровать области низкой сложности, программа SEG используется для последовательностей белков, а программа DUST - для последовательностей ДНК. С другой стороны, программа XNU используется для маскировки тандемных повторов в белковых последовательностях.

2. Сделать k-буквенный список слов в запросной последовательности.

   Взять k= 3, например, мы перечисляем слова длины 3 в последовательности белка запроса (k обычно равно 11 для последовательности ДНК) «последовательно», пока не будет включена последняя буква последовательности запроса. Метод показан на рисунке 1.

   

   Рис. 1 Методика определения k-буквенный список слов запроса.^[13]

3. Перечислите возможные совпадающие слова.

   Этот шаг - одно из основных различий между BLAST и FASTA. FASTA заботится обо всех общих словах в базе данных и последовательностях запросов, которые перечислены на шаге 2; однако BLAST заботятся только о словах с высокими оценками. Баллы создаются путем сравнения слова в списке на шаге 2 со всеми трехбуквенными словами. Используя оценочную матрицу (матрица замещения ), чтобы оценить сравнение каждой пары остатков, существует 20 ^ 3 возможных оценок соответствия для 3-буквенного слова. Например, оценка, полученная при сравнении PQG с PEG и PQA, составляет соответственно 15 и 12 с BLOSUM62 схема взвешивания. Для слов ДНК совпадение оценивается как +5, а несоответствие - как -4 или как +2 и -3. После этого порог оценки соседнего слова Т используется для уменьшения количества возможных совпадающих слов. Слова, оценка которых превышает пороговое значение Т останется в списке возможных подходящих слов, а слова с более низкими оценками будут отброшены. Например, PEG сохраняется, но PQA отменяется, когда T равно 13.

4. Организуйте оставшиеся высоко оцененные слова в эффективное дерево поиска.

   Это позволяет программе быстро сравнивать слова с высокими оценками с последовательностями базы данных.

5. Повторите шаги с 3 по 4 для каждого k-буквенное слово в запросе.
6. Просканируйте последовательности базы данных на предмет точных совпадений с оставшимися высоко оцененными словами.

   Программа BLAST сканирует последовательности базы данных на предмет оставшегося слова с высокой оценкой, такого как PEG, в каждой позиции. Если найдено точное совпадение, это совпадение используется для возможного выравнивания без пробелов между последовательностями запроса и базы данных.

7. Расширить точное совпадение до пары сегментов с высокими показателями (HSP).
   • Исходная версия BLAST растягивает более длинное выравнивание между запросом и последовательностью базы данных в левом и правом направлениях с позиции, где произошло точное совпадение. Продление не прекращается, пока общая сумма баллов HSP не начнет уменьшаться. Упрощенный пример представлен на рисунке 2.
     

     Рис. 2 Процесс продления точного совпадения. Адаптировано из анализа биологической последовательности I, Current Topics in Genome Analysis [2].
     

     Рис. 3 Расположение точных совпадений.
   • Чтобы сэкономить больше времени, была разработана новая версия BLAST, названная BLAST2 или gapped BLAST. BLAST2 принимает более низкий порог оценки соседнего слова, чтобы поддерживать тот же уровень чувствительности для обнаружения сходства последовательностей. Следовательно, список возможных совпадающих слов на шаге 3 становится длиннее. Затем точно совпадающие области на расстоянии A друг от друга на той же диагонали на рисунке 3 будут объединены в более длинную новую область. Наконец, новые области затем расширяются тем же методом, что и в исходной версии BLAST, и затем создаются оценки расширенных областей HSP (пара сегментов с высокими показателями) с использованием матрицы замещения, как и раньше.
8. Перечислите всех HSP в базе данных, оценка которых достаточно высока для рассмотрения.

   Мы перечисляем HSP, чьи баллы выше, чем эмпирически определенная пороговая оценка. S. Путем изучения распределения оценок выравнивания, смоделированных путем сравнения случайных последовательностей, оценка отсечения S можно определить так, чтобы его значение было достаточно большим, чтобы гарантировать значимость оставшихся HSP.

9. Оцените значимость оценки HSP.

   Затем BLAST оценивает статистическую значимость каждого показателя HSP, используя распределение экстремальных значений Гамбеля (EVD). (Доказано, что распределение баллов локального выравнивания Смита-Уотермана между двумя случайными последовательностями соответствует EVD Гамбеля. Для локальных выравниваний, содержащих пробелы, это не доказано.) В соответствии с EVD Гамбеля вероятность п наблюдения за счетом S равный или больший x определяется уравнением

   ${\displaystyle p\left(S\geq x\right)=1-\exp \left(-e^{-\lambda \left(x-\mu \right)}\right)}$

   где

   ${\displaystyle \mu ={\frac {\log \left(Km'n'\right)}{\lambda }}\;}$

   Статистические параметры ${\displaystyle \lambda }$ и ${\displaystyle \mathrm {K} }$ оцениваются путем подгонки распределения баллов локального выравнивания без пробелов, последовательности запроса и множества перетасованных версий (глобальная или локальная перетасовка) последовательности базы данных к распределению экстремальных значений Гамбеля. Обратите внимание, что ${\displaystyle \lambda }$ и ${\displaystyle \mathrm {K} }$ зависят от матрицы подстановки, штрафов за пропуски и композиции последовательности (частоты букв). ${\displaystyle m'}$ и ${\displaystyle n'}$ - эффективные длины последовательностей запроса и базы данных соответственно. Исходная длина последовательности сокращается до эффективной длины, чтобы компенсировать краевой эффект (начало выравнивания ближе к концу одного из запросов или последовательности базы данных, вероятно, не будет иметь достаточной последовательности для построения оптимального выравнивания). Их можно рассчитать как

   ${\displaystyle m'\approx m-{\frac {\ln Kmn}{H}}\;}$

   ${\displaystyle n'\approx n-{\frac {\ln Kmn}{H}}\;}$

   где ${\displaystyle \mathrm {H} }$ - средняя ожидаемая оценка на выровненную пару остатков при выравнивании двух случайных последовательностей. Альтшул и Гиш дали типичные значения, ${\displaystyle \lambda =0.318}$, ${\displaystyle \mathrm {K} =0.13}$, и ${\displaystyle \mathrm {H} =0.40}$, для локального выравнивания без зазора с использованием BLOSUM62 в качестве матрицы замещения. Использование типичных значений для оценки значимости называется методом справочной таблицы; это не точно. Ожидаемая оценка E совпадения базы данных - это количество раз, когда несвязанная последовательность базы данных получит оценку S выше чем Икс случайно. Ожидание E полученные при поиске базы данных D последовательности задаются

   ${\displaystyle E\approx 1-e^{-p\left(s>x\right)D}}$

   Кроме того, когда ${\displaystyle p<0.1}$, E можно было бы аппроксимировать распределением Пуассона как

   ${\displaystyle E\approx pD}$

   Это ожидание или ожидаемое значение "E" (часто называемое E оценка или E-значение или е-value), оценивающий значимость оценки HSP для локального выравнивания без зазора, сообщается в результатах BLAST. Приведенный здесь расчет изменяется, если индивидуальные HSP комбинируются, например, при создании выравниваний с разрывом (описанных ниже), из-за вариации статистических параметров.

10. Сделайте две или более областей HSP в более длинное выравнивание.

    Иногда мы обнаруживаем две или более областей HSP в одной последовательности базы данных, которые можно преобразовать в более длинное выравнивание. Это дает дополнительное свидетельство связи между запросом и последовательностью базы данных. Существует два метода: метод Пуассона и метод суммы баллов для сравнения значимости вновь объединенных областей HSP. Предположим, что есть две комбинированные области HSP с парами оценок (65, 40) и (52, 45) соответственно. Метод Пуассона придает большую значимость множеству с максимально низким баллом (45> 40). Однако метод суммы баллов предпочитает первый набор, потому что 65 + 40 (105) больше, чем 52 + 45 (97). Оригинальный BLAST использует метод Пуассона; BLAST с разрывом, а WU-BLAST использует метод суммы баллов.

11. Покажите пропущенные локальные сопоставления Смита-Уотермана запроса и каждой из совпадающих последовательностей базы данных.
    • Исходный BLAST генерирует только выравнивания без пропусков, включая изначально найденные HSP по отдельности, даже если в одной последовательности базы данных обнаружено более одного HSP.
    • BLAST2 производит единственное выравнивание с пробелами, которое может включать все первоначально обнаруженные области HSP. Обратите внимание, что вычисление оценки и соответствующее ей значение E-значение предполагает использование адекватных штрафов за пробелы.
12. Сообщать о каждом совпадении, ожидаемая оценка которого ниже порогового параметра E.

Параллельный BLAST

Параллельные версии BLAST разделенных баз данных реализованы с использованием MPI и Pthreads, и были перенесены на различные платформы, включая Windows, Linux, Солярис, Mac OS X, и AIX. Популярные подходы к распараллеливанию BLAST включают распределение запросов, сегментацию хэш-таблицы, распараллеливание вычислений и сегментацию (раздел) базы данных. Базы данных разделены на части равного размера и хранятся локально на каждом узле. Каждый запрос выполняется на всех узлах параллельно, и результирующие выходные файлы BLAST со всех узлов объединяются для получения окончательного результата. Конкретные реализации включают MPIblast, ScalaBLAST, DCBLAST и так далее.^[14]

Программа

Программа BLAST может быть загружена и запущена как утилита командной строки «blastall» или доступна бесплатно через Интернет. Веб-сервер BLAST, размещенный на NCBI, позволяет любому, у кого есть веб-браузер, выполнять поиск сходства в постоянно обновляемых базах данных белков и ДНК, которые включают большинство недавно секвенированных организмов.

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

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

BLAST - это фактически семейство программ (все они включены в исполняемый файл blastall). Они включают:^[15]

Нуклеотид-нуклеотидный BLAST (blastn)

Эта программа, получив запрос ДНК, возвращает наиболее похожие последовательности ДНК из базы данных ДНК, указанные пользователем.

Белково-протеиновый BLAST (бластп)

Эта программа при запросе белка возвращает наиболее похожие последовательности белков из база данных белков что указывает пользователь.

Итеративный BLAST с привязкой к позиции (PSI-BLAST) (blastpgp)

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

Включая связанные белки в поиск, PSI-BLAST гораздо более чувствителен к обнаружению удаленных эволюционные отношения чем стандартный белок-протеиновый BLAST.

Нуклеотидный 6-каркасный трансляционный белок (blastx)

Эта программа сравнивает продукты концептуальной трансляции с шестью рамками нуклеотидной запрашиваемой последовательности (обеих цепей) с базой данных последовательностей белков.

Нуклеотидная 6-рамочная трансляция-нуклеотидная 6-рамочная трансляция (tblastx)

Эта программа является самой медленной из семейства BLAST. Он переводит запрашиваемую нуклеотидную последовательность во все шесть возможных фреймов и сравнивает ее с шестикадровыми трансляциями из базы данных нуклеотидных последовательностей. Цель tblastx - найти очень отдаленные отношения между нуклеотидными последовательностями.

6-рамочная трансляция белок-нуклеотид (tblastn)

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

Большое количество последовательностей запросов (мегабласть)

При сравнении большого количества входных последовательностей через командную строку BLAST, «мегабласт» выполняется намного быстрее, чем запуск BLAST несколько раз. Он объединяет множество входных последовательностей вместе, чтобы сформировать большую последовательность перед поиском в базе данных BLAST, а затем анализирует результаты поиска, чтобы подобрать отдельные сопоставления и статистические значения.

Из этих программ BLASTn и BLASTp - наиболее часто используемые^{[нужна цитата ]} потому что они используют прямые сравнения и не требуют перевода. Однако, поскольку белковые последовательности эволюционно более консервативны, чем нуклеотидные последовательности, tBLASTn, tBLASTx, и BLASTx, дают более надежные и точные результаты при работе с кодирующей ДНК. Они также позволяют непосредственно увидеть функцию белковой последовательности, поскольку перевод интересующей последовательности перед поиском часто дает вам аннотированные совпадения белков.

Альтернативные версии

Версия, предназначенная для сравнения больших геномов или ДНК, BLASTZ.

CS-BLAST (Контекстно-зависимый BLAST) - это расширенная версия BLAST для поиска последовательностей белков, которая находит вдвое больше удаленно связанных последовательностей, чем BLAST, с той же скоростью и частотой ошибок. В CS-BLAST вероятность мутаций между аминокислотами зависит не только от отдельной аминокислоты, как в BLAST, но также от контекста ее локальной последовательности. Вашингтонский университет выпустил альтернативную версию NCBI BLAST под названием WU-BLAST. С тех пор права были приобретены Advanced Biocomputing, LLC.

В 2009 году NCBI выпустила новый набор исполняемых файлов BLAST, BLAST + на основе C ++, и выпустила версии C до 2.2.26.^[16] Начиная с версии 2.2.27 (апрель 2013 г.) доступны только исполняемые файлы BLAST +. Среди изменений - замена взрыв исполняемый файл с отдельными исполняемыми файлами для разных программ BLAST, а также изменения в обработке опций. В formatdb утилита (на основе C) была заменена на makeblastdb (На основе C ++) и базы данных, отформатированные любым из них, должны быть совместимы для идентичных взрывных выпусков. Алгоритмы остаются схожими, однако количество найденных совпадений и их порядок могут значительно различаться между старой и новой версией. BLAST + с

Ускоренные версии

TimeLogic предлагает FPGA -ускоренная реализация алгоритма BLAST под названием Tera-BLAST, который в сотни раз быстрее.

Другие ранее поддерживаемые версии включают:

• С ускорением на ПЛИС
  • До их приобретения Qiagen, CLC биография сотрудничал с SciEngines GmbH на ускорителе FPGA, как они утверждали, он даст 188-кратное ускорение BLAST.
  • Проект Mitrion-C Open Bio Project был попыткой перенести BLAST для работы на ПЛИС Mitrion.
• С ускорением на GPU
  • GPU-Blast^[17] это ускоренная версия NCBI BLASTP для CUDA что в 3–4 раза быстрее, чем NCBI Blast.
  • CUDA-BLASTP^[18] - это версия BLASTP с ускорением на графическом процессоре, которая, как утверждается, работает до 10 раз быстрее, чем NCBI BLAST.
  • G-BLASTN^[19] - это ускоренная версия NCBI blastn и megablast, ускорение которой варьируется от 4x до 14x (по сравнению с такими же запусками с 4 потоками ЦП). Его текущее ограничение заключается в том, что база данных должна умещаться в памяти графического процессора.
• С ускорением процессора
  • MPIBlast - это параллельная реализация NCBI BLAST с использованием Интерфейс передачи сообщений. Благодаря эффективному использованию распределенных вычислительных ресурсов посредством фрагментации базы данных, сегментации запросов, интеллектуального планирования и параллельного ввода-вывода, mpiBLAST улучшает производительность NCBI BLAST на несколько порядков при масштабировании до сотен процессоров.
  • КАБЛАСТ^[20] ускоряет поиск в больших базах данных на несколько порядков за счет использования избыточности данных.
  • Paracel BLAST был коммерческой параллельной реализацией NCBI BLAST, поддерживающей сотни процессоров.
  • QuickBLAST (kblastp) от NCBI - это реализация, ускоренная предварительной фильтрацией на основе Индекс Жаккара оценки с хешированными пентамерными фрагментами. Фильтрация немного снижает чувствительность, но увеличивает производительность на порядок.^[21] NCBI делает доступным только поиск по их неизбыточной (nr) коллекции белков и не предлагает загрузки.

Альтернативы BLAST

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

Чрезвычайно быстрая, но значительно менее чувствительная альтернатива BLAST - BLAT (Bпоследний LАйк Авыравнивание Тоол). В то время как BLAST выполняет линейный поиск, BLAT полагается на к-мер индексирует базу данных и, таким образом, может быстрее находить семена.^[22] Другая программная альтернатива, аналогичная BLAT, - PatternHunter.

Достижения в технологии секвенирования в конце 2000-х сделали поиск очень похожих нуклеотидных совпадений важной проблемой. Новые программы центровки, специально разработанные для этого использования, обычно используют BWT -индексирование целевой базы данных (обычно генома). После этого можно очень быстро отобразить входные последовательности, а выходные данные обычно имеют форму файла BAM. Примеры программ центровки: BWA, МЫЛО, и Галстук-бабочка.

Для идентификации белков поиск известных доменов (например, из Pfam ) путем сопоставления с Скрытые марковские модели это популярная альтернатива, например HMMER.

Альтернативой BLAST для сравнения двух банков последовательностей является PLAST. PLAST представляет собой высокопроизводительный универсальный инструмент поиска сходства последовательностей из банка в банк, основанный на PLAST.^[23] и ORIS^[24] алгоритмы. Результаты PLAST очень похожи на BLAST, но PLAST значительно быстрее и способен сравнивать большие наборы последовательностей с небольшим объемом памяти (то есть RAM).

Для приложений в метагеномике, где задача состоит в сравнении миллиардов коротких чтений ДНК с десятками миллионов ссылок на белки, DIAMOND^[25] работает до 20 000 раз быстрее, чем BLASTX, при сохранении высокого уровня чувствительности.

Программное обеспечение с открытым исходным кодом MMseqs является альтернативой BLAST / PSI-BLAST, которое улучшает существующие инструменты поиска по всему диапазону компромисса между скоростью и чувствительностью, обеспечивая более высокую чувствительность, чем PSI-BLAST, более чем в 400 раз от его скорости.^[26]

Оптические вычисления подходы были предложены в качестве многообещающей альтернативы текущим электрическим реализациям. OptCAM является примером таких подходов и показывает, что он быстрее, чем BLAST.^[27]

Сравнение BLAST и процесса Смита-Уотермана

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

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

Лучшей альтернативой для получения наилучших возможных результатов было бы использование алгоритма Смита-Уотермана. Этот метод отличается от метода BLAST в двух областях: точности и скорости. Вариант Смита-Уотермана обеспечивает лучшую точность, поскольку он находит совпадения, которые не может выполнить BLAST, поскольку не пропускает никакой информации. Следовательно, это необходимо для удаленной гомологии. Однако по сравнению с BLAST он требует больше времени, не говоря уже о том, что он требует большого объема использования компьютера и места. Однако было обнаружено, что технологии, ускоряющие процесс Смита-Уотермана, значительно сокращают время, необходимое для выполнения поиска. Эти технологии включают FPGA чипсы и SIMD технологии.

Чтобы получить лучшие результаты от BLAST, можно изменить настройки по умолчанию. Однако не существует заданного или установленного способа изменения этих настроек для получения наилучших результатов для данной последовательности. Доступные для изменения настройки: E-Value, стоимость пробелов, фильтры, размер слова и матрица замены. Обратите внимание, что алгоритм, используемый для BLAST, был разработан на основе алгоритма, используемого для Smith-Waterman. BLAST использует выравнивание, которое находит «локальные выравнивания между последовательностями путем поиска коротких совпадений, и из этих начальных совпадений создаются (локальные) выравнивания».^[28]

Визуализация вывода BLAST

Чтобы помочь пользователям интерпретировать результаты BLAST, доступно другое программное обеспечение. Вот некоторые доступные инструменты в зависимости от установки и использования, функций анализа и технологии:^[29]

• NCBI BLAST сервис
• общие интерпретаторы вывода BLAST, на основе графического интерфейса: JAMBLAST, Blast Viewer, BLASTGrabber
• интегрированные среды BLAST: PLAN, BlastStation-Free
• Парсеры вывода BLAST: MuSeqBox, Zerg, BioParser, BLAST-Explorer
• специализированные инструменты, связанные с BLAST: MEGAN, BLAST2GENE, BOV, Circoletto

Использование BLAST

BLAST можно использовать для нескольких целей. К ним относятся определение видов, определение местоположения доменов, определение филогении, картирование ДНК и сравнение.

Определение видов

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

Поиск доменов

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

Установление филогении

Используя результаты, полученные с помощью BLAST, вы можете создать филогенетическое дерево с помощью веб-страницы BLAST. Филогения, основанные только на BLAST, менее надежны, чем другие специализированные вычислительная филогенетика методы, поэтому на них следует полагаться только при филогенетических анализах «первого прохода».

Картирование ДНК

При работе с известными видами и поиске последовательности гена в неизвестном месте BLAST может сравнить хромосомное положение интересующей последовательности с соответствующими последовательностями в базе данных (ах). NCBI имеет для этой цели инструмент Magic-BLAST, созданный на основе BLAST.^[30]

Сравнение

При работе с генами BLAST может находить общие гены у двух родственных видов и может использоваться для сопоставления аннотаций от одного организма к другому.

Смотрите также

• Классификатор белков PSI
• Алгоритм Нидлмана-Вунша
• Алгоритм Смита-Уотермана
• Выравнивание последовательности
• Программное обеспечение для выравнивания последовательностей
• Секвером
• eTBLAST

использованная литература

1. «Информация для разработчиков BLAST». blast.ncbi.nlm.nih.gov.
2. Дуглас Мартин (21 февраля 2008 г.). «Сэмюэл Карлин, разносторонний математик, умер в возрасте 83 лет». Нью-Йорк Таймс.
3. Р. М. Кейси (2005). «Последовательности BLAST помогают в геномике и протеомике». Сеть бизнес-аналитики.
4. Липман, диджей; Пирсон, WR (1985). «Быстрые и чувствительные поиски сходства белков». Наука. 227 (4693): 1435–41. Bibcode:1985Sci ... 227.1435L. Дои:10.1126 / science.2983426. PMID  2983426.
5. "ВЗРЫВНЫЕ темы".
6. Дэн Стобер (16 января 2008 г.). «Сэм Карлин, математик, улучшивший анализ ДНК, умер в возрасте 83 лет». Stanford.edu.
7. Стивен Альтшул; Уоррен Гиш; Уэбб Миллер; Юджин Майерс; Дэвид Дж. Липман (1990). «Базовый инструмент поиска местного выравнивания». Журнал молекулярной биологии. 215 (3): 403–410. Дои:10.1016 / S0022-2836 (05) 80360-2. PMID  2231712.
8. Oehmen, C .; Nieplocha, J. (2006). «ScalaBLAST: масштабируемая реализация BLAST для высокопроизводительного биоинформатического анализа с интенсивным использованием данных». Транзакции IEEE в параллельных и распределенных системах. 17 (8): 740. Дои:10.1109 / TPDS.2006.112. S2CID  11122366.
9. Oehmen, C.S .; Бакстер, Д. Дж. (2013). «ScalaBLAST 2.0: быстрые и надежные вычисления BLAST в многопроцессорных системах». Биоинформатика. 29 (6): 797–798. Дои:10.1093 / биоинформатика / btt013. ЧВК  3597145. PMID  23361326.
10. "Смысл от последовательностей: Стивен Ф. Альтшул об улучшении BLAST". ScienceWatch. Июль – август 2000 г. Архивировано с оригинал 7 октября 2007 г.
11. Стивен Хеникофф; Джорджа Хеникофф (1992). «Матрицы аминокислотного замещения из белковых блоков». PNAS. 89 (22): 10915–10919. Bibcode:1992PNAS ... 8910915H. Дои:10.1073 / пнас.89.22.10915. ЧВК  50453. PMID  1438297.
12. Маунт, Д. В. (2004). Биоинформатика: анализ последовательности и генома (2-е изд.). Колд Спринг Харбор Пресс. ISBN  978-0-87969-712-9.
13. Адаптировано из анализа биологической последовательности I, Current Topics in Genome Analysis [1].
14. Yim, WC; Кушман, JC (2017). «Divide and Conquer (DC) BLAST: быстрое и простое выполнение BLAST в средах HPC». PeerJ. 5: e3486. Дои:10.7717 / peerj.3486. ЧВК  5483034. PMID  28652936.
15. "Таблицы выбора программ веб-сайта Blast NCBI".
16. Камачо, С .; Coulouris, G .; Авагян, В .; Мужчина.; Papadopoulos, J .; Bealer, K .; Мэдден, Т. Л. (2009). «BLAST +: Архитектура и приложения». BMC Bioinformatics. 10: 421. Дои:10.1186/1471-2105-10-421. ЧВК  2803857. PMID  20003500.
17. Vouzis, P.D .; Сахинидис, Н. В. (2010). «GPU-BLAST: использование графических процессоров для ускорения выравнивания последовательности белков». Биоинформатика. 27 (2): 182–8. Дои:10.1093 / биоинформатика / btq644. ЧВК  3018811. PMID  21088027.
18. Лю В., Шмидт Б., Мюллер-Виттиг В. (2011). «CUDA-BLASTP: ускорение BLASTP на графическом оборудовании с поддержкой CUDA». IEEE / ACM Trans Comput Biol Bioinform. 8 (6): 1678–84. Дои:10.1109 / TCBB.2011.33. PMID  21339531. S2CID  18221547.
19. Чжао К., Чу Х (май 2014 г.). «G-BLASTN: ускорение выравнивания нуклеотидов с помощью графических процессоров». Биоинформатика. 30 (10): 1384–91. Дои:10.1093 / биоинформатика / btu047. PMID  24463183.
20. Loh PR, Baym M, Berger B (июль 2012 г.). «Компрессионная геномика». Nat. Биотехнология. 30 (7): 627–30. Дои:10.1038 / nbt.2241. PMID  22781691.
21. Мэдден, Том; Боратин, Грег (2017). «QuickBLASTP: более быстрое выравнивание белков» (PDF). Материалы фестиваля исследований NIH. Получено 16 мая 2019. Абстрактная страница
22. Кент, У. Джеймс (2002-04-01). «BLAT - инструмент для выравнивания, подобный BLAST». Геномные исследования. 12 (4): 656–664. Дои:10.1101 / гр.229202. ISSN  1088-9051. ЧВК  187518. PMID  11932250.
23. Lavenier, D .; Лавенье, Доминик (2009). «PLAST: инструмент поиска параллельного локального выравнивания для сравнения баз данных». BMC Bioinformatics. 10: 329. Дои:10.1186/1471-2105-10-329. ЧВК  2770072. PMID  19821978.
24. Лавенье, Д. (2009). «Упорядоченный алгоритм начального индекса для интенсивного сравнения последовательностей ДНК» (PDF). Международный симпозиум IEEE по параллельной и распределенной обработке, 2008 г. (PDF). С. 1–8. CiteSeerX  10.1.1.155.3633. Дои:10.1109 / IPDPS.2008.4536172. ISBN  978-1-4244-1693-6. S2CID  10804289.
25. Букфинк, Се и Хусон (2015). «Быстрое и чувствительное выравнивание белков с помощью DIAMOND». Природные методы. 12 (1): 59–60. Дои:10.1038 / nmeth.3176. PMID  25402007. S2CID  5346781.
26. Стейнеггер, Мартин; Сёдинг, Йоханнес (2017-10-16). «MMseqs2 позволяет искать чувствительные последовательности белков для анализа массивных наборов данных». Природа Биотехнологии. 35 (11): 1026–1028. Дои:10.1038 / nbt.3988. HDL:11858 / 00-001M-0000-002E-1967-3. PMID  29035372. S2CID  402352.
27. Малеки, Эхсан; Кухи, Сомайе; Кавехваш, Захра; Машаги, Алиреза (2020). «OptCAM: сверхбыстрая полностью оптическая архитектура для обнаружения вариантов ДНК». Журнал биофотоники. 13 (1): e201900227. Дои:10.1002 / jbio.201900227. PMID  31397961.
28. «Объяснение биоинформатики: BLAST против Смита-Уотермана» (PDF). 4 июля 2007 г.
29. Нойман, Кумар и Шалчиан-Тебризи (2014). «Визуализация результатов BLAST в новую эру секвенирования». Брифинги по биоинформатике. 15 (4): 484–503. Дои:10.1093 / bib / bbt009. PMID  23603091.
30. «NCBI Magic-BLAST». ncbi.github.io. Получено 16 мая 2019.

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

• Официальный веб-сайт
• BLAST + исполняемые файлы - бесплатные загрузки исходников