un artículo educativo publicado recientemente en Nature Biotechnology me ha vuelto a recordar los grafos de De Bruijn, que ya había mencionado de pasada en una entrada anterior sobre vectores de sufijos. Hoy los veremos un poco más de cerca, por su importancia para la reconstrucción de secuencias genómicas a partir de fragmentos más pequeños que han sido previamente secuenciados.
Los modernos ensambladores de secuencias emplean grafos de De Bruijn para guardar en memoria los prefijos (nodos) y sufijos (aristas) de las lecturas o reads obtenidas en experimentos de secuenciación. Este tipo de representación permite reducir en parte la redundancia natural de este tipo de datos a la vez que facilita su ensamblaje posterior. La figura compara los métodos de ensamblaje tradicionales (a) con los actuales (d). Los tradicionales se usan para pegar entre si secuencias obtenidas por el método de Sanger, que suelen ser largas, de buena calidad y en números pequeños. Los métodos que acompañan a los secuenciadores actuales se adaptan al nuevo escenario de secuencias cortas y en números varios órdenes de magnitud más elevados.
 |
| fuente: http://www.nature.com/nbt/journal/v29/n11/full/nbt.2023.html |
Como se muestra en el panel d de la figura, un grafo de De Bruijn facilita la reconstrucción del genoma de partida, que se obtiene buscando un ciclo euleriano que recorra todas las aristas (sufijos) una sola vez. Esta estrategia es computacionalmente mucho más barata que la alternativa de buscar ciclos hamiltonianos, que en la práctica es imposible al ser un problema de tipo NP completo. Sin embargo, como pasa a menudo, la realidad se resiste a ser capturada por una sola teoría, e incluso los grafos de De Bruijn son todavía incapaces de resolver el problema de las secuencias repetidas, que aparecen en un genoma o región genómica no una sinó muchas veces.
En el Russell's blog encontraréis código fuente en Python para aprender cómo se construyen estos grafos. Espero haberos despertado la curiosidad, un saludo,
Bruno
