Сайты с буквой N
Фермент HinfI режет ДНК там, где встречаются пять букв G, A, любая, T, C. Биологи записывают такой сайт как GANTC: буква N в нём значит «любое основание». Для других неоднозначных позиций есть свои буквы — их утвердил комитет по номенклатуре IUPAC:
| Буква | A, C, G, T | R | Y | S | W | K | M | B | D | H | V | N |
|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Основания | сама буква | A G | C T | C G | A T | G T | A C | C G T | A G T | A C T | A C G | любое |
Например, у StyI сайт CCWWGG: в середине может стоять AA, AT, TA или TT. Префикс-функция и прочие хитрые алгоритмы поиска рассчитаны на точное совпадение букв, а здесь буква образца — целое множество. Наивному поиску всё равно: он и так сравнивает букву с буквой, сравнение просто становится проверкой «входит ли основание в множество».
Посчитайте, сколько раз каждый сайт встречается в геноме. Сайты могут перекрываться: в AAAA сайт RR встречается три раза. Геном читается как линейная молекула, по одной цепи, от первой буквы к последней. Среди тестов — геномы фагов λ и φX174 и десять настоящих ферментов.
Вход
В первой строке — геном: строка из букв A, C, G, T длиной n (1 ≤ n ≤ 50 000). Во второй — число сайтов q (1 ≤ q ≤ 10). Дальше q строк, в каждой сайт из букв таблицы длиной m, 1 ≤ m ≤ min(12, n).
Выход
q строк: для каждого сайта — число позиций генома, с которых он начинается.
Примеры
Пример 1
GAATTCGACTCGAGTCAA 3 GANTC CYCGRG NN
2 1 17
Пример 2
AAAAAAGG 4 RR ARA AAAA GG
7 4 3 1
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Возьмите наивный поиск из статьи и замените в нём одно место: вместо «буква текста равна букве образца» — «буква текста входит в множество, которое обозначает буква образца».
2Подсказка 2
Чтобы проверка стоила одно действие, заранее превратите каждую букву сайта в таблицу: для каждого из четырёх оснований — подходит оно или нет. В Python то же самое умеет регулярное выражение: буква сайта становится классом символов [AG].
3Подсказка 3
Проверьте второй пример: в AAAAAAGG сайт RR встречается семь раз. Сколько насчитает re.findall? Найдя вхождение, он продолжает искать после его конца.
4Идея
Наивный поиск не делает никаких выводов о тексте из совпавших букв: он просто прикладывает образец к каждой позиции заново. Поэтому ему безразлично, что сравнение — не равенство, а проверка принадлежности множеству. Алгоритмы, которые запоминают совпавшее, на этом ломаются: у КМП из совпадения A с R и R с G не следует, что A совпадает с G, и грани образца перестают описывать текст.
5Разбор
В Go для каждой позиции сайта строится таблица из 256 флажков, и поиск перебирает начала, как в статье, сравнивая основания с таблицами до первого отказа. В Python тот же перебор делает движок регулярных выражений: сайт становится цепочкой классов символов, а опережающая проверка (?=…) ищет совпадение, не поглощая текст. Поэтому движок пробует каждую позицию по очереди, и перекрывающиеся сайты все попадают в счёт. Это и есть наивный поиск, только написанный на C.
Ответы третьего и четвёртого тестов можно сверить со справочником. В таблицах производителя ферментов Promega HinfI режет ДНК фага λ в 148 местах, а φX174 — в 21, BglI — в 29 и ни разу, DdeI — в 104 и 14. Ровно столько и насчитывает решение.
5+Решение
6Сложность
На сайт — O(n · m) в худшем случае и около n проверок в обычном: в случайной ДНК точная первая буква сайта не подходит в трёх случаях из четырёх, R или W — в половине. Худший тест — геном из одних A и сайты из двенадцати букв, которые подходят к A почти целиком: до 10 · 50 000 · 12 = 6 · 10⁶ проверок. Go и движок регулярных выражений тратят на это миллисекунды, простой цикл на Python — около половины секунды на быстром ноутбуке, и в предел времени он тоже укладывается.
7Типичные ошибки
re.findallбез опережающей проверки. Находит вхождения, которые не перекрываются: в AAAA сайт RR — два раза вместо трёх. Перекрытия в настоящей ДНК обычны у сайтов с N и у коротких сайтов вроде RR.str.countилиstrings.Countпо сайту как есть. Буква N в геноме не встречается, и ответ почти всегда ноль. Кроме того, обе функции тоже не считают перекрытия.- Только N. Обработали «любую букву», но забыли R, Y, W и остальные: StyI и HaeII тогда никогда не находятся.
- Сайт длиннее генома. По условию так не бывает, но если перебирать начала до n, а не до n − m, выйдете за конец строки.