Куда легли риды
Эталонный геном хранится в виде преобразования Барроуза — Уилера, как в предыдущей задаче: к тексту T из букв A, C, G, T приписан знак $, меньший всех букв, циклические сдвиги отсортированы, выписаны их последние буквы — строка L. Секвенатор прочитал ДНК короткими кусками — ридами. Все риды прочитаны с той же цепи, что и T, но в некоторых есть ошибки.
Для каждого рида найдите, куда он ложится. Если рид встречается в T буква в букву, выведите все такие места. Если нет — все места, где он совпадает с T во всех буквах, кроме одной. Если и таких нет, рид не ложится.
В тестах — геномы фагов λ, φX174 и трёх родственных фагов подряд, митохондрии человека, случайные буквы и много копий одного куска. В тесте с λ риды взяты из лабораторного штамма с его четырьмя заменами, как в статье.
Вход
В первой строке — L: буквы A, C, G, T и один знак $, длина от 2 до 2·105 + 1. Во второй — число ридов q (1 ≤ q ≤ 3000). Дальше q строк — риды из букв A, C, G, T длиной от 1 до 40.
Выход
Для каждого рида — строка: число мест k, а за ним сами места в порядке возрастания. Место — номер первой буквы рида в T, буквы нумеруются с единицы. Если рид не ложится, строка — 0.
Примеры
Пример 1
TGTA$AAACCCGG 4 ACG CGA TTT GTACGT
3 1 5 9 1 6 0 2 3 7
Пример 2
CTCGGTA$ATTAA 4 GATTAC CCCC GATTCC A
1 1 0 1 1 4 2 5 7 9
Ограничения
- Время · Python
- 8000 мс
- Время · Go
- 1500 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Перебрать все места текста для каждого рида — 2·105 · 3000 · 40 сравнений, слишком много. Точные вхождения даёт обратный поиск. Как разрешить ему одну ошибку?
2Подсказка 2
Обратный поиск читает рид с конца и на каждом шаге выбирает букву. Что если на одном из шагов взять не букву рида, а другую — и запомнить, что ошибка потрачена? Сколько таких путей останется живыми, если путь бросать, как только его отрезок пустеет?
3Идея
Сначала — обычный обратный поиск; если отрезок не пуст, его строки и есть точные вхождения. Иначе — поиск с возвратом: состояние — (сколько букв рида осталось прочитать, отрезок, потрачена ли ошибка). Из состояния можно пойти по букве рида, а если ошибка не потрачена — ещё по трём другим буквам, потратив её. Пустой отрезок обрывает ветку. Отрезки, до которых дошли, прочитав весь рид, — строки, где рид стоит с одной заменой: замена ровно одна, потому что точных вхождений нет.
Остаётся перевести строки таблицы в места текста. Для этого не нужен сам текст: шаги LF из строки 0 — там сдвиг, начинающийся с $, — проходят строки позиций n − 1, n − 2, …, 0 по одной, и по дороге записывается весь суффиксный массив.
4Разбор
Счётчики rank для пяти знаков храним для всех строк — каждый шаг стоит O(1). Суффиксный массив — n чисел, заполненных за n шагов LF. Поиск с возвратом удобно писать стеком, а не рекурсией. Места из всех найденных отрезков сортируем.
В первом примере текст ACGTACGAACGT: ACG стоит точно с позиций 1, 5 и 9; CGA — точно с позиции 6, а места с одной заменой, вроде CGT с позиции 2, уже не выводятся. TTT не ложится. GTACGT точно не встречается, а с одной заменой — с позиций 3 (GTACGA) и 7 (GAACGT).
4+Решение
5Сложность
Подготовка — O(n). Рид длины m в худшем случае стоит O(σ·m2) шагов: для каждого места замены — три буквы и остаток рида. На деле ветка с заменой гибнет через несколько шагов: в геноме из 2·105 букв почти любые десять случайных букв подряд не встречаются. Вывод — сколько мест найдено.
6Типичные ошибки
- Выводить и точные места, и места с заменой. Если рид лёг точно, места с одной заменой не нужны — первый пример это ловит.
- Тратить ошибку на ту же букву. Ветка «буква рида, но ошибка потрачена» даёт те же строки, что и без траты, и места задваиваются.
- Рекурсия в Python. Глубина всего 40, но вызов функции в Python дорог; стек из кортежей быстрее.
- Проход по тексту. Восстановить текст и проверить каждое место для каждого рида — верно, но уже тест с геномом λ не уложится во время.