График Де Брейна

В теории графов n $-$ мерный граф Де Брейна из $m$ символов — это ориентированный граф , представляющий перекрытия между последовательностями символов. Он имеет $m n$ вершин , состоящий из всех возможных последовательностей длины $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_{м}),(s_{1},\dots ,s_{2},s_{1}),\dots ,(s_{м},\dots ,s_{м},s_{м})\}.

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

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$ , то условие для любых двух вершин, образующих ребро, выполняется бессодержательно , $и$ , следовательно, все вершины соединены, образуя в общей сложности $m2$ ребер.
Каждая вершина имеет ровно $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$ цифрам в представлении $x в системе счисления$ с основанием - $m$ . Эквивалентно, блуждания в графе Де Брейна соответствуют траекториям в одностороннем подсдвиге конечного типа .

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

Использует

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

Смотрите также

Ссылки

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

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

Вайсштейн, Эрик В. «График Де Брёйна». Математический мир .
Учебное пособие по использованию графов Де Брейна в биоинформатике от Homolog.us