stringtranslate.com

Gráfico de De Bruijn

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 n vértices , que consisten en todas las posibles secuencias de longitud n 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 1 , …, s m }, el conjunto de vértices es:

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

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

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 .

Imagen que muestra múltiples gráficos de De Bruijn, cada uno de ellos el gráfico lineal del anterior.

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.

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

Véase también

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, Zamín; Caccamo, Mario; Turner, Isaac; Flicek, Paul; McVean, Gil (2012). "Ensamblaje de novo y genotipado de variantes utilizando gráficos de Bruijn coloreados". Genética de la Naturaleza . 44 (2): 226–32. doi :10.1038/ng.1028. PMC 3272472 . PMID  22231483. 

Enlaces externos