Алгоритм Нудельмана-Вунша

Пример из молекулярной биологии. Молекулы ДНК, содержащие генетическую информацию - это длинные слова из четырех букв (А, Г, Ц, Т). В процессе эволюции, в результате мутаций, последовательности меняются, одна буква может замениться на другую, выпасть, а может добавиться новая. Насколько похожи два фрагмента, каким наименьшим числом превращений можно один из них получить из другого? Формулировка задачи. Даны два слова (длины M и N), состоящие из букв А, Г, Ц, Т. Найти подпоследовательность наибольшей длины, входящую в то и другое слово.

Пример. Слова ГЦАТАГГТЦ и АГЦААТГГТ. Схема решения иллюстрируется следующим рисунком.

На рисунке закрашены клетки, в строке и в столбце которых находятся одинаковые буквы. Принцип заполнения таблицы W следующий: элемент W[i,j] равен наибольшему из чисел W[i-1,j], W[i,j-1], а если клетка <i,j> закрашена, то и W[i-1,j-1]+1. Формирование первой строки и первого столбца выполняется до заполнения таблицы и осуществляется так: единицей отмечается первое совпадение, затем эта единица автоматически заносится во все оставшиеся клетки. Например, W[3,1] - первое совпадение в столбце, затем эта единица идет по первому столбцу. Подпоследовательность формируется при обратном просмотре заполненной таблицы от клетки, помеченной максимальным значением. Путь - это клетки с метками, отличающимися на единицу, буквы из закрашенных клеток выписываются. Последовательность этих букв - ответ задачи. Для нашего примера две подпоследовательности: ГЦААГГТ и ГЦАТГГТ.

Фрагмент основной логики.

...

for i:=1 to Length(S1) do

for j:=1 to Length(S2) do begin

A[i,j]:=Max(A[i-1,j],A[i,j-1]);

if S1[i]=S2[j] then A[i,j]:=Max(A[i,j],A[i-1,j-1]+1);

end;

Writeln(‘Ответ: ’,A[Length(S1),Length(S2)]);

....

Дата добавления: 2014-11-28