Vargas: безэвристическое выравнивание для оценки линейных и графовых выравнивателей ридов

Мотивация: Выравнивание ридов имеет центральное значение для многих задач современной геномики. Большинство выравнивателей используют эвристики для ускорения работы, но эти эвристики могут не находить оптимальные выравнивания ридов. Точность выравнивания обычно оценивают на основе смоделированных ридов; однако моделируемая позиция может быть не единственной позицией с оптимальным баллом выравнивания.

Результаты: Vargas реализует безэвристический алгоритм, который гарантированно находит выравнивание с наивысшим баллом для реальных секвенированных ридов к линейному или графовому геному. Поддерживая режимы полуглобального и локального выравнивания, а также штрафы за разрывы с аффинной моделью и за несовпадения, масштабированные по качеству, он может воспроизводить функции оценки, используемые распространёнными выравнивателями, для расчёта оптимальных выравниваний. Хотя это вычислительно затратно, Vargas использует многопоточную параллелизацию и векторизованные инструкции SIMD, что делает оптимальное выравнивание большого числа ридов практически осуществимым; достигнута максимальная скорость 456 млрд обновлений ячеек в секунду. Мы показали, что такие выравнивания Vargas, служащие «золотым стандартом», можно использовать для повышения точности эвристического выравнивания за счёт оптимизации параметров командной строки в Bowtie 2, BWA-maximal exact match и vg, что позволяет корректно выравнивать больше ридов.

Доступность и реализация: Исходный код на C++ и готовые двоичные сборки доступны по адресу https://github.com/langmead-lab/vargas на условиях лицензии MIT.

Дополнительная информация: Дополнительные данные доступны онлайн в Bioinformatics.