Алгоритм Ландау-Шмидта — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм)
м (rollbackEdits.php mass rollback)
 
(не показано 30 промежуточных версий 3 участников)
Строка 2: Строка 2:
 
== Определения ==
 
== Определения ==
 
{{Определение
 
{{Определение
|definition=Подстрока <tex>\alpha</tex>, содержащаяся в строке <tex>S</tex>, называется '''тандемным рядом'''(''tandem array'') строки <tex>\beta</tex> ( называемой основой), если а состоит из более чем одной последовательной копии <tex>\beta</tex>.
+
|definition=Подстрока <tex>\alpha</tex>, содержащаяся в строке <tex>S</tex>, называется '''тандемным рядом''' (англ. ''tandem array'') строки <tex>\beta</tex> ( называемой основой), если а состоит из более чем одной последовательной копии <tex>\beta</tex>.
 
}}
 
}}
Например, если <tex>S = xyzabcabcabcabcpq</tex>, то <tex>S = abcabcabcabc</tex> — тандемный ряд строки <tex>\beta = abc</tex>. Заметим, что <tex>S</tex> содержит также тандемный ряд строки <tex>abcabc</tex> ( т.е. тандемный ряд с более длинной основой). Тандемный
+
Например, если <tex>S = xyzabcabcabcabcpq</tex>, то <tex>S = abcabcabcabc</tex> — тандемный ряд строки <tex>\beta = abc</tex>. Заметим, что <tex>S</tex> содержит также тандемный ряд строки <tex>abcabc</tex> ( то есть тандемный ряд с более длинной основой). Тандемный
 
ряд ''максимален'', если он не может быть продолжен ни влево, ни вправо. При фиксированной основе <tex>\beta</tex> тандемный ряд <tex>\beta</tex> в <tex>S</tex> может быть задан парой чисел <tex>( j, k)</tex>, определяющей его начальную позицию в <tex>S</tex> и число повторов <tex>\beta</tex>.
 
ряд ''максимален'', если он не может быть продолжен ни влево, ни вправо. При фиксированной основе <tex>\beta</tex> тандемный ряд <tex>\beta</tex> в <tex>S</tex> может быть задан парой чисел <tex>( j, k)</tex>, определяющей его начальную позицию в <tex>S</tex> и число повторов <tex>\beta</tex>.
 
{{Определение
 
{{Определение
|definition='''Тандемный повтор''' <tex>\alpha</tex> — это строка, которая может быть записана как <tex>\beta\beta</tex>, где <tex>\beta</tex> — подстрока <tex>\alpha</tex>.
+
|definition='''Тандемный повтор''' (англ. ''tandem repeat'') <tex>\alpha</tex> — это строка, которая может быть записана как <tex>\beta\beta</tex>, где <tex>\beta</tex> — подстрока <tex>\alpha</tex>.
 
}}
 
}}
 
Каждый тандемный повтор задается начальной позицией повтора и длиной подстроки <tex>\beta</tex>. Это определение не требует, чтобы <tex>\beta</tex> была максимальной длины. Например,в строке <tex>xababababy</tex> есть шесть тандемных повторов. Два из них начинаются в позиции два: <tex>abab</tex> и <tex>abababab</tex>. В первом случае <tex>\beta = ab</tex>, а во втором <tex>\beta = abab</tex>.
 
Каждый тандемный повтор задается начальной позицией повтора и длиной подстроки <tex>\beta</tex>. Это определение не требует, чтобы <tex>\beta</tex> была максимальной длины. Например,в строке <tex>xababababy</tex> есть шесть тандемных повторов. Два из них начинаются в позиции два: <tex>abab</tex> и <tex>abababab</tex>. В первом случае <tex>\beta = ab</tex>, а во втором <tex>\beta = abab</tex>.
Строка 16: Строка 16:
  
 
== Алгоритм ==
 
== Алгоритм ==
Рещение Ландау-Шмидта — это рекурсивный алгоритм типа "разделяй и властвуй", который основан на возможности вычислять запросы о наибольшем общем продолжении за константное время. Пусть <tex>h = (n/2)</tex>. В укрупненном масштабе метод Ландау-Шмидта делит задачу нахождения всех тандемных повторов на четыре подзадачи:
+
Решение Ландау-Шмидта — это рекурсивный алгоритм типа "разделяй и властвуй", который основан на возможности вычислять запросы о наибольшем общем продолжении за константное время. Пусть <tex>h = \lfloor n/2\rfloor </tex>. В укрупненном масштабе метод Ландау-Шмидта делит задачу нахождения всех тандемных повторов на четыре подзадачи:
  
# Найти все тандемные повторы, содержащиеся целиком в первой половине <tex>S</tex>(до позиции <tex>h</tex> включительно).
+
* Найти все тандемные повторы, содержащиеся целиком в первой половине <tex>S</tex>(до позиции <tex>h</tex> включительно).
# Найти все тандемные повторы, содержащиеся целиком во второй половине <tex>S</tex> (после позиции <tex>h</tex>).
+
* Найти все тандемные повторы, содержащиеся целиком во второй половине <tex>S</tex>(после позиции <tex>h</tex>).
# Найти все тандемные повторы, в которых первая копия покрывает позицию <tex>h</tex>.
+
* Найти все тандемные повторы, в которых первая копия покрывает позицию <tex>h</tex>.
# Найти все тандемные повторы, в которых вторая копия покрывает позицию <tex>h</tex>.
+
* Найти все тандемные повторы, в которых вторая копия покрывает позицию <tex>h</tex>.
  
 
Ясно, что никакой тандемный повтор не может встретиться больше чем в одной из этих подзадач. Первые две подзадачи решаются рекурсивно применением того же алгоритма Ландау-Шмидта. Две последние подзадачи симметричны, поэтому мы рассмотрим только третью подзадачу, и алгоритм для нее определит весь алгоритм.
 
Ясно, что никакой тандемный повтор не может встретиться больше чем в одной из этих подзадач. Первые две подзадачи решаются рекурсивно применением того же алгоритма Ландау-Шмидта. Две последние подзадачи симметричны, поэтому мы рассмотрим только третью подзадачу, и алгоритм для нее определит весь алгоритм.
 
{|border="0" cellpadding="2" width=30% align=right
 
{|border="0" cellpadding="2" width=30% align=right
|[[Файл: tandem.png|thumb|400px|center| Любая позиция между <tex>A</tex> и <tex>B</tex> включительно может быть начальной точкой тандемного повтора длины <tex>2l</tex>. Как указывается в шаге 4, длины <tex>l_1</tex> и <tex>l_2</tex> обе положительны, поэтому подынтервал этих начальных точек определяет тандемные повторы, в которых первая копия покрывает <tex>h</tex>.]]
+
|[[Файл: tandem1.png|thumb|400px|center| Любая позиция между <tex>A</tex> и <tex>B</tex> включительно может быть начальной точкой тандемного повтора длины <tex>2l</tex>. Как указывается в шаге 4, длины <tex>l_1</tex> и <tex>l_2</tex> обе положительны, поэтому подынтервал этих начальных точек определяет тандемные повторы, в которых первая копия покрывает <tex>h</tex>.]]
 
|}
 
|}
===Алгоритм для задачи 3===
+
===Алгоритм для случая с перекрытием===
 
Мы хотим найти все тандемные повторы, у которых первая копия покрывает позицию <tex>h</tex> (но не обязательно начинается в ней). Идея алгоритма заключается в следующем. Для любого фиксированного <tex>l</tex> можно за константное время проверить, существует ли такой тандемный повтор длины <tex>2l</tex>, у которого первая копия покрывает позицию <tex>h</tex>. Применение этого теста ко всем допустимым значениям <tex>l</tex> означает, что за время <tex>O( n)</tex> мы можем найти все длины таких тандемных повторов. Более того, для каждой такой длины мы можем перечислить начальные точки этих тандемных повторов за время, пропорциональное их числу. Ниже описано, как проверить
 
Мы хотим найти все тандемные повторы, у которых первая копия покрывает позицию <tex>h</tex> (но не обязательно начинается в ней). Идея алгоритма заключается в следующем. Для любого фиксированного <tex>l</tex> можно за константное время проверить, существует ли такой тандемный повтор длины <tex>2l</tex>, у которого первая копия покрывает позицию <tex>h</tex>. Применение этого теста ко всем допустимым значениям <tex>l</tex> означает, что за время <tex>O( n)</tex> мы можем найти все длины таких тандемных повторов. Более того, для каждой такой длины мы можем перечислить начальные точки этих тандемных повторов за время, пропорциональное их числу. Ниже описано, как проверить
 
число <tex>l</tex>.
 
число <tex>l</tex>.
  
# Положить <tex>q:=h + l</tex>.
+
# Положить <tex>q = h + l</tex>.
 
# Вычислить наибольшее общее продолжение (в прямом направлении) из позиций <tex>h</tex> и <tex>q</tex>. Пусть <tex>l_1</tex> — длина  этого продолжения.
 
# Вычислить наибольшее общее продолжение (в прямом направлении) из позиций <tex>h</tex> и <tex>q</tex>. Пусть <tex>l_1</tex> — длина  этого продолжения.
 
# Вычислить наибольшее общее продолжение (в обратном направлении) из позиций <tex>h - 1</tex> и <tex>q - 1</tex>. Пусть <tex>l_2</tex> — длина этого продолжения.
 
# Вычислить наибольшее общее продолжение (в обратном направлении) из позиций <tex>h - 1</tex> и <tex>q - 1</tex>. Пусть <tex>l_2</tex> — длина этого продолжения.
# Тандемный повтор длины <tex>2l</tex>, первая копия которого покрывает позицию <tex>h</tex>, существует в том и только том случае, если <tex>l_1 + l_2 \geqslant l</tex> и обе длины <tex>l_1</tex> и <tex>l_2</tex> положительны. Более того, если такой тандемный повтор длины <tex>2l</tex> существует, то он может начинаться в любой позиции от <tex>\max ( h - l_2, h l + 1)</tex> до <tex>\min ( h + l_1 l, h)</tex> включительно. Вторая копия повтора начинается в <tex>l</tex> позициях вправо. Вывести каждую из этих начальных позиций вместе с длиной <tex>2l</tex>.
+
# Тандемный повтор длины <tex>2l</tex>, первая копия которого покрывает позицию <tex>h</tex>, существует в том и только том случае, если <tex>l_1 + l_2 \geqslant l</tex> и обе длины <tex>l_1</tex> и <tex>l_2</tex> положительны. Более того, если такой тандемный повтор длины <tex>2l</tex> существует, то он может начинаться в любой позиции от <tex>\max( h - l_2 ,\ h - l + 1)</tex> до <tex>\min( h + l_1 - l,\ h)</tex> включительно. Вторая копия повтора начинается в <tex>l</tex> позициях вправо. Вывести каждую из этих начальных позиций вместе с длиной <tex>2l</tex>.
 +
 
 
=== Корректность ===
 
=== Корректность ===
  
== Теорема ==
 
 
{{Лемма
 
{{Лемма
|statement = Приведенный метод корректно решает подзадачу 3 для фиксированного <tex>h</tex> Это значит, что он находит все тандемные повторы, у которых первая копия покрывает позицию <tex>h</tex>. Для фиксированного <tex>h</tex> его время работы равно <tex>O( n/2) + z_h</tex>, где <tex>z_h</tex> — число таких тандемных повторов.
+
|statement = Для фиксированного <tex>h</tex> время работы случай с перекрытием равно <tex>O( n/2) + z_h</tex>, где <tex>z_h</tex> — число таких тандемных повторов.
 
|proof =
 
|proof =
 
Предположим сначала, что имеется тандемный повтор, у которого первая копия покрывает позицию h, и его длина равна, скажем, <tex>2l</tex>. Это означает, что позиция <tex>q = h + l</tex> во второй копии соответствует позиции <tex>h</tex> в первойx копии. Следовательно, для того чтобы обеспечить совпадение суффиксов в этих копиях, некоторая подстрока, начинающаяся в <tex>h</tex>, должна совпадать с подстрокой, начинающейся в <tex>q</tex>. Такая подстрока может иметь длину не более <tex>l_1</tex>. Аналогично, должна быть подстрока, кончающаяся в <tex>h - 1</tex>, которая совпадает с подстрокой, кончающейся в <tex>q-1</tex>, для того чтобы обеспечить совпадение префиксов. Длина этой подстроки не должна превосходить <tex>l_2</tex>. Так как все символы между <tex>h</tex> и <tex>q</tex> содержатся в одной из двух копий, то <tex>l_1 + l_2 \geqslant l</tex>. Обратно, рассуждая в основном так же, если <tex> l_1 + l_2 \leqslant l </tex> и <tex>l_1</tex> и <tex>l_2</tex> положительны, то можно найти тандемный повтор длины <tex>2l</tex>, у которого первая копия покрывает <tex>h</tex>. Необходимое и достаточное условие существования такого тандема теперь доказано.
 
Предположим сначала, что имеется тандемный повтор, у которого первая копия покрывает позицию h, и его длина равна, скажем, <tex>2l</tex>. Это означает, что позиция <tex>q = h + l</tex> во второй копии соответствует позиции <tex>h</tex> в первойx копии. Следовательно, для того чтобы обеспечить совпадение суффиксов в этих копиях, некоторая подстрока, начинающаяся в <tex>h</tex>, должна совпадать с подстрокой, начинающейся в <tex>q</tex>. Такая подстрока может иметь длину не более <tex>l_1</tex>. Аналогично, должна быть подстрока, кончающаяся в <tex>h - 1</tex>, которая совпадает с подстрокой, кончающейся в <tex>q-1</tex>, для того чтобы обеспечить совпадение префиксов. Длина этой подстроки не должна превосходить <tex>l_2</tex>. Так как все символы между <tex>h</tex> и <tex>q</tex> содержатся в одной из двух копий, то <tex>l_1 + l_2 \geqslant l</tex>. Обратно, рассуждая в основном так же, если <tex> l_1 + l_2 \leqslant l </tex> и <tex>l_1</tex> и <tex>l_2</tex> положительны, то можно найти тандемный повтор длины <tex>2l</tex>, у которого первая копия покрывает <tex>h</tex>. Необходимое и достаточное условие существования такого тандема теперь доказано.
Строка 45: Строка 45:
 
Обратное доказательство, что все начальные позиции попадают в названный диапазон, аналогично доказывается.
 
Обратное доказательство, что все начальные позиции попадают в названный диапазон, аналогично доказывается.
 
Для подсчета времени сначала отметим, что при фиксированном <tex>h</tex> методу нужно константное время на один выбор <tex>l</tex> для того, чтобы выполнить общие запросы о продолжении, и, таким образом, время <tex>O( n/2)</tex> на все такие запросы. Для любого фиксированного <tex>l</tex> методу нужно константное время на обнаруживаемый тандем, и никакой тандем не обнаруживается дважды, так как у всех обнаруживаемых тандемов длины <tex>2l</tex> стартовые точки различны. Поскольку сообщение о каждом повторе состоит из начальной точки и длины, то алгоритм никогда не сообщает о тандемном повторе дважды. Следовательно, время, расходуемое на вывод информации о тандемных повторах, пропорционально <tex>z_h</tex> — числу повторов, у которых первая копия покрывает позицию <tex>h</tex>.}}
 
Для подсчета времени сначала отметим, что при фиксированном <tex>h</tex> методу нужно константное время на один выбор <tex>l</tex> для того, чтобы выполнить общие запросы о продолжении, и, таким образом, время <tex>O( n/2)</tex> на все такие запросы. Для любого фиксированного <tex>l</tex> методу нужно константное время на обнаруживаемый тандем, и никакой тандем не обнаруживается дважды, так как у всех обнаруживаемых тандемов длины <tex>2l</tex> стартовые точки различны. Поскольку сообщение о каждом повторе состоит из начальной точки и длины, то алгоритм никогда не сообщает о тандемном повторе дважды. Следовательно, время, расходуемое на вывод информации о тандемных повторах, пропорционально <tex>z_h</tex> — числу повторов, у которых первая копия покрывает позицию <tex>h</tex>.}}
 +
Приведенный метод корректно решает случай с перекрытием для фиксированного <tex>h</tex> Это значит, что он находит все тандемные повторы, у которых первая копия покрывает позицию <tex>h</tex>.
 +
 +
Теперь покажем что сам Алгоритм правильный.
 
{{Теорема
 
{{Теорема
|statement = Каждый тандемный повтор в <tex>S</tex> находится решением подзадач 1-4 и при этом только единожды. Время работы алгоритма равно <tex>O( n \log n + z)</tex>, где <tex>z</tex> — число всех тандемных повторов в <tex>S</tex>.
+
|statement = Каждый тандемный повтор в <tex>S</tex> находится единожды. Время работы алгоритма равно <tex>O( n \log n + z)</tex>, где <tex>z</tex> — число всех тандемных повторов в <tex>S</tex>.
 
|proof=
 
|proof=
То, что алгоритм находит все тандемные повторы, прямо следует из факта, что каждый тандем имеет форму, предусмотренную одной из подзадач 1 —4. Чтобы показать, что никакой тандемный повтор не выводится дважды, вспомним, что для <tex>h = n/2</tex> никакой из тандемов не принимает формы, предусмотренной более чем одной из четырех подзадач. Рекурсивно это выполняется для подзадач 1 и 2. Далее, при доказательстве Леммы мы установили, что решение подзадачи 3( а также 4) никогда не получает один и тот же тандем дважды. Следовательно, при полном решении четырех подзадач никакой тандемный повтор не выводится дважды. Отсюда следует, что время вывода всех тандемных повторов равно <tex>O( z)</tex>. Чтобы завершить анализ, рассмотрим время, расходуемое на запросы о продолжении. Это время пропорционально числу выполняемых запросов. Пусть <tex>T( n)</tex> — число запросов при длине строки <tex>n</tex>. Тогда <tex>T( n) = 2T( n/2) + O( n)</tex> и <tex>T( n) = O( n \log n)</tex>, как и утверждалось.}}
+
То, что алгоритм находит все тандемные повторы, прямо следует из факта, что каждый тандем имеет форму, предусмотренную для всех случаев. Чтобы показать, что никакой тандемный повтор не выводится дважды, вспомним, что для <tex>h = n/2</tex> никакой из тандемов не принимает формы, предусмотренной более чем одной из четырех подзадач. Рекурсивно это выполняется для первых двух случаев. Далее, при доказательстве леммы мы установили, что решение подзадачи покрытиями никогда не получает один и тот же тандем дважды. Следовательно, при полном решении четырех подзадач никакой тандемный повтор не выводится дважды. Отсюда следует, что время вывода всех тандемных повторов равно <tex>O( z)</tex>. Чтобы завершить анализ, рассмотрим время, расходуемое на запросы о продолжении. Это время пропорционально числу выполняемых запросов. Пусть <tex>T( n)</tex> — число запросов при длине строки <tex>n</tex>. Тогда <tex>T( n) = 2T( n/2) + O( n)</tex> и <tex>T( n) = O( n \log n)</tex>, как и утверждалось.}}
 +
 
 +
==См. также==
 +
* [[Алгоритм Бойера-Мура]]
 +
* [[Алгоритм Кнута-Морриса-Пратта]]
 +
* [[Алгоритм Крочемора]]
 +
* [[Алгоритм Ландау-Вишкина (k несовпадений)]]
  
 
== Источники информации ==
 
== Источники информации ==
 
* Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. — 2-е изд.
 
* Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. — 2-е изд.
 
* ''Билл Смит'' '''Методы и алгоритмы вычислений на строках'''. Пер. с англ.{{---}} М.:Издательский дом "Вильямс",  2006. ISBN 5-8459-1081-1
 
* ''Билл Смит'' '''Методы и алгоритмы вычислений на строках'''. Пер. с англ.{{---}} М.:Издательский дом "Вильямс",  2006. ISBN 5-8459-1081-1
* [http://neerc.ifmo.ru/wiki/index.php?title=%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%9A%D1%80%D0%BE%D1%87%D0%B5%D0%BC%D0%BE%D1%80%D0%B0 Алгоритм-Крочемора]
 
* [http://e-maxx.ru/algo/string_tandems Алгоритм Мейна-Лоренца]
 
* [http://digitool.library.colostate.edu/webclient/DeliveryManager?pid=166681 Michael G. Main and Richard J. Lorentz An O( n log n) Algorithm for Finding All Repetitions in a String]
 
 
* [http://cs.haifa.ac.il/LANDAU/gadi/LSS.pdf  Landau, G.M.,  J.P. Schmidt and D. Sokol. An algorithm for approximate tandem repeats]
 
* [http://cs.haifa.ac.il/LANDAU/gadi/LSS.pdf  Landau, G.M.,  J.P. Schmidt and D. Sokol. An algorithm for approximate tandem repeats]
  
[[Категория: Поиск тандемных повторов]]
+
[[Категория: Основные определения. Простые комбинаторные свойства слов]]
 
[[Категория: Алгоритмы и структуры данных]]
 
[[Категория: Алгоритмы и структуры данных]]
[[Категория: Дискретная математика и алгоритмы]]
 

Текущая версия на 19:29, 4 сентября 2022

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

Определение:
Тандемный повтор (англ. tandem repeat) [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]h = \lfloor n/2\rfloor [/math]. В укрупненном масштабе метод Ландау-Шмидта делит задачу нахождения всех тандемных повторов на четыре подзадачи:

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

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

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

Алгоритм для случая с перекрытием

Мы хотим найти все тандемные повторы, у которых первая копия покрывает позицию [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].

Корректность

Лемма:
Для фиксированного [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]h[/math] Это значит, что он находит все тандемные повторы, у которых первая копия покрывает позицию [math]h[/math].

Теперь покажем что сам Алгоритм правильный.

Теорема:
Каждый тандемный повтор в [math]S[/math] находится единожды. Время работы алгоритма равно [math]O( n \log n + z)[/math], где [math]z[/math] — число всех тандемных повторов в [math]S[/math].
Доказательство:
[math]\triangleright[/math]
То, что алгоритм находит все тандемные повторы, прямо следует из факта, что каждый тандем имеет форму, предусмотренную для всех случаев. Чтобы показать, что никакой тандемный повтор не выводится дважды, вспомним, что для [math]h = n/2[/math] никакой из тандемов не принимает формы, предусмотренной более чем одной из четырех подзадач. Рекурсивно это выполняется для первых двух случаев. Далее, при доказательстве леммы мы установили, что решение подзадачи покрытиями никогда не получает один и тот же тандем дважды. Следовательно, при полном решении четырех подзадач никакой тандемный повтор не выводится дважды. Отсюда следует, что время вывода всех тандемных повторов равно [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
  • Landau, G.M., J.P. Schmidt and D. Sokol. An algorithm for approximate tandem repeats