Я только что реализовал алгоритм Гото, как расширение алгоритма Нидлмана-Вунша для штрафов за аффинный пробел. Я наткнулся на этот сайт: http://florianerhard.github.io/2016/gotoh3 Автор предлагает упростить алгоритм возврата. Я пытался понять, как это сделать, но я не мог ничего понять.
Он пишет:
Таким образом, при каноническом возврате каждый член будет пересчитываться максимально и продолжить запись, получая наибольшее значение (которое является значением в текущей ячейке), тем самым переключаясь между тремя матрицами. Как указано выше, это довольно сложно реализовать. Но есть и более простой способ: представьте, что вы заполнили матрицу A алгоритмом Уотермана, Смита и Бейера (алгоритм cubi c для общих функций затрат на разрыв)! Просто проверьте Ai − 1, j − 1, Di, j и Ii, j; если это Ai − 1, j − 1, вы знаете, где продолжить возврат; если это Di, j, вы знаете, что вам нужно go влево, поэтому просто go k шагов влево до Ai, j − k + g (k) = Ai, j и продолжайте с Ai, j − k. Угадайте, что вам следует делать, если это Ii, j…
Поэтому обычно вы начинаете с нижнего правого угла i, j и уровня, который имеет наивысший балл в этой позиции. Тогда уровень, на котором вы находитесь, диктует следующую клетку, к которой вы go. A означает A, D или I (i-1, j-1) + счет матча, D означает A или D (i-1, j) + gapOpen (A) или gapExtend (D), а I означает A или I (i , j-1) + GapOpen (A) или GapExtend (I).
Я не понимаю, почему автор сравнивает Ai − 1, j − 1, Di, j и Ii, j на первом этапе не должно ли это быть Di-1, J-1 и Ii-1, J-1? Я смущен. Может кто знает, как именно это работает и может немного объяснить? Спасибо.