Новые алгоритмы ускоряют сборку генома с месяцев до минут

Современные секвенаторы нового поколения переводят последовательности оснований ДНК (A, G, C, T) в текст, но выдают лишь короткие "прочтения" длиной 50–300 символов. Сборка генома — это восстановление полной последовательности из этих фрагментов, подобно сборке книги из обрывков предложений. Процесс сложен и долог, особенно для больших геномов: человеческий содержит ~3 млрд оснований, пшеничный — ~17 млрд, сосновый — ~23 млрд. Сборка de novo (с нуля) без референсного генома сравнима со сборкой пазла из 10 млрд деталей без картинки.

Учёные из Lawrence Berkeley National Laboratory (Berkeley Lab), Joint Genome Institute (JGI) и UC Berkeley применили новые алгоритмы, вычислительные методы и язык программирования Unified Parallel C (UPC) к инструменту сборки генома de novo Meraculous. Это упростило и ускорило процесс, сократив его с месяцев до минут. Ключевым шагом стала параллелизация кода для использования мощности суперкомпьютеров, таких как система Edison в Национальном центре суперкомпьютерных вычислений для энергетических исследований (NERSC). Параллелизация означает разделение задач, которые раньше выполнялись последовательно, и их одновременный запуск на тысячах ядер суперкомпьютера.

"Используя параллелизованную версию Meraculous, мы можем собрать весь человеческий геном примерно за восемь минут, используя 15 360 процессорных ядер. С этим инструментом мы оцениваем, что выходные данные мировой биомедицинской мощности секвенирования можно собрать, используя лишь часть суперкомпьютера Edison NERSC", — говорит Евангелос Георганас, аспирант UC Berkeley, руководивший параллелизацией Meraculous.

"Эта работа кардинально улучшила скорость сборки генома. Новые параллельные алгоритмы позволяют выполнять расчёты сборки быстро, с почти линейным масштабированием на тысячах ядер. Теперь исследователи могут собирать большие геномы, такие как пшеница и сосна, за минуты вместо месяцев", — добавляет Леонид Оликер, специалист по компьютерным наукам из CRD.

Суперкомпьютеры: меняющие правила игры для сборки

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

"Применение фильтров Блума к этой части задачи сборки генома не ново. Наше отличие в том, что мы заставили фильтры Блума работать с системами с распределённой памятью. Это была нетривиальная задача, потребовавшая вычислительной экспертизы", — отмечает Айдын Булуч, научный сотрудник CRD.

Команда также разработала решения для параллелизации ввода-вывода (I/O) данных. "Когда у вас несколько терабайт данных, просто чтение данных компьютером и вывод результатов могут стать огромным узким местом. Позволив компьютеру загружать данные в нескольких потоках, мы ускорили процесс I/O с часов до минут", — объясняет Стивен Хофмайр, научный сотрудник CRD.

Сборка de novo

После фильтрации ошибок начинается сборка генома. Программы соединяют k-меры (короткие последовательности ДНК фиксированной длины K) в перекрывающихся областях, формируя непрерывные последовательности — контиги. Для сборки de novo (без референса) Георганас создал новый алгоритм, использующий одностороннюю коммуникацию и возможности модели Partitioned Global Address Space (PGAS) языка UPC. PGAS позволяет обращаться к физически разделённой памяти узлов суперкомпьютера как к единому адресному пространству, сокращая время и энергию на обмен информацией между узлами.

"Новая параллелизованная версия Meraculous демонстрирует беспрецедентную производительность и эффективное масштабирование до 15 360 процессорных ядер для геномов человека и пшеницы на суперкомпьютере Edison NERSC. Это улучшение ускорило рабочий процесс сборки с дней до секунд", — говорит Георганас.

Завершающий этап — заполнение пробелов в собранных контигах. Обе фазы этого процесса были переписаны на UPC и параллелизованы. "Результат конвертации этой части конвейера в UPC — ускорение в 20–30 раз по сравнению с оригинальным кодом Meraculous на Perl. Это также позволяет пользователю динамически балансировать нагрузку", — говорит Хофмайр.

Перспективы: метагеномика

"До этой версии Meraculous вычисления часто занимали больше времени, чем само секвенирование. Поскольку вычисления были такими долгими, я выбирал набор параметров на основе предположений, запускал задание — и это был мой результат", — рассказывает Джаррод Чепмен, разработчик Meraculous в JGI.

Теперь, когда вычисления перестали быть узким местом, Чепмен может тестировать множество параметров для получения максимально точных результатов. Он также считает, что это достижение позволит использовать Meraculous для анализа метагеномов — микробных сообществ, полученных непосредственно из образцов окружающей среды. Это критически важно, так как многие микробы не культивируются в лаборатории и могут быть источником новых лекарств или энергии.

"Анализ метагеномов — титанический труд. Если сборка одного генома (например, пшеницы) — это сборка одного романа, то сборка метагеномных данных — это восстановление Библиотеки Конгресса. Использование Meraculous для такого анализа изменит правила игры", — говорит Чепмен.

"Ключ к успеху нашего проекта — тесная синхронизация с учёными-предметниками. Они видят проблему и путь её решения. Мы, компьютерные учёные, вооружены 'мешком трюков'. Понимая научную перспективу, мы можем выбрать, какие инструменты наиболее полезны для ускорения их процесса", — подводит итог Хофмайр.