Изменения

Перейти к: навигация, поиск

Графы де Брюина

9037 байт добавлено, 23:09, 8 декабря 2017
Основные свойства
== Основные определения ==
 
{{Определение
|id = de_bruijn_graph
|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>
}}
== Основные свойства ==
* <tex> |V| = n^l </tex>. Очевидно из определения <tex> V </tex>.
* <tex> l = 1 \Leftrightarrow G - </tex> полный граф.
Действительно, для любых (необязательно различных) вершин <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>.
* <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> G - </tex> эйлеров.
Это следует из предыдущего свойства, так как <tex> deg(v) = 0 </tex>.
* <tex> e = (u, v) \in E \Leftrightarrow </tex> <tex> prefix_{l-1}(v) = suffix_{l-1}(u) </tex>.
<tex> \Leftarrow </tex>
Составим слово <tex> L = a \gamma b </tex>, где <tex> \gamma - </tex> общая часть слов, соответствующих вершинам <tex> u, v </tex>. А символы <tex> a, b \ - </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> l+1 </tex>, следовательно, были рассмотрены все возможные пары вершин, между которыми проведено ребро.
'''Время работы''': <tex> O(n^{l+1} \cdot substring) = O(|E| \cdot l) </tex>, где <tex> substring - </tex> время генерации слова, а так же поиска префикса и суффикса в нём. == Применение графов де Брюина == {{Задача|definition =Известно, что пароль имеет длину <tex> l </tex>, и состоит из цифр от <tex> 1 </tex> до <tex> n </tex>. Требуется вывести кратчайшую последовательность цифр, которая гарантированно содержит пароль как подстроку.}} [[Файл: De_brujin_binary_graph.png‎|справа|400px|thumb|Построенный граф Де Брюина для двоичного алфавита со словами <tex> L </tex> (из определения) на рёбрах]] '''Решение''': 1. Составим граф де Брюина <tex> (n, l-1) </tex>. 2. Найдём в построенном графе эйлеров цикл. Он существует, так как граф де Брюина эйлеров по первой лемме. 3. Слово, соответствующее первой вершине цикла, возьмём полностью (<tex> l - 1 </tex> символов), затем будем последовательно добавлять в конец строки последний символ слова вершины, в которую был осуществлён переход. Так как рёбер <tex> n^l </tex>, получим последовательность длиной <tex> 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>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. Риды не могут иметь фиксированную длину в силу особенностей метода секвенирования. '''Вывод''': Несмотря на то, что задача не решается в общем случае приведённым алгоритмом, граф де Брюина действительно используется в ''ассемблерах'' (программах, собирающих геном или его большие части из ридов), но с заметными усложнениями. == См. также == * [[Основные определения, связанные со строками]]* [[Эйлеровость графов]]* [[Алгоритм построения Эйлерова цикла]] == Источники информации == * [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 Нурк Сергей {{---}} Разработка алгоритмов обработки графа де Брюина в задаче геномного ассемблирования]
== Использование [[Категория: Дискретная математика и алгоритмы]][[Категория: Обходы графов де Брюина ==]]
Анонимный участник

Навигация