Новый метод поиска ДНК-последовательностей сокращает время с дней до минут

Исследователи из Университета Карнеги-Меллон разработали метод поиска, который позволяет находить ДНК-последовательности в базах данных за минуты вместо дней, которые требовались ранее.

Метод, созданный Карлом Кингсфордом и Брэдом Соломоном, предназначен для поиска "коротких прочтений" (short reads) — последовательностей ДНК и РНК, генерируемых методами высокопроизводительного секвенирования. В его основе лежит новая структура данных для индексирования — Sequence Bloom Trees (SBT).

Проблема масштаба

Национальные институты здоровья (NIH) поддерживают огромный архив Sequence Read Archive, содержащий около 3 петабаз (3 квадриллиона пар оснований). Поиск в этой базе, используемой для фундаментальных и медицинских исследований (включая изучение рака), крайне затруднён из-за её объёма.

Как работает SBT

  • Метод представляет каждое короткое прочтение как набор подпоследовательностей фиксированной длины.
  • Для хранения информации используются Bloom filters — структуры данных, эффективно хранящие информацию в малом объёме.
  • Поиск происходит по принципу бинарного дерева: сначала определяется, есть ли искомая последовательность в базе, затем поиск сужается до определённой половины данных и так далее, пока не будут идентифицированы нужные эксперименты.

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

Метод протестировали на базе из 2 652 экспериментов с РНК из человеческой крови, тканей груди и мозга. Результаты:

  • Среднее время поиска новым методом: ~20 минут.

  • Расчётное время поиска существующими методами:

    • SRA-BLAST: ~2.2 дня.
    • STAR: ~921 день.

Дополнительное ускорение возможно при пакетной обработке более 200 000 запросов одновременно.