Задачник Базовый курс EN

Пропуски одним куском

динамика похожесть биоинформатика матрица

Белки сравнивают, выравнивая их: две последовательности аминокислот пишут друг под другом и вставляют в них пропуски — дефисы. Столбец из двух букв x и y приносит оценку S(x, y) из матрицы замен. Одна мутация часто вставляет или удаляет сразу несколько аминокислот, поэтому пропуском считается кусок дефисов подряд в одной строке, и пропуск длины k стоит O + E·k: открыть дорого, продлить дёшево. Два куска дефисов, идущие встык в разных строках, — два разных пропуска.

Выровняйте два белка целиком, от первой буквы до последней, с наибольшим счётом — суммой оценок столбцов из двух букв минус штрафы за пропуски.

Белки в тестах — гемоглобины, миоглобины, лизоцим, рибонуклеаза и белки фагов λ, HK97 и HK022; матрица почти везде — BLOSUM62.

Вход

В первой строке — целые O и E (0 ≤ O ≤ 50, 1 ≤ E ≤ 20). Во второй — 20 букв аминокислот через пробел. Дальше 20 строк матрицы замен: буква и 20 целых чисел от −20 до 20 — оценки её пары с буквами в порядке второй строки; матрица симметрична. В последних двух строках — белки: строки из этих букв длиной от 1 до 600.

Выход

В первой строке — наибольший счёт. Во второй и третьей — выравнивание: первый и второй белок одинаковой длины с дефисами на месте пропусков. Столбцов из двух дефисов не бывает. Если лучших выравниваний несколько, выведите любое.

Примеры

Пример 1

Вход

3 1
A R N D C Q E G H I L K M F P S T W Y V
A 4 -1 -2 -2 0 -1 -1 0 -2 -1 -1 -1 -1 -2 -1 1 0 -3 -2 0
R -1 5 0 -2 -3 1 0 -2 0 -3 -2 2 -1 -3 -2 -1 -1 -3 -2 -3
N -2 0 6 1 -3 0 0 0 1 -3 -3 0 -2 -3 -2 1 0 -4 -2 -3
D -2 -2 1 6 -3 0 2 -1 -1 -3 -4 -1 -3 -3 -1 0 -1 -4 -3 -3
C 0 -3 -3 -3 9 -3 -4 -3 -3 -1 -1 -3 -1 -2 -3 -1 -1 -2 -2 -1
Q -1 1 0 0 -3 5 2 -2 0 -3 -2 1 0 -3 -1 0 -1 -2 -1 -2
E -1 0 0 2 -4 2 5 -2 0 -3 -3 1 -2 -3 -1 0 -1 -3 -2 -2
G 0 -2 0 -1 -3 -2 -2 6 -2 -4 -4 -2 -3 -3 -2 0 -2 -2 -3 -3
H -2 0 1 -1 -3 0 0 -2 8 -3 -3 -1 -2 -1 -2 -1 -2 -2 2 -3
I -1 -3 -3 -3 -1 -3 -3 -4 -3 4 2 -3 1 0 -3 -2 -1 -3 -1 3
L -1 -2 -3 -4 -1 -2 -3 -4 -3 2 4 -2 2 0 -3 -2 -1 -2 -1 1
K -1 2 0 -1 -3 1 1 -2 -1 -3 -2 5 -1 -3 -1 0 -1 -3 -2 -2
M -1 -1 -2 -3 -1 0 -2 -3 -2 1 2 -1 5 0 -2 -1 -1 -1 -1 1
F -2 -3 -3 -3 -2 -3 -3 -3 -1 0 0 -3 0 6 -4 -2 -2 1 3 -1
P -1 -2 -2 -1 -3 -1 -1 -2 -2 -3 -3 -1 -2 -4 7 -1 -1 -4 -3 -2
S 1 -1 1 0 -1 0 0 0 -1 -2 -2 0 -1 -2 -1 4 1 -3 -2 -2
T 0 -1 0 -1 -1 -1 -1 -2 -2 -1 -1 -1 -1 -2 -1 1 5 -2 -2 0
W -3 -3 -4 -4 -2 -2 -3 -2 -2 -3 -2 -3 -1 1 -4 -3 -2 11 2 -3
Y -2 -2 -2 -3 -2 -1 -2 -3 2 -1 -1 -2 -1 3 -3 -2 -2 2 7 -1
V 0 -3 -3 -3 -1 -2 -2 -3 -3 3 1 -2 1 -1 -2 -2 0 -3 -1 4
HEAGAWGHEE
PAWHEAE

Выход

17
HEAGAWGHE-E
---PAW-HEAE

Пример 2

Вход

10 1
A R N D C Q E G H I L K M F P S T W Y V
A 4 -1 -2 -2 0 -1 -1 0 -2 -1 -1 -1 -1 -2 -1 1 0 -3 -2 0
R -1 5 0 -2 -3 1 0 -2 0 -3 -2 2 -1 -3 -2 -1 -1 -3 -2 -3
N -2 0 6 1 -3 0 0 0 1 -3 -3 0 -2 -3 -2 1 0 -4 -2 -3
D -2 -2 1 6 -3 0 2 -1 -1 -3 -4 -1 -3 -3 -1 0 -1 -4 -3 -3
C 0 -3 -3 -3 9 -3 -4 -3 -3 -1 -1 -3 -1 -2 -3 -1 -1 -2 -2 -1
Q -1 1 0 0 -3 5 2 -2 0 -3 -2 1 0 -3 -1 0 -1 -2 -1 -2
E -1 0 0 2 -4 2 5 -2 0 -3 -3 1 -2 -3 -1 0 -1 -3 -2 -2
G 0 -2 0 -1 -3 -2 -2 6 -2 -4 -4 -2 -3 -3 -2 0 -2 -2 -3 -3
H -2 0 1 -1 -3 0 0 -2 8 -3 -3 -1 -2 -1 -2 -1 -2 -2 2 -3
I -1 -3 -3 -3 -1 -3 -3 -4 -3 4 2 -3 1 0 -3 -2 -1 -3 -1 3
L -1 -2 -3 -4 -1 -2 -3 -4 -3 2 4 -2 2 0 -3 -2 -1 -2 -1 1
K -1 2 0 -1 -3 1 1 -2 -1 -3 -2 5 -1 -3 -1 0 -1 -3 -2 -2
M -1 -1 -2 -3 -1 0 -2 -3 -2 1 2 -1 5 0 -2 -1 -1 -1 -1 1
F -2 -3 -3 -3 -2 -3 -3 -3 -1 0 0 -3 0 6 -4 -2 -2 1 3 -1
P -1 -2 -2 -1 -3 -1 -1 -2 -2 -3 -3 -1 -2 -4 7 -1 -1 -4 -3 -2
S 1 -1 1 0 -1 0 0 0 -1 -2 -2 0 -1 -2 -1 4 1 -3 -2 -2
T 0 -1 0 -1 -1 -1 -1 -2 -2 -1 -1 -1 -1 -2 -1 1 5 -2 -2 0
W -3 -3 -4 -4 -2 -2 -3 -2 -2 -3 -2 -3 -1 1 -4 -3 -2 11 2 -3
Y -2 -2 -2 -3 -2 -1 -2 -3 2 -1 -1 -2 -1 3 -3 -2 -2 2 7 -1
V 0 -3 -3 -3 -1 -2 -2 -3 -3 3 1 -2 1 -1 -2 -2 0 -3 -1 4
YFPHFDLSHGSAQVKGH
FFESFGDLSTPDAVMGNPKVKAH

Выход

23
YFPHF-DLS-----HGSAQVKGH
FFESFGDLSTPDAVMGNPKVKAH

Ограничения

Время · Python: 4000 мс
Время · Go: 1000 мс
Память: 256 МБ
Проверка: 16 тестов

Разбор

Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.

1Подсказка 1

Если бы каждый дефис стоил одинаково, хватило бы одной таблицы, как у редакционного расстояния. Что нужно знать о выравнивании первых букв, чтобы понять, сколько будет стоить следующий дефис?

2Подсказка 2

Следующий дефис стоит E, если последний столбец — дефис в той же строке, и O + E в остальных случаях. Значит, важно, каким столбцом кончается выравнивание. Заведите по таблице на каждый вид последнего столбца: пара букв, буква первого белка над дефисом, дефис над буквой второго.

3Подсказка 3

Края: выравнивание первых i букв с пустой строкой — один пропуск длины i, его счёт −O − E·i, и кончается оно дефисом во второй строке. Всё остальное на краях невозможно — минус бесконечность, только такая, чтобы вычитание её не переполняло.

4Идея

Пусть M(i, j), X(i, j), Y(i, j) — лучшие счета выравниваний первых i букв белка a с первыми j буквами белка b, которые кончаются парой букв, буквой a_i над дефисом и дефисом над b_j. Тогда

M(i, j) = S(a_i, b_j) + max(M, X, Y в (i − 1, j − 1)),
X(i, j) = max(M(i − 1, j) − O − E, X(i − 1, j) − E, Y(i − 1, j) − O − E),
Y(i, j) = max(M(i, j − 1) − O − E, Y(i, j − 1) − E, X(i, j − 1) − O − E).

Почему это верно. Уберём из лучшего выравнивания, кончающегося буквой над дефисом, последний столбец. Остаток — выравнивание первых i − 1 букв с первыми j, и последний столбец стоил E, если остаток тоже кончается буквой над дефисом, и O + E иначе. Цена последнего столбца зависит от остатка только через вид его последнего столбца, поэтому остаток обязан быть лучшим среди выравниваний своего вида — иначе его можно заменить лучшим того же вида и улучшить всё выравнивание. Перебрав три вида остатка, получаем формулу. Для двух других таблиц рассуждение то же. Ответ — наибольшее из трёх значений в клетке (n, m).

5Разбор

Заполняем три таблицы по строкам, затем идём от клетки (n, m) назад, помня, в какой таблице находимся. В M выписываем пару букв и ищем, какая из трёх таблиц в клетке по диагонали дала максимум; в X выписываем букву над дефисом и проверяем, продолжение это пропуска или его открытие, и так далее. Выписанное переворачиваем.

В первом примере это видно сразу. Если каждый дефис стоит 4, выгодно рассыпать их: --P-AW-HEAE. При открытии 3 и продлении 1 три дефиса подряд стоят 3 + 3 = 6, а те же три дефиса двумя кусками — 5 + 4 = 9, и лучшее выравнивание ---PAW-HEAE набирает 17. Во втором примере — угол α- и β-цепей гемоглобина: пять дефисов подряд встают напротив спирали D β-цепи, которой у α-цепи нет.

5+Решение

6Сложность

Время и память — O(n·m): три таблицы по 361 201 клетке в худшем тесте. Если нужен только счёт, хватит двух строк каждой таблицы. Выравнивание тоже можно получить в линейной памяти, способом Майерса и Миллера: таблицы считают от двух концов до средней строки, находят, где через неё проходит лучший путь, и решают две половины отдельно.

7Типичные ошибки

Открытие за каждый дефис. Одна таблица со штрафом O + E за букву — это линейный штраф, и длинный пропуск стоит столько же, сколько столько же коротких. В первом примере так получается выравнивание со счётом 15, во втором — 14 вместо 23.
Встык — значит одним куском. Если перейти из X в Y без штрафа за открытие, дефис над буквой и сразу за ним буква над дефисом сольются в один пропуск, а по условию это два.
Края без открытия. Пропуск в начале выравнивания — тоже пропуск: −O − E·i, а не −E·i.
Обратный ход без состояния. Если в каждой клетке брать ту таблицу, где значение больше, можно перескочить на путь, который в эту клетку пришёл по-другому, и выписать выравнивание с другим счётом. Таблицу, в которой находишься, надо помнить.
Переполнение. «Минус бесконечность» вроде наименьшего 32-битного числа после вычитания штрафа становится огромным положительным. Берите запас: −2⁶⁰ в 64 битах.

Алгоритмы задачи

DP Алгоритм Выравнивание последовательностей Лучшее сопоставление двух последовательностей с очками за замены и пропуски: целиком, по кускам и с проверкой на случайность. O(m · n) 2 задачи