Sesión Lógica y Computabilidad (II)

Diciembre 13, 11:20 ~ 11:40

Extensi'on eficiente de secuencias De Bruijn

Taravilse, Leopoldo

Fijemos un alafabeto $A$ finito y sea $|A|$ su cardinalidad. Una secuencia De Bruijn de orden $n$ es una secuencia de $|A|^n$ caracteres, en la que todas las secuencias de longitud $n$ en dicho alfabeto aparecen como subsecuencia, si consideramos la secuencia de manera circular (es decir, si comenzamos en alguno de los últimos $n-1$ caracteres, completamos los $n$ caracteres con un prefijo de la secuencia). Las secuencias de Bruijn han sido muy estudiadas y aparecen en la literatura también comos {\em linear shift register}. En este trabajo nos dedicamos al problema de extender secuencias de Bruijn de un orden dado al orden siguiente. Los aspectos algoritmicos de este problema no han sido considerados anteriormente en la literatura. Específicamente nuestro objetivo es encontrar algoritmos eficientes para computar una extensión de una de Bruin dada. Las secuencias de Bruijn de orden $n$ pueden caracterizarse como las etiquetas de los circuitos eulerianos en el llamados grafos de Bruijn $G_{n-1}$ de palabras de longitud $n-1$. Una de las propiedades fundametales de estos objetos combinatorios es que el grafo $G_n$ de palabras de longitud $n$ es el grafo de línea de del $G_{n-1}$. Por lo que los cada circuito euleriano en $G_{n-1}$ es un circuito hamiltoniano en $G_n$. En 1982 Fredricksen dio un algoritmo para generar secuencias en alfabetos binarios, basado en los {\em spanning trees} de un grafo De Bruijn. Recientemente dimos una generalización del algoritmo de Fredricksen que permite generar cada una de las extensiones de una secuencia de Bruin de orden $n$ en un alfabeto de tres símbolos. Para abordar el problema de dar un algoritmo eficiente es necesario comprender la estructura de los grafos de Bruijn que resultan después de quitarles un circuito hamiltoniano. Apuntamos a caracterizar el conjunto de {\em spanning trees} de estos grafos. En este trabajo estudiamos problemas ya resueltos para la generación de secuencias De Bruijn y nos planteamos los problemas análogos para la extensión.

Autores: Taravilse, Leopoldo.