Изменения

|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> V u </tex>, и префиксом для строки, соответствующей <tex> v </tex>.* }} {{Лемма|id = lem4|about = о графе с <tex> l = 1 </tex>|statement= <tex> B(n, 1)\Leftrightarrow G - </tex> полный граф. |proof = Действительно, для любых (необязательно различных) вершин <tex> u, v \ \exists L = \alpha \beta </tex>, где <tex> \alpha, \beta - </tex> слова (символы), соответствующие вершинам <tex> u, v </tex>. И тогда очевидно, что существует ребро <tex> e = (u, v)\ \forall u, v \in V </tex>.* }} == Алгоритм построения == {{Задача|definition =Дан алфавит длины <tex> n </tex> и длина слов <tex> l </tex>. Построить по ним граф де Брюина.}}'''Алгоритм: ''' 1. Создаём пустой граф из <tex> n^l </tex> вершин. Установим в алфавите отношение порядка и будем рассматривать его символы как цифры в <tex> n </tex>-значной системе счисления. 2. Генерируем минимальное в лексикографическом порядке слово длины <tex> l+1 </tex>, которое ещё не было использовано (порядок может быть любым, главное перебрать все такие слова без повторений). 3. Считаем префикс <tex> pref </tex> и суффикс <tex> suff </tex> длины <tex> l </tex> для текущего. 4. Проводим ребро <tex> (pref, suff) </tex> в графе. Переходим к пункту <tex> 2 </tex>, пока не будут перебраны все слова длины <tex> l+1 </tex>. '''Корректность''': перебраны все слова длины <tex> \forall v \in V l+1 </tex> верно, что следовательно, были рассмотрены все возможные пары вершин, между которыми проведено ребро. '''Время работы''': <tex> deg_O(n^{outl+1}\cdot substring) = O(v|E| \cdot l) </tex>, где <tex> substring - </tex> время генерации слова, а так же поиска префикса и суффикса в нём. == Применение графов де Брюина = n = deg_ {{inЗадача|definition =Известно, что пароль имеет длину <tex> l </tex>, и состоит из цифр от <tex> 1 </tex> до <tex> n </tex>. Требуется вывести кратчайшую последовательность цифр, которая гарантированно содержит пароль как подстроку.}} [[Файл: De_brujin_binary_graph.png‎|справа|400px|thumb|Построенный граф Де Брюина для двоичного алфавита со словами <tex> L </tex> (из определения) на рёбрах]] '''Решение''': 1. Составим граф де Брюина <tex> (vn, l-1)</tex>. Докажем первое равенство 2. Найдём в построенном графе эйлеров цикл. Он существует, второе аналогичнотак как граф де Брюина эйлеров по первой лемме. 3. Существует ровно Слово, соответствующее первой вершине цикла, возьмём полностью (<tex> n l - 1 </tex> символов алфавита), которые можно добавить затем будем последовательно добавлять в конец строки последний символ слова вершины, в которую был осуществлён переход. Так как рёбер <tex> \alphan^l </tex>, соответствующему вершине получим последовательность длиной <tex> v n^l + l - 1 </tex>. Получим  '''Корректность''': 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>. То есть это одно и то же ребро, при этом кратных рёбер в графе нет. '''Вывод''': Из доказательства корректности следует, что в последовательности содержится <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>. {{Задача|definition = Даны неповторяющиеся последовательности ''нуклеотидов'' (''риды'') длины <tex> l </tex>. Известно, что все подстроки генома длины <tex> l </tex>входят в данное множество ридов. Построить возможный геном. Таким образом}} [[Файл: De Brujin Graph In Science.png‎|справа|400px|thumb|Подграф графа Де Брюина для ридов, указанных на рёбрах. Искомый геном: '''ACGTACTAT''']] '''Пояснение''': Геном (как и его части <tex> - </tex> риды) является словом из вершины <tex> v 4</tex>-символьного алфавита <tex> \{A, G, C, T\} </tex>, где символы так же называются нуклеотидами. В реальности длины ридов находятся обычно в диапазоне <tex> 100 </tex>-<tex> 1000 </tex> нуклеотидов, а геном может содержать от <tex> 10^6 </tex> выходит ровно n рёбернуклеотидов у простейших организмов. При этом учёные могут получать информацию только о ридах (в силу размера последовательностей) физическим путем (''метод секвенирования'').* '''Решение''': Решение этой задачи очень простое после решения предыдущей задачи. Построим граф <tex> G </tex>, где вершинами будут являться суффиксы и префиксы длины <tex> l - 1 </tex> всех ридов. Получили подграф графа де Брюина <tex> (4, l- 1) </tex> (подграф, так как в нём есть не обязательно все <tex> 4^{l - 1} </tex> вершины), где каждому ребру соответствует рид. Найдём в нём эйлеровпуть. Он существует, так как на геном было наложено условие о том, что все его подстроки длины <tex> l </tex> входят в наше множество ридов. Этот путь является возможным ответом. Это следует из предыдущего свойстваОчевидно, что единственно верный ответ (коим является реальный геном реального существа) получить можно не всегда, так как не всегда в графе есть единственный эйлеров путь. '''Комментарий''': К сожалению, кроме того, что алгоритм работает за <tex> degO(v4^l \cdot l) = </tex>, в реальности есть немало технических проблем: 1. Как можно догадаться из пояснения: едва ли риды обязательно будут неповторяющимися.  2. Данные о ридах могут быть получены лишь с некоторой вероятностью (как правило, ошибка в нуклеотиде имеет вероятность около <tex> 0.001 </tex>, но вблизи "края" генома она может достигать и <tex> 0 .3 </tex>). 3. Риды не могут иметь фиксированную длину в силу особенностей метода секвенирования. '''Вывод''': Несмотря на то, что задача не решается в общем случае приведённым алгоритмом, граф де Брюина действительно используется в ''ассемблерах'' (программах, собирающих геном или его большие части из ридов), но с заметными усложнениями. == См. также == * [[Основные определения, связанные со строками]]* [[Эйлеровость графов]]* [[Алгоритм построения Эйлерова цикла]] == Источники информации == * [https://en.wikipedia.org/wiki/De_Bruijn_graph Wikipedia {{---}} De Bruijn graph]* [http://se.math.spbu.ru/SE/diploma/2011/Nurk%20Sergej%20-%20text.pdf Нурк Сергей {{---}} Разработка алгоритмов обработки графа де Брюина в задаче геномного ассемблирования] [[Категория: Дискретная математика и алгоритмы]][[Категория: Обходы графов]]