# Точный алгоритм картирования по эскизам: полнота 0,88 против 0,76 у minimap2 на симуляции хромосомы Y

- Опубликовано: 2026-11-14 16:41 UTC
- Раздел: Цифра и вычисления › Софт и сервисы
- Теги: картирование ридов по эскизам, точный алгоритм картирования, сравнение с minimap2, хромосома Y человека, сборка T2T, ампликонные районы, минимайзеры, длинные риды, полнота и точность
- Адрес: https://realtech.media/ru/news/rt-b88992b8bae30522994438db_tochnyy_algoritm_kartirovaniya/

**Существующие методы на эскизах не гарантировали находить все позиции картирования выше порога; новый точный алгоритм это делает, проверка — на симулированных длинных ридах.**

![Exact sketch read mapping algorithm: recall 0.88 vs 0.76 for minimap2 on simulated chromosome Y reads](https://realtech.media/media/2026/11/44137283d0599902.jpg)
*Scotted400, Wikimedia Commons, CC BY 3.0*

Исследователи сформулировали задачу картирования ридов на уровне эскизов последовательностей и описали точный алгоритм динамического программирования, который находит все совпадения выше заданного порога сходства, сообщается в статье в журнале Algorithms for Molecular Biology. На симулированных длинных ридах по сборке T2T человеческой хромосомы Y при точности, эквивалентной minimap2, полнота алгоритма составила 0,88, а у minimap2 — 0,76 [1].

Традиционно похожей считалась последовательность с высоким счётом выравнивания, а картировщики рассматривались как эвристические решения этой задачи. Для методов на эскизах не было постановки задачи, описывающей, что должен решать точный алгоритм, и ни один такой метод не мог найти все позиции картирования рида выше порога по счёту [1].

## Постановка задачи и алгоритм

Авторы определяют задачу на эскизах: по эскизу рида и эскизу референса нужно выдать все кандидатные интервалы референса, счёт которых превышает порог. Кандидат должен начинаться и заканчиваться k-мерами, присутствующими в эскизе рида, и не должен содержаться в более длинном интервале со строго большим счётом. Авторы также вводят параметризованную линейную функцию счёта и доказывают, что она разделяет кандидатов не хуже взвешенного индекса Жаккара [1].

Алгоритм работает за время O(|t| + |p| + ℓ²) и использует память O(ℓ log ℓ). Здесь |t| — число k-меров в эскизе референса, |p| — число k-меров в эскизе рида, а ℓ — число вхождений k-меров из эскиза рида в эскиз референса [1]. Память удерживается небольшой за счёт того, что матрица динамического программирования считается по столбцам и одновременно хранятся только два столбца.

## Проверка на хромосоме 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 [1].

## Источники

1. [Algorithms for Molecular Biology](https://doi.org/10.1186/s13015-024-00261-7)
2. [bioengineer.org](https://bioengineer.org/exact-sketch-read-mapping-algorithm-achieves-superior-recall-on-repetitive-chromosome-reads)

---

Источник: RealTech, realtech.media — https://realtech.media/ru/news/rt-b88992b8bae30522994438db_tochnyy_algoritm_kartirovaniya/