Пример классического алгоритма обработки паттернов: имеется строка (иногда называемая текстом) и требуется найти одно или все вхождения в нее другой заданной строки (которая называется паттерном). Такую операцию, например, многократно (за один сеанс работы) выполняют текстовые редакторы. Другой пример этой задачи не такой очевидный: молекулярные биологи получают из международной базы данных генетической информации сегменты ДНК длиной 65 5 млн комплиментарных пар оснований нуклеиновых кислот (в нашей терминологии — это строка из 5 млн букв) для определения местоположения в этом большом сегменте отдельных коротких сегментов ДНК, состоящих из 300 комплиментарных пар оснований нуклеиновых кислот.

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

       р = CGAT

и допустима перестановка двух первых или двух последних букв, тогда р и GCAT и р% CGTA. Поэтому в строке

       х = ТСТ AGGCGATTCGGC AT ATTCGCGT AGCTCTА

НЕ нашли? Не то? Что вы ищете?

подчеркнутые подстроки будут считаться совпадающими с паттерном р. Основная идея в использовании аппроксимирующих (приближенных) паттернов состоит в определении "расстояния" между двумя строками. В общем случае расстояние между строками p1 и р2 рассчитывается как взвешенное количество стандартных операций редактирования, необходимых для выполнения преобразования p1 в p2.

Обычно рассматривают следующие операции редактирования:

    Вставка — например, вставка символа G в строку GCAT сформирует строку GCGAT. Удаление — например, удаление символа G из строки GCGAT сформирует строку CGAT. Подстановка — например, подстановка символа G вместо символа С из строки GCAT сформирует строку GGAT.

       Конечно, перечисленные операции определены только для непустых символов. На основе этих операций можно определить несколько типов расстояния между строками, некоторые из которых мы сейчас рассмотрим.

Если две строки x1 и x2 имеют одинаковую длину n, расстояние Хемминга dH{х1, x2) определяется как минимальное количество подстановок, необходимых для преобразования строки х1 в строку х2. Так, dH(GCAT, CGAT) = 2. Отметим, что для замены некоего символа x1 на какой-нибудь другой может потребоваться одна операция удаления этого символа и одна операция вставки нового символа после предыдущего символа. Для произвольных строк х1 и х2 расстояние Левенштейна dL(x1,,x2) определяется как минимальное количество операций удаления и вставки, необходимых для преобразования строки х1 в строку х2. Так, dL(GCAT, CGAT) = 2, но

dL(GCGAT, CGAT) = dL{CAT, CGAT) = 1.

Если строки x1 и x2 имеют одинаковую длину, то совсем не обязательно, что dH(х1,x2) = dL(x1, x2).

Например, если х1 = CGA и x2 = AGT, то dH(CGA, AGT) = 2,  тогда как dL(CGA, AG'T) = 4. Отметим, что последовательность операций удаления и вставки, преобразующих строку х1 в строку х2, может определяться неоднозначно, даже если общее количество таких операций одинаково. Например, строку GGATA можно преобразовать в строку ATACG путем применения четырех операций удаления символов CG и AT и последующих четырех вставок символов AT и CG либо путем применения двух операций удаления префикса CG и последующих двух вставок суффикса CG.

Для произвольных строк х1 и x2 расстояние преобразования dE{x1, x2) определяется как минимальное количество операций удаления, вставки и подстановки, необходимых для преобразования строки х1 в строку х2.

Здесь предполагается, что подстановка одной буквы вместо другой выполняется за одну операцию, тогда как при вычислении расстояния dL подстановка выполняется за две операции: удаление и последующая вставка. Чтобы лучше понять, как dE соотносится с dH и dL, рассмотрим строки х1 = CGACG и x2 = GTCGA. Для этих строк dH{x1, x2) = 5, поскольку ни на одном месте в этих строках нет попарно совпадающих букв, и поэтому для получения из одной строки другой требуется ровно пять подстановок. Но dL(x1, x2) = 4, так как необходимо удалить префикс С, вставить суффикс А и заменить букву А на букву Т, для чего потребуется одна операция удаления и одна операция вставки. Однако dE(x1, x2) = 3, поскольку здесь для замены буквы А на букву Т требуется только одна операция.

Предыдущие определения расстояния основаны на том, что все операции редактирования подсчитываются с одинаковыми значениями. Однако покрайней мере для операции подстановки одинаковые не всегда верно значения отражают условия решаемой задачи. Например, если некоторые подстановки (скажем, С —> G) выполняются чаще или с большей вероятностью, чем другие подстановки (например, С —> Т). Чтобы отобразить такие различия, разным подстановкам назначаются разные веса, которые представляются в виде матрицы весов W. (Так, например, делается в молекулярной биологии.) Матрица весов имеет размерность ахай состоит из не отрицательных действительных чисел, где число W[i, j] является весом замены (подстановки) j-й буквы 1-й буквой алфавита А. Для произвольных строк x1 и x2 взвешенное расстояние dW(x1, x2) определяется как минимальная сумма количества операций удаления и вставки и весов операций подстановок, необходимых для преобразования строки х1 в строку х1, при этом веса задаются матрицей весов W. .

       Обычно требуется, чтобы функция расстояния d, определенная на какой-либо области D, удовлетворяла условиям метрики: для любых u, v, w принадлежащих  D:

    d(u, v) >= 0 - условие неотрицательности d(u, v) = 0 <=> +u = v - условие единственности d(u, v) = d(v, u)  - условие симметричности d(u, v) <= d(u, v) + d(v, w)  - неравенство треугольника

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

       2.4 Онлайновые алгоритмы обработки последовательностей

       Просмотр строковых последовательностей естественно выполнять слева направо. Поэтому чрезвычайно привлекательным свойством строковых алгоритмов считается их онлайновость. Это означает, что если в процессе вычислений уже просмотрена позиция i в строковой последовательности, то алгоритм уже не вернется к этой позиции i снова. Другими словами, онлайновый алгоритм никогда не выполняет возврата к уже просмотренным позициям.

       Существует также более слабое определение онлайновых алгоритмов. Например, алгоритм называется онлайновым с окном размера k, если существует такая положительная константа k, что для выполнения вычислений в текущей позиции i требуется не более k строковых позиций из интервала i — k + 1..i Еще одно подобное слабое определение позволяет считать алгоритм онлайновым, если значение, вычисляемое алгоритмом для любой позиции i, никогда не пересчитывается, даже если потребуется заново обратиться к позициям  меньше i.

       Из любого сделанного выше определения онлайновости следует, что строковый онлайновый алгоритм при решении определенной задачи для строки x = x[1..п] эффективно решает ту же задачу для каждого префикса x[1..i] этой строки. Таким образом, можно сказать, что онлайновый алгоритм фактически решает n задач по цене одной задачи.

       Например, онлайновым является алгоритм Кнута-Мориса-Пратта для вычисления всех вхождений шаблона p в шаблон x. Основная идея этого  алгоритма заключается в последовательном сдвиге паттерна p вдоль строковой последовательности x и сравнении его с просматриваемым участком последовательности х так. При этом паттерн р сдвигается на следующую букву вдоль строки х только в том случае, когда р не совпадает с текущим участком последовательности х.

       Рассмотрим этот алгоритм на примере

x = an, p = am-1b, 2 <= m <= n

       В этом примере после сравнения с подстрокой x[1..m] мы будем располагать информацией, что

x[1..m — 1] = p[1..m — 1] = am-1

       Чтобы проверить, будет ли паттерн p совпадать с подстрокой x[2..m + 1], нет необходимости проводить сравнения в подстроке x[2..m — 1], поскольку уже известно, что

x[2..m — 1] = am-2,

поэтому следует провести только одно сравнение x[m] : p[m - 1], и в случае равенства этих букв, мы фиксируем несовпадение

x[m + 1] ≠ b = p[m]

       Применяя эту стратегию в каждой позиции i <= n — m + 1, можно показать, что выполняется всего 2n - m  буквенных сравнений, а не m(n  - m + 1),, как можно было ожидать.        На этом примере показана основная особенность алгоритма -  сравнения

x[i..i + h — 1] = p[1..h], 1 <= h <= m

можно (частично или полностью) использовать для избежания дальнейшей проверки подстроки u = x[i..i + h - 1]. Если паттерн р входит в строку х в некоторой позиции i' принадлежащей i..i + h — 1, тогда строкa u = p[1..h] имеет не пустой собственный префикс

p[1..h'], h' = i + h — i',

а также суффикс x[i'..i + h — 1]. Другими словами, подстрока p[l..h'] должна быть гранью строки u = p[l..h].

       Таким образом, с помощью граней строки г надо определить только те позиции i', в которых может встретиться р. Но поскольку u — это подстрока p[l..h] паттерна р для некоторого h принадлежащего 1..m, то нет необходимости вычислять грани строки u в процессе выполнения алгоритма — можно вычислить их заранее и сохранить в массиве граней β = β[1..m]. Поэтому алгоритм Кнута-Мориса-Пратта имеет предварительный этап, на котором вычисляется массив B. [1]

Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 6 7