Secuencia de bruijn

Una sucesión de de Bruijn [1]  es un orden cíclico cuyos elementos pertenecen a un conjunto finito dado (generalmente se considera el conjunto ), tal que todas sus subsucesiones [2] de una longitud dada son distintas.

A menudo se consideran secuencias periódicas con período , que contienen diferentes subsecuencias , es decir, tales secuencias periódicas en las que cualquier segmento de longitud es una secuencia de De Bruijn con los mismos parámetros y .

Los ciclos llevan el nombre del matemático holandés Nicholas de Bruijn , quien los estudió en 1946 [3] , aunque se han estudiado antes [4] .

Propiedades

Obviamente, la duración (período) de dicho ciclo no puede exceder  - el número de todos los vectores de longitud diferentes con elementos de ; Es fácil probar que esta estimación es alcanzable. Los ciclos de esta duración máxima posible suelen denominarse ciclos de Bruijn (sin embargo, a veces este término también se aplica a ciclos de duración más corta).

Para , existen tales ciclos de De Bruijn con una longitud uno menos que el máximo, que se expresan mediante relaciones de recurrencia lineal del orden Sobre la base de tales secuencias, en particular, se construye el código redundante cíclico CRC32 (EDB88320).

Ejemplos

Ejemplos de ciclos de Bruijn para los períodos 2, 4, 8, 16:

Número de ciclos de de Bruijn

El número de ciclos de de Bruijn con parámetros también lo es ( un caso especial del teorema de de Bruijn es el teorema BEST , llamado así por los nombres de de Bruijn, Tatiana Ehrenfest , Cedric Smith  y William Tutt ).

Comte de Bruyne

Hay una interpretación conveniente de las secuencias y ciclos de De Bruijn basada en el llamado gráfico de Bruijn  : un gráfico dirigido con vértices correspondientes a diferentes conjuntos de longitudes con elementos de , en el que un borde conduce de vértice a vértice si y solo si ( ); en este caso, la propia arista se puede asociar a un conjunto de longitudes : . Para tal gráfico, los caminos de Euler ( ciclos eulerianos ) que no pasan dos veces por el mismo borde corresponden a una secuencia (ciclo) de Bruijn con parámetros y , y los caminos hamiltonianos ( ciclos hamiltonianos ) que no pasan dos veces por el mismo vértice corresponden a una secuencia (ciclo) de Bruijn con parámetros y .

El gráfico de Bruijn es ampliamente utilizado en bioinformática en tareas de ensamblaje de genomas .

Notas

  1. ↑ También se escriben "de Bruyn" y "de Bruyn".
  2. ↑ Si , entonces el elemento con índice se selecciona en orden cíclico
  3. ↑ de Bruijn NG Un problema combinatorio // Koninklijke Nederlandse Akademie v. Wetenschappen. 1946. - v. 49.-pp. 758-764.
  4. ↑ Flye Sainte-Marie C. Pregunta 48 // L'intermédiaire math. - 1894. - v. 1.-pp. 107-110.