График де Брёйна

В теории графов граф $n$ -мерный Де Брейна из $m$ символов представляет собой ориентированный граф, представляющий перекрытия между последовательностями символов. У него есть $м н$ вершины , состоящие из всех возможных последовательностей длиной $n$ заданных символов; один и тот же символ может появляться в последовательности несколько раз. Для набора из $m$ символов $S = {s 1, \dots, s m}$ набор вершин равен:

V=S^{n}=\{(s_{1},\dots ,s_{1},s_{1}),(s_{1},\dots ,s_{1},s_{2}),\dots ,(s_{1},\dots ,s_{1},s_{m}),(s_{1},\dots ,s_{2},s_{1}),\dots ,(s_{m},\dots ,s_{m},s_{m})\}.

Если одну из вершин можно выразить как другую вершину, сдвинув все ее символы на одно место влево и добавив в конце этой вершины новый символ, то последняя имеет направленное ребро к первой вершине. Таким образом, набор дуг (то есть направленных ребер) равен

E=\{((t_{1},t_{2},\dots ,t_{n}),(t_{2},\dots ,t_{n},s_{j})):t_{i}\in S,1\leq i\leq n,1\leq j\leq m\}.

Хотя графы Де Брейна названы в честь Николааса Говерта де Брейна , они были изобретены независимо обоими де Брейном. ^[1] и Эй Джей Гуд . ^[2] Намного раньше Камилла Флай Сент-Мари ^[3] неявно использовали их свойства.

Характеристики

Если $n = 1$ , то условие для любых двух вершин, образующих ребро, выполняется бессмысленно , и, следовательно, все вершины связаны, образуя в общей сложности $m 2$ края.
Каждая вершина имеет ровно $m$ входящих и $m$ исходящих ребер.
Каждый $n-$ мерный граф Де Брейна представляет собой линейный орграф графа $(n - 1)$ -мерного Де Брейна с тем же набором символов. ^[4]
Каждый граф Де Брейна является эйлеровым и гамильтоновым . Циклы Эйлера и гамильтоновы циклы этих графов (эквивалентные друг другу посредством конструкции линейного графа) являются последовательностями Де Брейна .

Ниже изображена конструкция линейного графа трех наименьших двоичных графов Де Брейна. Как видно на иллюстрации, каждая вершина $n$ -мерного графа Де Брейна соответствует ребру $(n - 1)$ -мерного графа Де Брейна, а каждое ребро в $n$ -мерном графе Де Брейна соответствует двумерному графу Де Брейна. -реберный путь в $(n - 1)$ -мерном графе Де Брейна.

Изображение, показывающее несколько графиков Де Брейна, каждый из которых представляет собой линейный график предыдущего.

Динамические системы

Бинарные графы Де Брейна можно нарисовать таким образом, что они напоминают объекты из теории динамических систем , такие как аттрактор Лоренца :

Двоичный граф Де Брейна

Аттрактор Лоренца

Эту аналогию можно сделать строгой: $n$ -мерный $m$ -символьный граф Де Брейна является моделью отображения Бернулли.

x\mapsto mx\ {\bmod {\ }}1.

Отображение Бернулли (также называемое $отображением 2 x mod 1$ для $m = 2$ ) представляет собой динамическую систему, которую можно понимать как одиночный сдвиг m $эргодическую$ -адического числа . ^[5] Траектории этой динамической системы соответствуют блужданиям в графе Де Брейна, где соответствие задается путем отображения каждого действительного $x$ в интервале $[0,1)$ в вершину, соответствующую первым $n$ цифрам в по основанию - $m$ представлении $x$ . . Эквивалентно, блуждания в графе Де Брёйна соответствуют траекториям в одностороннем сдвиге конечного типа .

Подобные вложения можно использовать, чтобы показать, что двоичные графы Де Брейна имеют очередь номер 2. ^[6] и что у них толщина книги максимум 5. ^[7]

Использование

Некоторые топологии грид-сетей представляют собой графы Де Брёйна.
Протокол таблицы распределенной хэш - Koorde использует граф Де Брейна.
В биоинформатике графы Де Брёйна используются для de novo сборки считываний секвенирования в геном . ^[8]^[9]^[10]^[11]^[12]

См. также

Ссылки

^ де Брейн, НГ (1946). «Комбинаторная задача». Математические исследования . 49 : 758–764. МР 0018142 .
^ Хорошо, Эй Джей (1946). «Обычные повторяющиеся десятичные дроби». Журнал Лондонского математического общества . 21 (3): 167–169. дои : 10.1112/jlms/s1-21.3.167 .
^ Флай Сент-Мари, К. (1894). «Вопрос 48». Посредник математиков . 1 :107–110.
^ Чжан, Фу Цзи; Линь, Го Нин (1987). «О графиках де Брейна – Гуда». Акта Математика Синика . 30 (2): 195–205.
^ Леру, Филипп (2005). «Коассоциативная грамматика, периодические орбиты и квантовое случайное блуждание по $\mathbb {Z}$ " . Международный журнал математики и математических наук . 2005 (24): 3979–3996. arXiv : quant-ph/0209100 . doi : 10.1155/IJMMS.2005.3979 . MR 2204471 .
^ Хит, Ленвуд С.; Розенберг, Арнольд Л. (1992). «Построение графиков с помощью очередей». SIAM Journal по вычислительной технике . 21 (5): 927–958. дои : 10.1137/0221055 . МР 1181408 .
^ Обренич, Бояна (1993). «Вложение графов де Брёйна и тасования-обмена на пяти страницах». SIAM Journal по дискретной математике . 6 (4): 642–654. дои : 10.1137/0406049 . МР 1241401 .
^ Певзнер Павел Александрович ; Тан, Хайсюй; Уотерман, Майкл С. (2001). «Подход Эйлера к сборке фрагментов ДНК» . Труды Национальной академии наук . 98 (17): 9748–9753. Бибкод : 2001PNAS...98.9748P . дои : 10.1073/pnas.171285098 . ПМЦ 55524 . ПМИД 11504945 .
^ Певзнер Павел Александрович ; Тан, Хайсюй (2001). «Сборка фрагментов с двуствольными данными» . Биоинформатика . 17 (Приложение 1): С225–С233. doi : 10.1093/биоинформатика/17.suppl_1.S225 . ПМИД 11473013 .
^ Зербино, Дэниел Р.; Бирни, Юэн (2008). «Бархат: алгоритмы сборки короткого чтения de novo с использованием графов де Брёйна» . Геномные исследования . 18 (5): 821–829. дои : 10.1101/гр.074492.107 . ПМК 2336801 . ПМИД 18349386 .
^ Чихи, Р.; Лимассет, А.; Джекман, С.; Симпсон, Дж.; Медведев, П. (2014). «О представлении графов де Брейна». Журнал вычислительной биологии . 22 (5): 336–52. arXiv : 1401.5383 . дои : 10.1089/cmb.2014.0160 . ПМИД 25629448 . S2CID 9502231 .
^ Икбал, Замин; Каккамо, Марио; Тернер, Исаак; Фличек, Пол; Маквин, Гил (2012). «Сборка de novo и генотипирование вариантов с использованием цветных графов де Брёйна» . Природная генетика . 44 (2): 226–32. дои : 10.1038/ng.1028 . ПМЦ 3272472 . ПМИД 22231483 .

Внешние ссылки

[Bruijn1946-1] де Брейн, НГ (1946). «Комбинаторная задача». Математические исследования . 49 : 758–764. МР 0018142 .

[Good1946-2] Хорошо, Эй Джей (1946). «Обычные повторяющиеся десятичные дроби». Журнал Лондонского математического общества . 21 (3): 167–169. дои : 10.1112/jlms/s1-21.3.167 .

[Flye1894-3] Флай Сент-Мари, К. (1894). «Вопрос 48». Посредник математиков . 1 :107–110.

[Zhang1987-4] Чжан, Фу Цзи; Линь, Го Нин (1987). «О графиках де Брейна – Гуда». Акта Математика Синика . 30 (2): 195–205.

[Leroux2002-5] Леру, Филипп (2005). «Коассоциативная грамматика, периодические орбиты и квантовое случайное блуждание по $\mathbb {Z}$ " . Международный журнал математики и математических наук . 2005 (24): 3979–3996. arXiv : quant-ph/0209100 . doi : 10.1155/IJMMS.2005.3979 . MR 2204471 .

[HeathRosenberg-6] Хит, Ленвуд С.; Розенберг, Арнольд Л. (1992). «Построение графиков с помощью очередей». SIAM Journal по вычислительной технике . 21 (5): 927–958. дои : 10.1137/0221055 . МР 1181408 .

[Obrenic-7] Обренич, Бояна (1993). «Вложение графов де Брёйна и тасования-обмена на пяти страницах». SIAM Journal по дискретной математике . 6 (4): 642–654. дои : 10.1137/0406049 . МР 1241401 .

[Pevzner2001a-8] Певзнер Павел Александрович ; Тан, Хайсюй; Уотерман, Майкл С. (2001). «Подход Эйлера к сборке фрагментов ДНК» . Труды Национальной академии наук . 98 (17): 9748–9753. Бибкод : 2001PNAS...98.9748P . дои : 10.1073/pnas.171285098 . ПМЦ 55524 . ПМИД 11504945 .

[Pevzner2001b-9] Певзнер Павел Александрович ; Тан, Хайсюй (2001). «Сборка фрагментов с двуствольными данными» . Биоинформатика . 17 (Приложение 1): С225–С233. doi : 10.1093/биоинформатика/17.suppl_1.S225 . ПМИД 11473013 .

[zerbino2008-10] Зербино, Дэниел Р.; Бирни, Юэн (2008). «Бархат: алгоритмы сборки короткого чтения de novo с использованием графов де Брёйна» . Геномные исследования . 18 (5): 821–829. дои : 10.1101/гр.074492.107 . ПМК 2336801 . ПМИД 18349386 .

[chikhi2014representation-11] Чихи, Р.; Лимассет, А.; Джекман, С.; Симпсон, Дж.; Медведев, П. (2014). «О представлении графов де Брейна». Журнал вычислительной биологии . 22 (5): 336–52. arXiv : 1401.5383 . дои : 10.1089/cmb.2014.0160 . ПМИД 25629448 . S2CID 9502231 .

[ukmss-37901-12] Икбал, Замин; Каккамо, Марио; Тернер, Исаак; Фличек, Пол; Маквин, Гил (2012). «Сборка de novo и генотипирование вариантов с использованием цветных графов де Брёйна» . Природная генетика . 44 (2): 226–32. дои : 10.1038/ng.1028 . ПМЦ 3272472 . ПМИД 22231483 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]