Grafo de De Bruijn

Un grafo de De Bruijn es un grafo dirigido que permite representar los solapamientos de longitud ${\displaystyle n-1}$ entre todas las palabras (cadenas de caracteres) de longitud ${\displaystyle n}$ con un alfabeto dado. El nombre de los grafos deriva del matemático Nicolaas Govert de Bruijn quien los describió en 1946.^[1]​ Sin embargo, dichos grafos ya habían sido descritos por Camille Flye Santa-Casa en 1894^[2]​ y por Irving J. Good en 1946.^[3]​^[4]​

El grafo de De Bruijn ${\displaystyle B(k,n)}$ de orden ${\displaystyle n}$ con un alfabeto ${\displaystyle A}$ de ${\displaystyle k}$ letras está construido como se explica a continuación. Los nodos (o vértices) de ${\displaystyle B(k,n)}$ están en biyección con (están etiquetados por) las ${\displaystyle k^{n}}$ palabras de longitud ${\displaystyle n}$ sobre ${\displaystyle A}$. Si ${\displaystyle u}$ y ${\displaystyle v}$ son dos nodos, hay un arco de ${\displaystyle u}$ a ${\displaystyle v}$ cuando la palabra obtenida al suprimir la primera letra de ${\displaystyle u}$ es la misma que la palabra obtenida al suprimir la última letra de ${\displaystyle v}$; dicho de otra manera, cuando existen dos letras ${\displaystyle a}$ y ${\displaystyle b}$, y una palabra o cadena ${\displaystyle x}$, tales que ${\displaystyle u=ax}$ y ${\displaystyle v=xb}$. La presencia de un arco significa entonces que existe una superposición entre dos palabras de la misma longitud. Es común etiquetar ese arco con la cadena ${\displaystyle axb}$.

El grafo ${\displaystyle B(2,3)}$ de la figura a la derecha está construido mediante un alfabeto binario ${\displaystyle A=\{0,1\}}$ con cadenas de longitud ${\displaystyle n=3}$. Las ${\displaystyle 2^{3}=8}$ cadenas de longitud 3 con el alfabeto binario son:

${\displaystyle 000,\ 001,\ 010,\ 011,\ 111,\ 110,\ 101,\ 100}$

Hay, por ejemplo, un arco que sale del nodo ${\displaystyle 000}$ que va al nodo ${\displaystyle 001}$ porque el sufijo de longitud 2 de ${\displaystyle 000}$ es igual al prefijo de longitud 2 de ${\displaystyle 001}$. Ese arco queda marcado con la cadena ${\displaystyle 0001}$. Asimismo, hay un arco que va del nodo ${\displaystyle 100}$ al nodo ${\displaystyle 000}$ porque el sufijo de longitud 2 de ${\displaystyle 100}$ es igual al prefijo de longitud 2 de ${\displaystyle 000}$. Ese arco queda marcado con la cadena ${\displaystyle 1000}$.

El grafo ${\displaystyle B(n,1)}$ está formado por ${\displaystyle n}$ nodos, uno por cada letra. De cada nodo parten ${\displaystyle n}$ arcos, hay entonces ${\displaystyle n^{2}}$ arcos.

• Cada nodo en un grafo ${\displaystyle B(k,n)}$ tiene grado de salida ${\displaystyle k}$ y grado de entrada ${\displaystyle k}$.

• El grafo ${\displaystyle B(k,n)}$ de orden ${\displaystyle n}$ es el grafo línea del grafo ${\displaystyle B(k,n-1)}$ de orden ${\displaystyle n-1}$:

• Un grafo de De Bruijn es euleriano y hamiltoniano.

• Toda secuencia de De Bruijn corresponde a un ciclo euleriano de un grafo de De Bruijn.

• Los circuitos eulerianos de ${\displaystyle B(k,n-1)}$ y hamiltonianos de ${\displaystyle B(k,n)}$ se corresponden por la construcción del grafo línea. Estos circuitos son sucesiones de De Bruijn.

Se puede hacer un grafo de De Bruijn binario de modo que parezca un objeto de teoría de sistemas dinámicos, como el atractor de Lorenz.

Esta analogía se explica porque el grafo de De Bruijn ${\displaystyle B(k,n)}$ es un modelo de aplicación de Bernoulli.

${\displaystyle x\mapsto kx\ {\bmod {\ }}1}$

La aplicación de Bernoulli (también llamada la función 2x mod 1 o función diádica para ${\displaystyle k=2}$) es un sistema dinámico ergódico que puede ser visto como un operador de desplazamiento sobre un número k-ádico. Las trayectorias de este sistema dinámico corresponden a los caminos en el grafo de De Bruijn, con la correspondencia que asocia a cada real ${\displaystyle x}$ del intervalo semi-abierto ${\displaystyle [0,1)}$ la suma del grafo que corresponde a las ${\displaystyle n}$ primeras cifras en la representación de ${\displaystyle x}$ en base ${\displaystyle k}$. De manera equivalente, los caminos en el grafo de De Bruijn corresponden a las trayectorias de un sistema dinámico de tipo acabado.

• Muchas veces las topologías de red son grafos de De Bruijn.
• El protocolo Koorde de tabla de hash distribuida usa un grafo de De Bruijn.
• Los grafos de De Bruijn han sido utilizados en bioinformática para el ensamblaje de genoma y transcriptoma a partir de fragmentos de lectura (reads) provenientes de un secuenciamiento.^[5]​^[6]​

1. ↑ Nicolaas Govert de Bruijn, «A Combinatorial Problem», Koninklijke Nederlandse Akademie v. Wetenschappen, vol. 49, 1946, p. 758–764
2. ↑ Sainte-Marie, Camille Flye (1894). «Question 48». L'Intermédiaire des Mathématiciens. p. vol. 1, p. 107–110. Camille Flye Sainte-Marie, «Question 48», L'Intermédiaire des Mathématiciens, vol. 1, 1894, p. 107–110
3. ↑ Good, I. J. (1946). «Normal Recurring Decimals». Journal of the London Mathematical Society (en inglés). s1-21 (3): 167-169. ISSN 1469-7750. doi:10.1112/jlms/s1-21.3.167. Consultado el 14 de junio de 2021. 
4. ↑ «The origins of combinatorics on words». European Journal of Combinatorics (en inglés) 28 (3): 996-1022. 1 de abril de 2007. ISSN 0195-6698. doi:10.1016/j.ejc.2005.07.019. Consultado el 14 de junio de 2021. 
5. ↑ Compeau, Phillip E. C.; Pevzner, Pavel A.; Tesler, Glenn (2011-11). «How to apply de Bruijn graphs to genome assembly». Nature Biotechnology (en inglés) 29 (11): 987-991. ISSN 1546-1696. PMID 22068540. doi:10.1038/nbt.2023. Consultado el 14 de junio de 2021. 
6. ↑ Martin, Jeffrey A.; Wang, Zhong (2011-10). «Next-generation transcriptome assembly». Nature Reviews Genetics (en inglés) 12 (10): 671-682. ISSN 1471-0064. doi:10.1038/nrg3068. Consultado el 14 de junio de 2021.