En teoría de grafos , un-Gráfico de De Bruijn dimensional desímbolos es un gráfico dirigido que representa superposiciones entre secuencias de símbolos. Tiene vértices , que constan de todas las longitudes posiblessecuencias de los símbolos dados; el mismo símbolo puede aparecer varias veces en una secuencia. Para un conjunto de simbolos , 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 agregando un nuevo símbolo al final de este vértice, entonces este último tiene un borde dirigido al vértice anterior. Por 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 descubiertos de forma independiente tanto por De Bruijn [1] como por IJ Good . [2] Mucho antes, Camille Flye Sainte-Marie [3] usó implícitamente sus propiedades.
Propiedades
- Si entonces la condición para dos vértices cualesquiera que formen un borde se mantiene vacía, y por lo tanto todos los vértices están conectados formando un total bordes.
- Cada vértice tiene exactamente entrante y bordes salientes.
- Cada -El gráfico de De Bruijn dimensional es el dígrafo lineal del-Gráfico de De Bruijn dimensional con el mismo conjunto de símbolos. [4]
- Cada gráfico de De Bruijn es euleriano y hamiltoniano . Los ciclos de Euler y los ciclos hamiltonianos de estos gráficos (equivalentes entre sí a través de la construcción del gráfico de líneas) son secuencias de De Bruijn .
La construcción del gráfico de líneas de los tres gráficos binarios de De Bruijn más pequeños se muestra a continuación. Como puede verse en la ilustración, cada vértice del-El gráfico de De Bruijn dimensional corresponde a un borde del gráfico de De Bruijn dimensional, y cada borde en el -dimensional de De Bruijn corresponde a una trayectoria de dos aristas en el -Gráfico de De Bruijn dimensional.
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: la -dimensional -symbol De Bruijn graph es un modelo del mapa de Bernoulli
El mapa de Bernoulli (también llamado mapa 2x mod 1 para) es un sistema dinámico ergódico , que puede entenderse como un solo desplazamiento de un número m -ádico . [5] Las trayectorias de este sistema dinámico corresponden a caminatas en el gráfico de De Bruijn, donde la correspondencia se da mapeando cada real en el intervalo al vértice correspondiente al primero dígitos en la base - representacion de . De manera equivalente, los paseos en el gráfico de De Bruijn corresponden a trayectorias en un subdesplazamiento unilateral de tipo finito .
Se pueden usar incrustaciones similares a esta para mostrar que los gráficos binarios de De Bruijn tienen el número de cola 2 [6] y que tienen un grosor de libro como máximo 5. [7]
Usos
- Algunas topologías de redes de rejilla 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]
Ver también
Referencias
- ↑ de Bruijn, NG (1946). "Un problema combinatorio". Indagationes Mathematicae . 49 : 758–764. Señor 0018142 .
- ^ Bueno, IJ (1946). "Decimales recurrentes normales". Revista de la Sociedad Matemática de Londres . 21 (3): 167-169. doi : 10.1112 / jlms / s1-21.3.167 .
- ^ Flye Sainte-Marie, C. (1894). "Pregunta 48". L'Intermédiaire des Mathématiciens . 1 : 107-110.
- ^ Zhang, Fu Ji; Lin, Guo Ning (1987). "Sobre los gráficos de Bruijn – Good". Acta Mathematica Sinica . 30 (2): 195–205.
- ^ Leroux, Philippe (2005). "Gramática coasociativa, órbitas periódicas y recorrido aleatorio cuántico." Revista Internacional de Matemáticas y Ciencias matemáticas (24):. 3.979-3996 arXiv : quant-ph / 0209100 . Doi : 10.1155 / IJMMS.2005.3979 . MR 2.204.471 .
- ^ Heath, Lenwood S .; Rosenberg, Arnold L. (1992). "Trazado de gráficos mediante colas". Revista SIAM de Computación . 21 (5): 927–958. doi : 10.1137 / 0221055 . Señor 1181408 .
- ^ Obrenić, Bojana (1993). "Incrustación de gráficos de Bruijn e intercambio aleatorio en cinco páginas". Revista SIAM de Matemática Discreta . 6 (4): 642–654. doi : 10.1137 / 0406049 . Señor 1241401 .
- ^ 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. Código Bibliográfico : 2001PNAS ... 98.9748P . doi : 10.1073 / pnas.171285098 . PMC 55524 . PMID 11504945 .
- ^ 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 .
- ^ Zerbino, Daniel R .; Birney, Ewan (2008). "Velvet: algoritmos para ensamblaje de lectura corta de novo usando gráficos de Bruijn" . Investigación del genoma . 18 (5): 821–829. doi : 10.1101 / gr.074492.107 . PMC 2336801 . PMID 18349386 .
- ^ Chikhi, R .; Limasset, A .; Jackman, S .; Simpson, J .; Medvedev, P. (2014). "Sobre la representación de los gráficos de Bruijn". Revista de Biología Computacional . 22 (5): 336–52. arXiv : 1401.5383 . doi : 10.1089 / cmb.2014.0160 . PMID 25629448 .
- ^ Iqbal, Zamin; Caccamo, Mario; Turner, Isaac; Flicek, Paul; McVean, Gil (2012). "Montaje de novo y genotipado de variantes utilizando gráficos coloreados de Bruijn" . Genética de la naturaleza . 44 (2): 226–32. doi : 10.1038 / ng.1028 . PMC 3272472 . PMID 22231483 .
enlaces externos
- Weisstein, Eric W. "De Bruijn Graph" . MathWorld .
- Tutorial sobre el uso de gráficos de De Bruijn en bioinformática por Homolog.us