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

Основные определения

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

Графом де Брюина (англ. 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) \wedge 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] deg(v) = 0 [/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], и состоит из цифр от 1 до [math] n [/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], и именно столько чисел можно составить из цифр от 1 до [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} \wedge 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] входят в данное множество ридов. Построить возможный геном.

Пояснение:

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

См. также

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

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

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