Gráfico de De Bruijn

Gráfico dirigido que representa superposiciones entre secuencias de símbolos.

En teoría de grafos , un grafo de De Bruijn n -dimensional de m símbolos es un grafo dirigido que representa superposiciones entre secuencias de símbolos. Tiene m ⁿ vértices , que consisten en todas las secuencias de longitud n posibles de los símbolos dados; el mismo símbolo puede aparecer varias veces en una secuencia. Para un conjunto de m símbolos S = { s ₁ , …, s _m }, el conjunto de vértices es:

${\displaystyle 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})\}.}$

Si uno de los vértices puede expresarse como otro vértice desplazando todos sus símbolos un lugar hacia la izquierda y añadiendo un nuevo símbolo al final de este vértice, entonces este último tiene una arista dirigida hacia el vértice anterior. Por lo tanto, el conjunto de arcos (es decir, aristas dirigidas) es

${\displaystyle 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\}.}$

Aunque los gráficos de De Bruijn llevan el nombre de Nicolaas Govert de Bruijn , fueron inventados de forma independiente tanto por De Bruijn ^[1] como por IJ Good . ^[2] Mucho antes, Camille Flye Sainte-Marie ^[3] utilizó implícitamente sus propiedades.

Propiedades

• Si n = 1 , entonces la condición para que dos vértices formen una arista se cumple vacíamente y, por lo tanto, todos los vértices están conectados, formando un total de m ² aristas.
• Cada vértice tiene exactamente m aristas entrantes y m aristas salientes.
• Cada gráfico de De Bruijn n -dimensional es el dígrafo lineal del gráfico de De Bruijn ( n – 1) -dimensional con el mismo conjunto de símbolos. ^[4]
• Cada grafo de De Bruijn es euleriano y hamiltoniano . Los ciclos de Euler y los ciclos hamiltonianos de estos grafos (equivalentes entre sí mediante la construcción del grafo lineal) son secuencias de De Bruijn .

A continuación se muestra la construcción del gráfico lineal de los tres grafos binarios de De Bruijn más pequeños. Como se puede ver en la ilustración, cada vértice del grafo de De Bruijn de n dimensiones corresponde a una arista del grafo de De Bruijn de ( n – 1) dimensiones , y cada arista del grafo de De Bruijn de n dimensiones corresponde a una trayectoria de dos aristas en el grafo de De Bruijn de ( n – 1) dimensiones .

Sistemas dinámicos

Los gráficos binarios de De Bruijn se pueden dibujar de tal manera que se asemejen a objetos de la teoría de sistemas dinámicos , como el atractor de Lorenz :

Esta analogía puede hacerse rigurosa: el gráfico de De Bruijn de dimensión n y símbolo m es un modelo del mapa de Bernoulli.

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

El mapa de Bernoulli (también llamado mapa 2 x mod 1 para m = 2 ) es un sistema dinámico ergódico , que puede entenderse como un único desplazamiento de un número m -ádico . ^[5] Las trayectorias de este sistema dinámico corresponden a los paseos en el grafo de De Bruijn, donde la correspondencia se da al mapear cada x real en el intervalo [0,1) al vértice correspondiente a los primeros n dígitos en la representación base - m de x . Equivalentemente, los paseos en el grafo de De Bruijn corresponden a trayectorias en un subdesplazamiento unilateral de tipo finito .

Grafos dirigidos de dos secuencias de Bruijn B (2,3) y una secuencia B (2,4) . En B (2,3) , cada vértice se visita una vez, mientras que en B (2,4) , cada arista se recorre una vez.

Se pueden utilizar incrustaciones similares a ésta para demostrar que los gráficos binarios de De Bruijn tienen un número de cola de 2 ^[6] y que tienen un grosor de libro de como máximo 5. ^[7]

Usos

• Algunas topologías de redes grid son gráficos de De Bruijn.
• El protocolo de tabla hash distribuida Koorde utiliza un gráfico de De Bruijn.
• En bioinformática , los gráficos de De Bruijn se utilizan para el ensamblaje de novo de lecturas de secuenciación en un genoma . ^{[8] [9] [10] [11] [12]}

Véase también

• El toro de Bruijn
• Gráfico de Hamming
• Gráfico de Kautz

Referencias

1. de Bruijn, NG (1946). "Un problema combinatorio". Indagaciones Mathematicae . 49 : 758–764. SEÑOR  0018142.
2. Good, IJ (1946). "Decimales periódicos normales". Revista de la Sociedad Matemática de Londres . 21 (3): 167–169. doi :10.1112/jlms/s1-21.3.167.
3. Flye Sainte-Marie, C. (1894). "Pregunta 48". L'Intermédiaire des Mathématiciens . 1 : 107–110.
4. Zhang, Fu Ji; Lin, Guo Ning (1987). "Sobre los buenos gráficos de De Bruijn". Acta Mathematica Sínica . 30 (2): 195–205.
5. Leroux, Philippe (2005). "Gramática coasociativa, órbitas periódicas y recorrido aleatorio cuántico sobre Z {\displaystyle \mathbb {Z} }". Revista Internacional de Matemáticas y Ciencias Matemáticas . 2005 (24): 3979–3996. arXiv : quant-ph/0209100 . doi : 10.1155/IJMMS.2005.3979 . MR  2204471.
6. Heath, Lenwood S.; Rosenberg, Arnold L. (1992). "Diseño de gráficos mediante colas". Revista SIAM de Computación . 21 (5): 927–958. doi :10.1137/0221055. MR  1181408.
7. Obrenić, Bojana (1993). "Incrustación de gráficos de Bruijn y de intercambio aleatorio en cinco páginas". Revista SIAM de Matemáticas Discretas . 6 (4): 642–654. doi :10.1137/0406049. MR  1241401.
8. Pevzner, Pavel A. ; Tang, Haixu; Waterman, Michael S. (2001). "Un enfoque de ruta euleriana para el ensamblaje de fragmentos de ADN". Actas de la Academia Nacional de Ciencias . 98 (17): 9748–9753. Bibcode :2001PNAS...98.9748P. doi : 10.1073/pnas.171285098 . PMC 55524 . PMID  11504945. 
9. Pevzner, Pavel A. ; Tang, Haixu (2001). "Ensamblaje de fragmentos con datos de doble cañón". Bioinformática . 17 (Supl 1): S225–S233. doi : 10.1093/bioinformatics/17.suppl_1.S225 . PMID  11473013.
10. Zerbino, Daniel R.; Birney, Ewan (2008). "Velvet: algoritmos para el ensamblaje de lecturas cortas de novo utilizando grafos de Bruijn". Genome Research . 18 (5): 821–829. doi :10.1101/gr.074492.107. PMC 2336801 . PMID  18349386. 
11. Chikhi, R.; Limasset, A.; Jackman, S.; Simpson, J.; Medvedev, P. (2014). "Sobre la representación de los grafos de De Bruijn". Revista de Biología Computacional . 22 (5): 336–52. arXiv : 1401.5383 . doi :10.1089/cmb.2014.0160. PMID  25629448. S2CID  9502231.
12. Iqbal, Zamin; Caccamo, Mario; Turner, Isaac; Flicek, Paul; McVean, Gil (2012). "Ensamblaje de novo y genotipado de variantes utilizando gráficos de Bruijn coloreados". Nature Genetics . 44 (2): 226–32. doi :10.1038/ng.1028. PMC 3272472 . PMID  22231483. 

Enlaces externos

• Weisstein, Eric W. "Gráfico de De Bruijn". MundoMatemático .
• Tutorial sobre el uso de los gráficos de De Bruijn en bioinformática por Homolog.us