Изменения

|definition = '''Графом де Брюина''' (англ. ''De Bruijn graph'') с параметром <tex>l</tex> для <tex>n</tex>-буквенного алфавита называется ориентированный граф <tex>G(V, E)</tex>, где <tex> V - </tex> множество всех слов длины <tex>l</tex> в заданном алфавите, и <tex>e = (u, v) \in E \Leftrightarrow \exists </tex> слово <tex>L</tex> длины <tex>l+1</tex> в заданном алфавите такое, что <tex> u = prefix(L) \wedge </tex> и <tex> v = suffix(L) </tex>. Обозначается как <tex> B(n, l) </tex>

{{Лемма|id = lem1|about = об эйлеровости графа|statement= <tex>B(n, l)\ - </tex> эйлеров|proof= Ориентированный граф является эйлеровым, если число входящих рёбер равно числу исходящих. Докажем, что это верно для <tex> B(n, l) </tex>. А именно, что <tex> \forall v \in V </tex> верно, что <tex> deg_{out}(v) = n = deg_{in}(v)</tex>. Докажем первое равенство, второе аналогично. Существует ровно <tex> n </tex> символов алфавита, которые можно добавить в конец слова <tex> \alpha</tex>, соответствующему вершине <tex> v </tex>. Получим ровно <tex> n </tex> различных слов. И у всех этих слов различные суффиксы длины <tex> l </tex>. Таким образом, из вершины <tex> v </tex> выходит ровно <tex> n </tex> рёбер и входит тоже <tex> n </tex> рёбер. Значит, граф де Брюина <tex> - </tex> эйлеров.}} {{Лемма|id = lem2|about = о количестве вершин и рёбер в графе|statement= В <tex> B(n, l) \ |V| = n^l, |E| = n^{l+1}</tex>|proof= Число вершин очевидно находится из определения графа и равно <tex> n^l </tex>. Число рёбер следует из доказательства предыдущей леммы: каждой вершине инцидентно ровно <tex> 2n </tex> ребер. Значит, <tex> |E| = n^{l+1} </tex> по [[Лемма о рукопожатиях | лемме о рукопожатиях]].}} {{Лемма|id = lem3|about = о равносильном определении|statement= В <tex> B(n, l) \ (u, v) \in E \Leftrightarrow </tex> <tex> prefix_{l-1}(v) = suffix_{l-1}(u) </tex>|proof= <tex> \Leftarrow </tex>Составим слово длины <tex>l+1 \ L = a \gamma b </tex>, тогда <tex> \gamma b = suffix(L), a \gamma = prefix(L) </tex> . Если выбрать <tex> a, b \ </tex> как первый и последний символ слов <tex> u, v </tex> соответственно, и взять <tex> \gamma = prefix_{l-1}(v) = suffix_{l-1}(u) </tex>, то ребро между этими вершинами есть по определению.  <tex> \Rightarrow </tex>Возьмём подстроку слова <tex> L </tex> (из определения) без крайних символов (её длина <tex> l - 1 </tex>). Так же из определения следует, что это будет суффиксом строки, соответствующей вершине <tex> u </tex>, и префиксом для строки, соответствующей <tex> v </tex>.}} {{Лемма|id = lem4|about = о графе с <tex> l = 1 </tex>|statement= <tex> B(n, 1)\ - </tex> полный граф.|proof = Действительно, для любых (необязательно различных) вершин <tex> u, v \ \exists L = \alpha \beta </tex>, где <tex> \alpha, \beta - </tex> слова (символы), соответствующие вершинам <tex> u, v </tex>. И тогда очевидно, что существует ребро <tex>(u, v)\ \forall u, v \in V </tex>.}}

1. Создаём пустой граф из <tex> n^l </tex> вершин. Установим в алфавите отношение порядка и будем рассматривать его символы как цифры в <tex> n </tex>-значной системе счисления.

2. Генерируем минимальное в лексикографическом порядке слово длины <tex> l+1 </tex>, которое ещё не было использовано (порядок может быть любым, главное перебрать все такие слова без повторений).

3. Считаем префикс <tex> pref </tex> и суффикс <tex> suff </tex> длины <tex> l </tex> для текущего. Причём установим в алфавите отношение порядка и будем рассматривать его символы как цифры в <tex> n </tex>-значной системе счисления.

4. Проводим ребро <tex> (pref, suff) </tex> в графе. Переходим к п.пункту <tex> 2 (например, будем перебирать в порядке лексикографического возрастания)</tex>, пока не будут перебраны все слова длины <tex> l+1 </tex>.

'''Время работы''': <tex> O(n^{l+1} \cdot substring) = O(|E| \cdot l) </tex>, где <tex> substring - </tex> время генерации слова, а так же поиска префикса и суффикса в нём.

Известно, что пароль имеет длину <tex> l </tex>, и состоит из цифр от <tex> 1 </tex> до <tex> n </tex>. Требуется вывести кратчайшую последовательность цифр, которая гарантированно содержит пароль как подстроку.

2. Найдём в построенном графе эйлеров цикл. Он существует, так как граф де Брюина эйлеров (смпо первой лемме. свойства)

1. Очевидно, что последовательность меньшей длины составить нельзя: в полученной последовательности ровно <tex> n^l </tex> подстрок длины <tex> l </tex>, и именно столько чисел можно составить из цифр от <tex> 1 </tex> до <tex> n </tex>. 2. Двум разным рёбрам <tex>(u_1, v_1), (u_2, v_2) </tex> соответствует два ''различных'' слова <tex> L </tex> длины <tex> l </tex>. Иначе <tex> u_{1} = prefix(L) = u_{2} </tex> и <tex> v_{1} = suffix(L) = v_{2} </tex>. То есть это одно и то же ребро, при этом кратных рёбер в графе нет.

2. Двум разным рёбрам <tex> e_1 = (u_1, v_1), e_2 = (u_2, v_2) </tex> соответствует два ''различных'Вывод' слова <tex> L </tex> длины <tex> l </tex>. Иначе <tex> u_{1} = prefix(L) = u_{2} \wedge v_{1} = suffix(L) = v_{2} </tex>. То есть это одно и то же ребро, при этом кратных рёбер в графе нет.'':

3. Отсюда Из доказательства корректности следует, что в последовательности содержится <tex> n^l </tex> различных подстрок длины <tex> l </tex>. И короче последовательность получить нельзя. Значит, мы Мы получили ответ за <tex> O((|E| \cdot (l-1)) + (|E| + |V|)) = O(|E| \cdot (l-1)) </tex>, то есть за время построения графа де Брюина <tex> (n, l-1) </tex>.

Геном (как и его части <tex> - </tex> риды) является словом из <tex>4</tex>-символьного алфавита <tex> \{A, G, C, T\} </tex>, где символы так же называются нуклеотидами. В реальности длины ридов находятся обычно в диапазоне <tex> 100</tex>-<tex> 1000 </tex> нуклеотидов, а геном может содержать от <tex> 10^6 </tex> нуклеотидов у простейших организмов. При этом учёные могут получать информацию только о ридах (в силу размера последовательностей) физическим путем (''метод секвенирования'').

Решение этой задачи очень простое после решения предыдущей задачи. Построим граф <tex> G</tex>, где вершинами будут являться суффиксы и префиксы длины <tex> l - 1 </tex> всех ридов. Получили подграф графа де Брюина <tex> (4, l-1) </tex> (подграф, так как в нём есть не обязательно все <tex> 4^{l - 1} </tex> вершины), где каждому ребру соответствует рид. Найдём в нём эйлеров циклпуть. Он существует, так как на геном было наложено условие о том, что все его подстроки длины <tex> l </tex> входят в наше множество ридов. Этот цикл путь является возможным ответом. Очевидно, что единственно верный ответ (коим является реальный геном реального существа) получить мы можно не сможемвсегда, потому что так как не всегда в графе есть единственный эйлеров цикл может быть не единственным, и цикл можно сдвигатьпуть.

К сожалению, в реальности есть очень много проблем (кроме того, что алгоритм работает за <tex> O(4^l \cdot l) </tex>), в реальности есть немало технических проблем: 1. Во-первых, как Как можно догадаться из пояснения: едва ли риды обязательно будут неповторяющимися. Во-вторых, данные  2. Данные о ридах тоже получаются могут быть получены лишь с некоторой вероятностью (как правило, ошибка в нуклеотиде имеет вероятность около <tex> 0.001</tex>, но вблизи "края" генома она может достигать и <tex> 0.3</tex>). В-третьих, риды  3. Риды не могут иметь фиксированную длинув силу особенностей метода секвенирования. Таким образом '''Вывод''': Несмотря на то, что задача не решается за экспоненциальное времяв общем случае приведённым алгоритмом, и с довольно жёсткими условиями на входные данные. Однако многие реальные граф де Брюина действительно используется в ''ассемблерыассемблерах''(программах, собирающие геномы (собирающих геном или их его большие части, заметно превышающие размер ридаиз ридов), действительно используют идеи графа де Брюина, но более усложнённыес заметными усложнениями.

[[Категория: Теория Обходы графов]]