Точный алгоритм картирования по эскизам: полнота 0,88 против 0,76 у minimap2 на симуляции хромосомы Y
Существующие методы на эскизах не гарантировали находить все позиции картирования выше порога; новый точный алгоритм это делает, проверка — на симулированных длинных ридах.
Исследователи сформулировали задачу картирования ридов на уровне эскизов последовательностей и описали точный алгоритм динамического программирования, который находит все совпадения выше заданного порога сходства, сообщается в статье в журнале Algorithms for Molecular Biology. На симулированных длинных ридах по сборке T2T человеческой хромосомы Y при точности, эквивалентной minimap2, полнота алгоритма составила 0,88, а у minimap2 — 0,76 biomedcentral.com
Algorithms for Molecular Biologybiomedcentral.comОткрыть источник ↗.
Традиционно похожей считалась последовательность с высоким счётом выравнивания, а картировщики рассматривались как эвристические решения этой задачи. Для методов на эскизах не было постановки задачи, описывающей, что должен решать точный алгоритм, и ни один такой метод не мог найти все позиции картирования рида выше порога по счёту.
Постановка задачи и алгоритм
Авторы определяют задачу на эскизах: по эскизу рида и эскизу референса нужно выдать все кандидатные интервалы референса, счёт которых превышает порог. Кандидат должен начинаться и заканчиваться k-мерами, присутствующими в эскизе рида, и не должен содержаться в более длинном интервале со строго большим счётом. Авторы также вводят параметризованную линейную функцию счёта и доказывают, что она разделяет кандидатов не хуже взвешенного индекса Жаккара.
Алгоритм работает за время O(|t| + |p| + ℓ²) и использует память O(ℓ log ℓ). Здесь |t| — число k-меров в эскизе референса, |p| — число k-меров в эскизе рида, а ℓ — число вхождений k-меров из эскиза рида в эскиз референса biomedcentral.com
Algorithms for Molecular Biologybiomedcentral.comОткрыть источник ↗. Память удерживается небольшой за счёт того, что матрица динамического программирования считается по столбцам и одновременно хранятся только два столбца.
Проверка на хромосоме Y человека
Хромосома Y содержит ампликонные районы, где желательно находить все хорошие позиции картирования, а не одну лучшую. Риды симулировали по образцу данных Pacific Biosciences HiFi: длины следовали гамма-распределению со средним 9 000 пар оснований, общая частота мутаций составляла 0,2 процента с учётом замен, вставок и делеций. После исключения ридов из повторяющихся центромерных и теломерных массивов, которые выравнивались более чем на двадцать позиций, осталось 32 295 ридов.
Алгоритм сравнили с minimap2, Winnowmap2 и точным инструментом на основе выравнивания, реализованным через edlib. Он использовал те же параметры минимайзеров, что и minimap2: длина k-мера 15 и размер окна 10, при этом минимайзеры, встречающиеся в эскизе референса более 100 раз, маскировались. Эталонную разметку получали по выравниваниям BLAST. При точности, эквивалентной minimap2, полнота составила 0,88 против 0,76.
