Недавно я столкнулся с хитрым вопросом программирования c. Мне даны две строки длины n. Каждая буква каждой строки может быть выбрана из S = {G, T, C, A}. Я знаю, что существует неотрицательная функция стоимости C (x, y), где x в S и y в S, но я не знаю, что это значения явно. Я хочу минимизировать общую стоимость выравнивания этих двух строк. Выравнивание определяется как вставка одинакового количества символов «-» в обе строки. Например, если s1 = GTCA и s2 = ACTG, то одним кандидатом на выравнивание минимальной стоимости будет G-TCA, ACT-G со стоимостью: C (G, A) + C (-, C) + C (T, T) + C (C, -) + C (A, G). Я знаю, что C (-, *) для любого * в {G, T, C, A} равно некоторому постоянному значению ie. 2.
Насколько я понимаю, у этого вопроса есть подзадачи в нескольких измерениях (как длина входных строк, так и количество вставок в строки). Точнее, похоже, что, зная оптимальное выравнивание с GTA, ATG полезна только при попытке решить подзадачу добавления другого «-» в G-TCA, ACT-G. В случае строк длиной 4 существует 16 уникальных расположений, которые являются результатом вставки символа «-» в каждую строку. Каждое из этих выравниваний приводит к 16 различным подзадачам длины 3. Затем в каждом из них будет 9 разных подзадач при рассмотрении добавления второго «-». Затем 4 различных подзадачи при рассмотрении третьего «-». Базовым случаем будет подзадача, включающая строки длины 1. Здесь нам нужно только спросить, можем ли мы сделать что-то лучше, сложив 2 и вычтя C (x, y), где x, y - два последних символа из { GTCA}. Для каждого уровня дерева рекурсии мы должны оценить подзадачу минимальных затрат и посмотреть, было бы полезно добавить ее к минимальной стоимости верхнего уровня. Тем не менее, я все еще не понимаю, даст ли мне правильный ответ вопрос о том, как лучше узнать, где лучше поставить первое «-» в задаче длины 4, или же другое неоптимальное размещение первого «-» станет глобально оптимальным. после добавления еще «-» позже.
В любом случае, я застрял и на данный момент мне просто интересно, можно ли решить эту проблему даже с помощью предоставленной информации. В Интернете довольно много ресурсов, рассказывающих о выравнивании последовательностей, но ни один из них не имеет такой же спецификации, как этот. Будем весьма благодарны за любые мысли или идеи о целесообразности этой проблемы или о лучших способах мышления о структуре.