Алгоритм Ландау-Шмидта

Алгоритм Ландау-Шмидта — алгоритм на строках, позволяющий найти все тандемные повторы в строке [math]S[1..n][/math] за [math]O(n \log n + z)[/math], где [math]z[/math] — полное число тандемных повторов в [math]S[/math]. Было опубликовано в журнале [of Computational Biology] 2001 году.

Определения

Определение:

Подстрока [math]\alpha[/math], содержащаяся в строке [math]S[/math], называется тандемным рядом(tandem array) строки [math]\beta[/math] (называемой основой), если а состоит из более чем одной последовательной копии [math]\beta[/math].

Например, если [math]S = xyzabcabcabcabcpq[/math], то [math]S = abcabcabcabc[/math] — тандемный ряд строки [math]\beta = abc[/math]. Заметим, что [math]S[/math] содержит также тандемный ряд строки [math]abcabc[/math] (т.е. тандемный ряд с более длинной основой). Тандемный ряд максимален, если он не может быть продолжен ни влево, ни вправо. При фиксированной основе [math]\beta[/math] тандемный ряд [math]\beta[/math] в [math]S[/math] может быть задан парой чисел [math](j, k)[/math], определяющей его начальную позицию в [math]S[/math] и число повторов [math]\beta[/math].

Определение:

Тандемный повтор [math]\alpha[/math] — это строка, которая может быть записана как [math]\beta\beta[/math], где [math]\beta[/math] — подстрока [math]\alpha[/math].

Каждый тандемный повтор задается начальной позицией повтора и длиной подстроки [math]\beta[/math]. Это определение не требует, чтобы [math]\beta[/math] была максимальной длины. Например,в строке [math]xababababy[/math] есть шесть тандемных повторов. Два из них начинаются в позиции два: [math]abab[/math] и [math]abababab[/math]. В первом случае [math]\beta = ab[/math], а во втором [math]\beta = abab[/math].

Определение:

Тандемным повтором точности [math]k[/math] называется подстрока, которая становится тандемным повтором после изменения не более [math]k[/math] символов.

Например, [math]axabaybb[/math] — тандемный повтор точности [math]2[/math].

Алгоритм

Метод нахождения всех тандемных повторой за время [math]O(n \log n + z)[/math], где [math]z[/math] — полное число тандемных повторов в [math]S[/math]. Метод разработали Ландау и Шмидт. Рещение Ландау-Шмидта — это рекурсивный алгоритм типа "разделяй и властвуй", который основан на возможности вычислять запросы о наибольшем общем продолжении за константное время. Пусть [math]h = [n/2][/math]. В укрупненном масштабе метод Ландау-Шмидта делит задачу нахождения всех тандемных повторов на четыре подзадачи:

1. Найти все тандемные повторы, содержащиеся целиком в первой половине [math]S[/math](до позиции [math]h[/math] включительно).
2. Найти все тандемные повторы, содержащиеся целиком во второй половине [math]S[/math] (после позиции [math]h[/math]).
3. Найти все тандемные повторы, в которых первая копия покрывает позицию [math]h[/math].
4. Найти все тандемные повторы, в которых вторая копия покрывает позицию [math]h[/math].

Ясно, что никакой тандемный повтор не может встретиться больше чем в одной из этих подзадач. Первые две подзадачи решаются рекурсивно применением того же алгоритма Ландау-Шмидта. Две последние подзадачи симметричны, поэтому мы рассмотрим только третью подзадачу, и алгоритм для нее определит весь алгоритм.

Любая позиция между [math]A[/math] и [math]B[/math] включительно может быть начальной точкой тандемного повтора длины [math]2l[/math]. Как указывается в шаге 4, длины [math]l_1[/math] и [math]l_2[/math] обе положительны, поэтому подынтервал этих начальных точек определяет тандемные повторы, в которых первая копия покрывает [math]h[/math].

Алгоритм для задачи 3 Мы хотим найти все тандемные повторы, у которых первая копия покрывает позицию [math]h[/math] (но не обязательно начинается в ней). Идея алгоритма заключается в следующем. Для любого фиксированного [math]l[/math] можно за константное время проверить, существует ли такой тандемный повтор длины [math]2l[/math], у которого первая копия покрывает позицию [math]h[/math]. Применение этого теста ко всем допустимым значениям [math]l[/math] означает, что за время [math]O(n)[/math] мы можем найти все длины таких тандемных повторов. Более того, для каждой такой длины мы можем перечислить начальные точки этих тандемных повторов за время, пропорциональное их числу. Ниже описано, как проверить число [math]l[/math].

1. Положить [math]q:=h + l[/math].
2. Вычислить наибольшее общее продолжение (в прямом направлении) из позиций [math]h[/math] и [math]q[/math]. Пусть [math]l_1[/math] — длина этого продолжения.
3. Вычислить наибольшее общее продолжение (в обратном направлении) из позиций [math]h - 1[/math] и [math]q - 1[/math]. Пусть [math]l_2[/math] — длина этого продолжения.
4. Тандемный повтор длины [math]2l[/math], первая копия которого покрывает позицию [math]h[/math], существует в том и только том случае, если [math]l_1 + l_2 \geqslant l[/math] и обе длины [math]l_1[/math] и [math]l_2[/math] положительны. Более того, если такой тандемный повтор длины [math]2l[/math] существует, то он может начинаться в любой позиции от [math]\max (h - l_2, h — l + 1)[/math] до [math]\min (h + l_1 — l, h)[/math] включительно. Вторая копия повтора начинается в [math]l[/math] позициях вправо. Вывести каждую из этих начальных позиций вместе с длиной [math]2l[/math].

Теорема

Лемма:

Приведенный метод корректно решает подзадачу 3 для фиксированного [math]h[/math] Это значит, что он находит все тандемные повторы, у которых первая копия покрывает позицию [math]h[/math]. Для фиксированного [math]h[/math] его время работы равно [math]O(n/2) + z_h[/math], где [math]z_h[/math] — число таких тандемных повторов.

Доказательство:

[math]\triangleright[/math]

Предположим сначала, что имеется тандемный повтор, у которого первая копия покрывает позицию h, и его длина равна, скажем, [math]2l[/math]. Это означает, что позиция [math]q = h + l[/math] во второй копии соответствует позиции [math]h[/math] в первойx копии. Следовательно, для того чтобы обеспечить совпадение суффиксов в этих копиях, некоторая подстрока, начинающаяся в [math]h[/math], должна совпадать с подстрокой, начинающейся в [math]q[/math]. Такая подстрока может иметь длину не более [math]l_1[/math]. Аналогично, должна быть подстрока, кончающаяся в [math]h - 1[/math], которая совпадает с подстрокой, кончающейся в [math]q-1[/math], для того чтобы обеспечить совпадение префиксов. Длина этой подстроки не должна превосходить [math]l_2[/math]. Так как все символы между [math]h[/math] и [math]q[/math] содержатся в одной из двух копий, то [math]l_1 + l_2 \geqslant l[/math]. Обратно, рассуждая в основном так же, если [math] l_1 + l_2 \leqslant l [/math] и [math]l_1[/math] и [math]l_2[/math] положительны, то можно найти тандемный повтор длины [math]2l[/math], у которого первая копия покрывает [math]h[/math]. Необходимое и достаточное условие существования такого тандема теперь доказано. Обратное доказательство, что все начальные позиции попадают в названный диапазон, аналогично доказывается. Для подсчета времени сначала отметим, что при фиксированном [math]h[/math] методу нужно константное время на один выбор [math]l[/math] для того, чтобы выполнить общие запросы о продолжении, и, таким образом, время [math]O(n/2)[/math] на все такие запросы. Для любого фиксированного [math]l[/math] методу нужно константное время на обнаруживаемый тандем, и никакой тандем не обнаруживается дважды, так как у всех обнаруживаемых тандемов длины [math]2l[/math] стартовые точки различны. Поскольку сообщение о каждом повторе состоит из начальной точки и длины, то алгоритм никогда не сообщает о тандемном повторе дважды. Следовательно, время, расходуемое на вывод информации о тандемных повторах, пропорционально [math]z_h[/math] — числу повторов, у которых первая копия покрывает позицию [math]h[/math].

[math]\triangleleft[/math]

Теорема:

Каждый тандемный повтор в [math]S[/math] находится решением подзадач 1-4 и при этом только единожды. Время работы алгоритма равно [math]O(n \log n + z)[/math], где [math]z[/math] — полное число тандемных повторов в [math]S[/math].

Доказательство:

[math]\triangleright[/math]

То, что алгоритм находит все тандемные повторы, прямо следует из факта, что каждый тандем имеет форму, предусмотренную одной из подзадач 1 —4. Чтобы показать, что никакой тандемный повтор не выводится дважды, вспомним, что для [math]h = n/2[/math] никакой из тандемов не принимает формы, предусмотренной более чем одной из четырех подзадач. Рекурсивно это выполняется для подзадач 1 и 2. Далее, при доказательстве Леммы мы установили, что решение подзадачи 3(а также 4) никогда не получает один и тот же тандем дважды. Следовательно, при полном решении четырех подзадач никакой тандемный повтор не выводится дважды. Отсюда следует, что время вывода всех тандемных повторов равно [math]O(z)[/math]. Чтобы завершить анализ, рассмотрим время, расходуемое на запросы о продолжении. Это время пропорционально числу выполняемых запросов. Пусть [math]T(n)[/math] — число запросов при длине строки [math]n[/math]. Тогда [math]T(n) = 2T(n/2) + O(n)[/math] и [math]T(n) = O(n \log n)[/math], как и утверждалось.

[math]\triangleleft[/math]

Источники информации

• Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. — 2-е изд.
• Билл Смит Методы и алгоритмы вычислений на строках. Пер. с англ.— М.:Издательский дом "Вильямс", 2006. ISBN 5-8459-1081-1
• Алгоритм-Крочемора
• Алгоритм Мейна-Лоренца
• Michael G. Main and Richard J. Lorentz An O(n log n) Algorithm for Finding All Repetitions in a String
• Landau, G.M., J.P. Schmidt and D. Sokol. An algorithm for approximate tandem repeats