42
правки
Изменения
→Определения
|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>\beta</tex> тандемный ряд <tex>\beta</tex> в <tex>S</tex> может быть задан парой чисел <tex>( j, k)</tex>, определяющей его начальную позицию в <tex>S</tex> и число повторов <tex>\beta</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>h = (\lfloor n/2)\rfloor </tex>. В укрупненном масштабе метод Ландау-Шмидта делит задачу нахождения всех тандемных повторов на четыре подзадачи:
* Найти все тандемные повторы, содержащиеся целиком в первой половине <tex>S</tex>(до позиции <tex>h</tex> включительно).
{{Лемма
|statement = Для фиксированного <tex>h</tex> время работы 3й подзадачи случай с перекрытием равно <tex>O( n/2) + z_h</tex>, где <tex>z_h</tex> — число таких тандемных повторов.
|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>. Необходимое и достаточное условие существования такого тандема теперь доказано.
Обратное доказательство, что все начальные позиции попадают в названный диапазон, аналогично доказывается.
Для подсчета времени сначала отметим, что при фиксированном <tex>h</tex> методу нужно константное время на один выбор <tex>l</tex> для того, чтобы выполнить общие запросы о продолжении, и, таким образом, время <tex>O( n/2)</tex> на все такие запросы. Для любого фиксированного <tex>l</tex> методу нужно константное время на обнаруживаемый тандем, и никакой тандем не обнаруживается дважды, так как у всех обнаруживаемых тандемов длины <tex>2l</tex> стартовые точки различны. Поскольку сообщение о каждом повторе состоит из начальной точки и длины, то алгоритм никогда не сообщает о тандемном повторе дважды. Следовательно, время, расходуемое на вывод информации о тандемных повторах, пропорционально <tex>z_h</tex> — числу повторов, у которых первая копия покрывает позицию <tex>h</tex>.}}
Приведенный метод корректно решает подзадачу 3 случай с перекрытием для фиксированного <tex>h</tex> Это значит, что он находит все тандемные повторы, у которых первая копия покрывает позицию <tex>h</tex>.
Теперь покажем что сам Алгоритм правильный.
|statement = Каждый тандемный повтор в <tex>S</tex> находится единожды. Время работы алгоритма равно <tex>O( n \log n + z)</tex>, где <tex>z</tex> — число всех тандемных повторов в <tex>S</tex>.
|proof=
То, что алгоритм находит все тандемные повторы, прямо следует из факта, что каждый тандем имеет форму, предусмотренную для всех случаев. Чтобы показать, что никакой тандемный повтор не выводится дважды, вспомним, что для <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>, как и утверждалось.}}
==См. также==
* Гасфилд Д. Строки, деревья и последовательности в алгоритмах: Информатика и вычислительная биология. — 2-е изд.
* ''Билл Смит'' '''Методы и алгоритмы вычислений на строках'''. Пер. с англ.{{---}} М.:Издательский дом "Вильямс", 2006. ISBN 5-8459-1081-1
* [http://cs.haifa.ac.il/LANDAU/gadi/LSS.pdf Landau, G.M., J.P. Schmidt and D. Sokol. An algorithm for approximate tandem repeats]
[[Категория: Поиск тандемных повторовОсновные определения. Простые комбинаторные свойства слов]]
[[Категория: Алгоритмы и структуры данных]]
