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

Определение:

Графом де Брюина (англ. De Bruijn graph) с параметром [math]l[/math] для [math]n[/math]-буквенного алфавита называется ориентированный граф [math]G(V, E)[/math], где [math] V - [/math] множество всех слов длины [math]l[/math] в заданном алфавите, и [math]e = (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] |V| = n^l [/math]. Очевидно из определения [math] V [/math].
• [math] l = 1 \Leftrightarrow G - [/math] полный граф.

Действительно, для любых (необязательно различных) вершин [math] u, v \ \exists L = \alpha \beta [/math], где [math] \alpha, \beta - [/math] слова (символы), соответствующие вершинам [math] u, v [/math]. И тогда очевидно, что существует ребро [math] e = (u, v)\ \forall u, v \in V [/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] G - [/math] эйлеров.

Это следует из предыдущего свойства, так как число входящих и исходящих рёбер равны.

• [math] e = (u, v) \in E \Leftrightarrow [/math] [math] prefix_{l-1}(v) = suffix_{l-1}(u) [/math].

[math] \Leftarrow [/math] Составим слово [math] L = a \gamma b [/math], где [math] \gamma - [/math] общая часть слов, соответствующих вершинам [math] u, v [/math]. А символы [math] a, b \ - [/math] первый и последний символ этих слов соответственно. Из определения графа де Брюина следует, что ребро существует.

[math] \Rightarrow [/math] Возьмём подстроку слова [math] L [/math] (из определения) без крайних символов (её длина [math] l - 1 [/math]). Так же из определения следует, что это будет суффиксом строки, соответствующей вершине [math] u [/math], и префиксом для строки, соответствующей [math] v [/math].

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

Задача:

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

Алгоритм:

1. Создаём пустой граф из [math] n^l [/math] вершин.

2. Генерируем слово длины [math] l+1 [/math].

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

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

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

Время работы: [math] O(n^{l+1} \cdot substring) = O(|E| \cdot l) [/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] e_1 = (u_1, v_1), e_2 = (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]. То есть это одно и то же ребро, при этом кратных рёбер в графе нет.

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

Решение:

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

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

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

См. также

• Основные определения, связанные со строками
• Эйлеровость графов
• Алгоритм построения Эйлерова цикла

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

• Wikipedia — De Bruijn graph
• Нурк Сергей — Разработка алгоритмов обработки графа де Брюина в задаче геномного ассемблирования