Общий кусок
Геномы лямбдоидных фагов — мозаики: кусок одного фага встречается в другом почти без изменений, а по соседству у них нет ничего общего. Чтобы найти такой кусок, выравнивают не геномы целиком, а их части — локально.
Даны два куска ДНК, s и t. Выберите в каждом по участку подряд идущих букв и выровняйте их так, чтобы счёт был наибольшим. Совпадение букв приносит A очков, несовпадение отнимает B, пропуск длины k — кусок дефисов подряд в одной строке — отнимает O + E·k. Два куска дефисов встык в разных строках — два пропуска. Пустые участки дают счёт 0.
В тестах — куски геномов фагов λ, HK97 и HK022: гены интеграз, репрессоров, белков головки, хвоста и выхода из клетки.
Вход
В первой строке — целые A, B, O, E (1 ≤ A ≤ 10, 0 ≤ B ≤ 20, 0 ≤ O ≤ 50, 1 ≤ E ≤ 20). Во второй и третьей — s и t: строки из букв A, C, G, T длиной от 1 до 1000.
Выход
В первой строке — наибольший счёт. Если он равен 0, больше ничего не выводите. Иначе во второй строке — четыре числа: начало и конец участка s, начало и конец участка t (позиции с единицы, концы включительно). В третьей и четвёртой — выравнивание этих участков: две строки одинаковой длины с дефисами на месте пропусков, без столбцов из двух дефисов. Если лучших ответов несколько, выведите любой.
Примеры
Пример 1
3 3 0 2 TGTTACGG GGTTGACTA
13 2 6 2 7 GTT-AC GTTGAC
Пример 2
2 3 5 2 ATGGAACAACGCATAACCCTGAAAGATTATGCAATGCGCT CCGTTATGGAACAACGCATAACCAAAGATTATGCAATGCGCTGACC
63 1 40 6 42 ATGGAACAACGCATAACCCTGAAAGATTATGCAATGCGCT ATGGAACAACGCATAACC---AAAGATTATGCAATGCGCT
Ограничения
- Время · Python
- 7000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 16 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Если бы участки были известны, это было бы выравнивание целиком, как в задаче «Пропуски одним куском». Перебирать все начала и концы — это (n·m)2 пар участков. А что, если разрешить выравниванию начинаться в любой клетке таблицы?
2Подсказка 2
В формулу для столбца из двух букв добавьте вариант «начать здесь»: к оценке пары прибавляется не только лучшее из трёх таблиц по диагонали, но и ноль — счёт пустого выравнивания. Если всё, что было до клетки, в сумме хуже нуля, его выгоднее отбросить.
3Подсказка 3
Ответ лежит не в углу, а в клетке таблицы M с наибольшим значением, где бы она ни была. Обратный ход идёт от этой клетки и останавливается там, где выравнивание началось с нуля.
4Идея
Лучший непустой кусок начинается и кончается парой букв: пропуск на краю только отнимает очки, ведь E ≥ 1, и без него счёт больше. Поэтому достаточно таблиц
M(i, j) = w(si, tj) + max(0, M, X, Y в (i − 1, j − 1)),
где w — это A или −B, а X и Y — те же, что в выравнивании целиком, без нуля. M(i, j) — лучший счёт выравнивания какого-нибудь участка s, кончающегося буквой si, с каким-нибудь участком t, кончающимся буквой tj, если последний столбец — эта пара. Доказательство то же, что для целых строк: убираем последний столбец, остаток либо пуст (это и есть ноль), либо кончается в клетке (i − 1, j − 1) одним из трёх видов и обязан быть лучшим своего вида. Ответ — max(0, наибольшее M(i, j)).
5Разбор
Заполняем три таблицы и запоминаем клетку с наибольшим M. Обратный ход — как в выравнивании целиком, но в таблице M проверяем: если без оценки пары остаётся ноль, кусок здесь начался. Клетка, в которой мы остановились, плюс один — начала участков, клетка с максимумом — их концы.
Первый пример — классический: при совпадении 3, несовпадении −3 и пропуске 2 за букву лучший кусок GTT-AC над GTTGAC: пять совпадений по 3 минус один пропуск. Во втором — начало гена cro фага λ и тот же кусок без одного кодона среди чужих букв: 37 совпадений по 2 минус пропуск из трёх букв 5 + 3·2 = 11, итого 63.
На настоящих тестах видна мозаика из статьи. Гены интегразы и эксцизионазы λ и HK97 дают кусок длиной 994 буквы со счётом 942 — почти без отличий. Гены репрессоров λ и HK022 дают 12, а две случайные строки по тысяче букв при тех же ценах — от 8 до 11: этих генов друг в друге нет. Гены белка хвоста J родственны по белку — 31 % одинаковых аминокислот, — а в ДНК лучший кусок — 39 букв со счётом 38 против 19–25 у случайных строк. Дальнее родство видно в белках и почти не видно в генах: одна аминокислота шифруется разными кодонами, и за долгое время буквы ДНК расходятся сильнее.
5+Решение
6Сложность
Время и память — O(n·m): три таблицы по миллиону клеток в худшем тесте. Если нужен только счёт и конец куска, хватит двух строк каждой таблицы; начало куска можно найти вторым проходом — тем же расчётом на перевёрнутых строках, начиная от найденного конца.
7Типичные ошибки
- Ответ в углу или на краю. Если искать максимум только в последней строке и последнем столбце, найдутся куски, которые доходят до конца строки, а остров в середине обеих потеряется. Так ошибается уже первый пример.
- Обратный ход до края таблицы. Если не остановиться на нуле, к куску прилипнет начало с отрицательным счётом: названный кусок наберёт меньше, чем напечатанный счёт.
- Ноль без штрафа в X и Y. Начинать кусок с пропуска невыгодно, и ноль там не нужен. А если написать max(…, 0) прямо в формуле пропуска, пропуски станут бесплатными.
- Пустой ответ. Если общих букв нет, лучший счёт 0, и выводится только он.
- Позиции с нуля. Границы участков в ответе считаются с единицы, концы включительно.