Ensamble de ADN usando diagramas de De Bruijn

Ponente(s): Alexis García Durán, José Manuel Gómez Soto
Sea k>=2 entero y A un alfabeto finito. El diagrama de De Bruijn de dimensión k es el grafo B_{k,A}=(A^k,E), tal que E={(v,w):v,w en A^k y v[2…k]=w[1…(k-1)]}. En otras palabras un diagrama de De Bruijn de dimensión k es un grafo cuyos nodos son todas las palabras de longitud k que se pueden formar sobre un alfabeto dado y cuyas aristas unen palabras que se superponen en k-1 símbolos, de modo que el sufijo de una coincide con el prefijo de la otra. Ahora bien, uno de los mayores problemas que enfrentan los biólogos y/o genetistas al tratar de secuenciar el genoma de una especie es la cantidad de nucleótidos que pueden obtener en una sola prueba; dado que la secuencia completa del genoma está compuesta por millones de nucleótidos es imposible para la tecnología actual obtenerla completa en una sola toma, es por eso que la metodología empleada es obtener fragmentos de una longitud fija (dependiendo de la maquina secuenciadora utilizada) para después unirlos y obtener la secuencia completa. En 2011 Pevzner y otros publicaron en Nature como aplicar diagramas de De Bruijn para ensamblar el genoma. Nos pareció interesante saber exactamente como Pevzner et al realizaron eso, de manera que hemos estado investigando como ensamblar código genético utilizando diagramas de De Bruijn e implementando nuestros propios programas computacionales. Esta plática muestra nuestros avances en dicha investigación.