Ошибки секвенатора
Секвенатор прочитал кусок генома, но с ошибками: иногда он путает букву, иногда вставляет лишнюю, иногда пропускает настоящую. У каждой машины свой характер. Одна почти не теряет букв, но часто их путает; нанопоровый секвенатор, наоборот, путает редко, зато легко пропускает. Поэтому цены ошибок разные: замена стоит S, вставка лишней буквы — I, пропуск буквы эталона — D.
Дан эталон — кусок известного генома — и рид. Найдите самый дешёвый способ получить рид из эталона заменами, вставками и пропусками и запишите его выравниванием: эталон и рид друг под другом, с дефисами на месте пропусков. Столбец, где буква эталона стоит над дефисом, — пропуск; дефис над буквой рида — вставка; две разные буквы — замена. Столбцов из двух дефисов не бывает.
Эталоны в тестах — куски геномов фагов лямбда и φX174 и митохондрии человека.
Вход
В первой строке три целых числа S, I, D (1 ≤ S, I, D ≤ 100). Во второй — эталон, в третьей — рид: строки из букв A, C, G, T длиной от 1 до 600.
Выход
В первой строке — наименьшая цена. Во второй и третьей — выравнивание: эталон и рид одинаковой длины с дефисами. Если самых дешёвых выравниваний несколько, выведите любое.
Примеры
Пример 1
1 1 1 GATTACA GCATGCG
4 GATTACA GCATGCG
Пример 2
3 1 1 GATTACA GCATGCG
6 G-AT-TAC-A GCATG--CG-
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 11 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Если бы все ошибки стоили 1, это было бы обычное расстояние редактирования. Что меняется в таблице, когда цены разные?
2Подсказка 2
Подзадача та же: самый дешёвый способ получить первые j букв рида из первых i букв эталона. Последний столбец выравнивания — пропуск, вставка или пара букв, и у каждого варианта своя цена.
3Подсказка 3
Не ищите сначала выравнивание с наименьшим числом правок, чтобы потом сложить их цены. Во втором примере замена стоит 3, а пропуск и вставка вместе — 2.
4Идея
D[i][j] = min(D[i − 1][j] + D, D[i][j − 1] + I, D[i − 1][j − 1] + (0, если буквы равны, иначе S)), края — i · D и j · I. Доказательство то же, что в статье: в любом выравнивании последний столбец — один из трёх видов, и остаток выравнивания обязан быть самым дешёвым для своих начал.
5Разбор
Заполняем таблицу (n + 1) × (m + 1) по строкам, потом идём от правого нижнего угла назад: на каждом шаге ищем соседа, из которого клетка получила своё значение, и выписываем столбец выравнивания. Выписанное переворачиваем.
Посмотрите на второй пример. С ценами 1, 1, 1 самое дешёвое выравнивание GATTACA и GCATGCG стоит 4 и состоит из четырёх замен. Если замена стоит 3, те же четыре замены обошлись бы в 12, а выравнивание из трёх пропусков и трёх вставок — в 6: G-AT-TAC-A над GCATG--CG-, где совпали G, A, T и C. Самое короткое по числу правок и самое дешёвое — разные выравнивания.
5+Решение
6Сложность
Время и память — O(n · m), 360 000 клеток в худшем тесте. Если нужна только цена, хватит двух строк таблицы. Для самого выравнивания в линейной памяти есть приём Хиршберга: таблицу считают от двух концов до середины, находят, где путь пересекает среднюю строку, и решают две половины отдельно.
7Типичные ошибки
- Сначала правки, потом цены. Выравнивание с наименьшим числом правок может стоить дороже другого: при дорогой замене выгоднее пропуск и вставка, при дешёвых вставках — лишние вставки вместо замен.
- Перепутаны вставка и пропуск. Шаг вниз по таблице (по эталону) — пропуск буквы эталона, шаг вправо (по риду) — вставка. На тестах с I ≠ D это меняет ответ.
- Края таблицы с единицами. Первая строка — j вставок, первый столбец — i пропусков, каждые по своей цене, а не i и j.