Графы де Брюина — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Алгоритм построения)
м (rollbackEdits.php mass rollback)
 
(не показано 13 промежуточных версий 4 участников)
Строка 1: Строка 1:
 
{{Определение
 
{{Определение
 
|id = de_bruijn_graph
 
|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) </tex> и <tex> v = suffix(L) </tex>. Обозначается как <tex> B(n, l) </tex>
+
|definition = '''Графом де Брюина''' (англ. ''De Bruijn graph'') с параметром <tex>l</tex> для <tex>n</tex>-буквенного алфавита называется ориентированный граф <tex>G(V, E)</tex>, где <tex> V - </tex> множество всех слов длины <tex>l</tex> в заданном алфавите, и <tex>(u, v) \in E \Leftrightarrow \exists </tex> слово <tex>L</tex> длины <tex>l+1</tex> в заданном алфавите такое, что <tex> u = prefix(L) </tex> и <tex> v = suffix(L) </tex>. Обозначается как <tex> B(n, l) </tex>
 
}}
 
}}
  
Строка 9: Строка 9:
 
|id = lem1
 
|id = lem1
 
|about = об эйлеровости графа
 
|about = об эйлеровости графа
|statement= Граф де Брюина <tex> - </tex> эйлеров
+
|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> эйлеров.
 
|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> эйлеров.
 
}}
 
}}
Строка 16: Строка 16:
 
|id = lem2
 
|id = lem2
 
|about = о количестве вершин и рёбер в графе
 
|about = о количестве вершин и рёбер в графе
|statement= В графе де Брюина <tex> B(n, l): |V| = n^l, |E| = n^{l+1}</tex>
+
|statement= В <tex> B(n, l) |V| = n^l, |E| = n^{l+1}</tex>
|proof= Число вершин очевидно находится из определения графа и равно <tex> n^l </tex>. Число рёбер следует из доказательства предыдущей леммы: каждой вершине инцидентно ровно <tex> 2 </tex> ребра. Таким образом, <tex> |E| = \frac{1}{2} \cdot n^l \cdot 2n  = n^{l+1} </tex>  
+
|proof= Число вершин очевидно находится из определения графа и равно <tex> n^l </tex>. Число рёбер следует из доказательства предыдущей леммы: каждой вершине инцидентно ровно <tex> 2n </tex> ребер. Значит, <tex> |E| = n^{l+1} </tex> по [[Лемма о рукопожатиях | лемме о рукопожатиях]].
 
}}
 
}}
  
Строка 23: Строка 23:
 
|id = lem3
 
|id = lem3
 
|about = о равносильном определении
 
|about = о равносильном определении
|statement= В графе де Брюина <tex> B(n, l): e = (u, v) \in E \Leftrightarrow </tex> <tex> prefix_{l-1}(v) = suffix_{l-1}(u) </tex>
+
|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>
 
|proof= <tex> \Leftarrow </tex>
Составим слово <tex> L = a \gamma b </tex>, где <tex> \gamma - </tex> общая часть слов, соответствующих вершинам <tex> u, v </tex>. А символы <tex> a, b \ - </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> \Rightarrow </tex> Возьмём подстроку слова <tex> L </tex> (из определения) без крайних символов (её длина <tex> l - 1  </tex>). Так же из определения следует, что это будет суффиксом строки, соответствующей вершине <tex> u </tex>, и префиксом для строки, соответствующей <tex> v </tex>.
Возьмём подстроку слова <tex> L </tex> (из определения) без крайних символов (её длина <tex> l - 1  </tex>). Так же из определения следует, что это будет суффиксом строки, соответствующей вершине <tex> u </tex>, и префиксом для строки, соответствующей <tex> v </tex>.
 
 
}}
 
}}
  
Строка 34: Строка 33:
 
|id = lem4
 
|id = lem4
 
|about = о графе с <tex> l = 1 </tex>
 
|about = о графе с <tex> l = 1 </tex>
|statement= Граф де Брюина <tex> B(n, 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> e = (u, v)\  \forall u, v \in V </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>.
 
}}
 
}}
  
Строка 46: Строка 45:
 
'''Алгоритм: '''
 
'''Алгоритм: '''
  
1. Создаём пустой граф из <tex> n^l </tex> вершин.
+
1. Создаём пустой граф из <tex> n^l </tex> вершин. Установим в алфавите отношение порядка и будем рассматривать его символы как цифры в <tex> n </tex>-значной системе счисления.
  
2. Генерируем слово длины <tex> l+1 </tex>.
+
2. Генерируем минимальное в лексикографическом порядке слово длины <tex> l+1 </tex>, которое ещё не было использовано (порядок может быть любым, главное перебрать все такие слова без повторений).
  
3. Считаем префикс <tex> pref </tex> и суффикс <tex> suff </tex> длины <tex> l </tex> для текущего. Причём установим в алфавите отношение порядка и будем рассматривать его символы как цифры в <tex> n </tex>-значной системе счисления.  
+
3. Считаем префикс <tex> pref </tex> и суффикс <tex> suff </tex> длины <tex> l </tex> для текущего.
  
4. Проводим ребро <tex> (pref, suff) </tex> в графе. Переходим к пункту <tex> 2 </tex> (например, будем перебирать в порядке лексикографического возрастания), пока не будут перебраны все слова длины <tex> l+1 </tex>.
+
4. Проводим ребро <tex> (pref, suff) </tex> в графе. Переходим к пункту <tex> 2 </tex>, пока не будут перебраны все слова длины <tex> l+1 </tex>.
  
 
'''Корректность''': перебраны все слова длины <tex> l+1 </tex>, следовательно, были рассмотрены все возможные пары вершин, между которыми проведено ребро.
 
'''Корректность''': перебраны все слова длины <tex> l+1 </tex>, следовательно, были рассмотрены все возможные пары вершин, между которыми проведено ребро.
  
'''Время работы''': <tex> O(n^{l+1} \cdot substring) = O(|E| \cdot l) </tex>
+
'''Время работы''': <tex> O(n^{l+1} \cdot substring) = O(|E| \cdot l) </tex>, где <tex> substring - </tex> время генерации слова, а так же поиска префикса и суффикса в нём.
  
 
== Применение графов де Брюина ==
 
== Применение графов де Брюина ==
Строка 79: Строка 78:
 
1. Очевидно, что последовательность меньшей длины составить нельзя: в полученной последовательности ровно <tex> n^l </tex> подстрок длины <tex> l </tex>, и именно столько чисел можно составить из цифр от <tex> 1 </tex> до <tex> n </tex>.
 
1. Очевидно, что последовательность меньшей длины составить нельзя: в полученной последовательности ровно <tex> n^l </tex> подстрок длины <tex> l </tex>, и именно столько чисел можно составить из цифр от <tex> 1 </tex> до <tex> n </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} </tex> и <tex> v_{1} = suffix(L) = v_{2} </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>. То есть это одно и то же ребро, при этом кратных рёбер в графе нет.
  
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> 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>.
  
 
{{Задача
 
{{Задача
Строка 92: Строка 93:
 
'''Пояснение''':
 
'''Пояснение''':
  
Геном (как и его части <tex> - </tex> риды) является словом из 4-символьного алфавита <tex> \{A, G, C, T\} </tex>, где символы так же называются нуклеотидами. В реальности длины ридов находятся обычно в диапазоне <tex> 100 </tex>-<tex> 1000 </tex> нуклеотидов, а геном может содержать от <tex> 10^6 </tex> нуклеотидов у простейших организмов. При этом учёные могут получать информацию только о ридах (в силу размера последовательностей) физическим путем (''метод секвенирования'').
+
Геном (как и его части <tex> - </tex> риды) является словом из <tex>4</tex>-символьного алфавита <tex> \{A, G, C, T\} </tex>, где символы так же называются нуклеотидами. В реальности длины ридов находятся обычно в диапазоне <tex> 100 </tex>-<tex> 1000 </tex> нуклеотидов, а геном может содержать от <tex> 10^6 </tex> нуклеотидов у простейших организмов. При этом учёные могут получать информацию только о ридах (в силу размера последовательностей) физическим путем (''метод секвенирования'').
  
 
'''Решение''':
 
'''Решение''':
  
Решение этой задачи очень простое после решения предыдущей задачи. Построим граф G, где вершинами будут являться суффиксы и префиксы длины <tex> l - 1 </tex> всех ридов. Получили подграф графа де Брюина <tex> (4, l-1) </tex> (подграф, так как в нём есть не обязательно все <tex> 4^{l - 1} </tex> вершины), где каждому ребру соответствует рид. Найдём в нём эйлеров путь. Он существует, так как на геном было наложено условие о том, что все его подстроки длины <tex> l </tex> входят в наше множество ридов. Этот путь является возможным ответом. Очевидно, что единственно верный ответ (коим является реальный геном реального существа) получить можно не всегда, так как не всегда в графе есть единственный эйлеров путь.
+
Решение этой задачи очень простое после решения предыдущей задачи. Построим граф <tex> G </tex>, где вершинами будут являться суффиксы и префиксы длины <tex> l - 1 </tex> всех ридов. Получили подграф графа де Брюина <tex> (4, l-1) </tex> (подграф, так как в нём есть не обязательно все <tex> 4^{l - 1} </tex> вершины), где каждому ребру соответствует рид. Найдём в нём эйлеров путь. Он существует, так как на геном было наложено условие о том, что все его подстроки длины <tex> l </tex> входят в наше множество ридов. Этот путь является возможным ответом. Очевидно, что единственно верный ответ (коим является реальный геном реального существа) получить можно не всегда, так как не всегда в графе есть единственный эйлеров путь.
  
 
'''Комментарий''':
 
'''Комментарий''':

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

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


Основные свойства

Лемма (об эйлеровости графа):
[math]B(n, l)\ - [/math] эйлеров
Доказательство:
[math]\triangleright[/math]
Ориентированный граф является эйлеровым, если число входящих рёбер равно числу исходящих. Докажем, что это верно для [math] B(n, l) [/math]. А именно, что [math] \forall v \in V [/math] верно, что [math] deg_{out}(v) = n = deg_{in}(v)[/math]. Докажем первое равенство, второе аналогично. Существует ровно [math] n [/math] символов алфавита, которые можно добавить в конец слова [math] \alpha[/math], соответствующему вершине [math] v [/math]. Получим ровно [math] n [/math] различных слов. И у всех этих слов различные суффиксы длины [math] l [/math]. Таким образом, из вершины [math] v [/math] выходит ровно [math] n [/math] рёбер и входит тоже [math] n [/math] рёбер. Значит, граф де Брюина [math] - [/math] эйлеров.
[math]\triangleleft[/math]
Лемма (о количестве вершин и рёбер в графе):
В [math] B(n, l) \ |V| = n^l, |E| = n^{l+1}[/math]
Доказательство:
[math]\triangleright[/math]
Число вершин очевидно находится из определения графа и равно [math] n^l [/math]. Число рёбер следует из доказательства предыдущей леммы: каждой вершине инцидентно ровно [math] 2n [/math] ребер. Значит, [math] |E| = n^{l+1} [/math] по лемме о рукопожатиях.
[math]\triangleleft[/math]
Лемма (о равносильном определении):
В [math] B(n, l) \ (u, v) \in E \Leftrightarrow [/math] [math] prefix_{l-1}(v) = suffix_{l-1}(u) [/math]
Доказательство:
[math]\triangleright[/math]

[math] \Leftarrow [/math] Составим слово длины [math]l+1 \ L = a \gamma b [/math], тогда [math] \gamma b = suffix(L), a \gamma = prefix(L) [/math] . Если выбрать [math] a, b \ [/math] как первый и последний символ слов [math] u, v [/math] соответственно, и взять [math] \gamma = prefix_{l-1}(v) = suffix_{l-1}(u) [/math], то ребро между этими вершинами есть по определению.

[math] \Rightarrow [/math] Возьмём подстроку слова [math] L [/math] (из определения) без крайних символов (её длина [math] l - 1 [/math]). Так же из определения следует, что это будет суффиксом строки, соответствующей вершине [math] u [/math], и префиксом для строки, соответствующей [math] v [/math].
[math]\triangleleft[/math]
Лемма (о графе с [math] l = 1 [/math]):
[math] B(n, 1)\ - [/math] полный граф.
Доказательство:
[math]\triangleright[/math]
Действительно, для любых (необязательно различных) вершин [math] u, v \ \exists L = \alpha \beta [/math], где [math] \alpha, \beta - [/math] слова (символы), соответствующие вершинам [math] u, v [/math]. И тогда очевидно, что существует ребро [math](u, v)\ \forall u, v \in V [/math].
[math]\triangleleft[/math]

Алгоритм построения

Задача:
Дан алфавит длины [math] n [/math] и длина слов [math] l [/math]. Построить по ним граф де Брюина.

Алгоритм:

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

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

3. Считаем префикс [math] pref [/math] и суффикс [math] suff [/math] длины [math] l [/math] для текущего.

4. Проводим ребро [math] (pref, suff) [/math] в графе. Переходим к пункту [math] 2 [/math], пока не будут перебраны все слова длины [math] l+1 [/math].

Корректность: перебраны все слова длины [math] l+1 [/math], следовательно, были рассмотрены все возможные пары вершин, между которыми проведено ребро.

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

Применение графов де Брюина

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


Построенный граф Де Брюина для двоичного алфавита со словами [math] L [/math] (из определения) на рёбрах

Решение:

1. Составим граф де Брюина [math] (n, l-1) [/math].

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

3. Слово, соответствующее первой вершине цикла, возьмём полностью ([math] l - 1 [/math] символов), затем будем последовательно добавлять в конец строки последний символ слова вершины, в которую был осуществлён переход. Так как рёбер [math] n^l [/math], получим последовательность длиной [math] n^l + l - 1 [/math].

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

1. Очевидно, что последовательность меньшей длины составить нельзя: в полученной последовательности ровно [math] n^l [/math] подстрок длины [math] l [/math], и именно столько чисел можно составить из цифр от [math] 1 [/math] до [math] n [/math].

2. Двум разным рёбрам [math](u_1, v_1), (u_2, v_2) [/math] соответствует два различных слова [math] L [/math] длины [math] l [/math]. Иначе [math] u_{1} = prefix(L) = u_{2} [/math] и [math] v_{1} = suffix(L) = v_{2} [/math]. То есть это одно и то же ребро, при этом кратных рёбер в графе нет.

Вывод:

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


Задача:
Даны неповторяющиеся последовательности нуклеотидов (риды) длины [math] l [/math]. Известно, что все подстроки генома длины [math] l [/math] входят в данное множество ридов. Построить возможный геном.


Подграф графа Де Брюина для ридов, указанных на рёбрах. Искомый геном: ACGTACTAT

Пояснение:

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

Решение:

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

Комментарий:

К сожалению, кроме того, что алгоритм работает за [math] O(4^l \cdot l) [/math], в реальности есть немало технических проблем:

1. Как можно догадаться из пояснения: едва ли риды обязательно будут неповторяющимися.

2. Данные о ридах могут быть получены лишь с некоторой вероятностью (как правило, ошибка в нуклеотиде имеет вероятность около [math] 0.001 [/math], но вблизи "края" генома она может достигать и [math] 0.3 [/math]).

3. Риды не могут иметь фиксированную длину в силу особенностей метода секвенирования.

Вывод:

Несмотря на то, что задача не решается в общем случае приведённым алгоритмом, граф де Брюина действительно используется в ассемблерах (программах, собирающих геном или его большие части из ридов), но с заметными усложнениями.

См. также

Источники информации