grafos de De Bruijn

Hola,
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

Mapamundi NGS

¿Te has preguntado alguna vez dónde puedes secuenciar ácidos nucleicos?
¿Estás buscando un servicio que ofrezca 'runs' en el Polonator o en Illumina HiSeq?
¿Quieres saber cuántos secuenciadores de DNA hay en tu ciudad y qué modelos son?
¿Dónde está el secuenciador más septentrional del planeta? ¿Y el más meridional?
¿Hay secuenciadores en la Antártida o en Hawai?

Hola,
en esta nueva entrada recomendamos un pequeño pasatiempos, una aplicación web basada en Google Maps que nos permite visualizar la localización de los distintos centros de secuenciación y, más concretamente, de los aparatos de secuenciación (NGS, claro) a lo largo y ancho del planeta.

Next Generation Genomics: World Map of High-throughput Sequencers

 

Y no sólo permite visualizar, ya que pretende que sean los usuarios los que añadan los centros y/o secuenciadores, y corrijan las localizaciones. Así que ya sabes, si conoces un secuenciador que no aparece en el mapa añádelo. Además, cuenta con un sencillo filtro en la parte superior, con el cual visualizar solamente los modelos de interés o hacer una rápida comparativa; y con un desplegable para poder ir directamente a un país concreto.

La aplicación fue creada mediante Google Maps API, JQuery, MarkerClusterer, LabeledMarker, Django y SQLite, en la Universidad de Birmingham.

Un saludo, hasta una nueva entrada,
Carlos

Adiós a ClustalW

Hola,
en esta entrada quería enterrar al ya vetusto ClustalW, el programa de alineamiento múltiple más citado de la historia. En realidad lo acaban de enterrar sus propios autores en este artículo, donde presentan a su sucesor Clustal Omega. Como es habitual en Bioinformática, los autores ponen a prueba el nuevo programa de alineamiento comparándolo con las principales opciones de software disponibles, incluyendo al viejo ClustalW. Las comparaciones son bastante extensas, usando hasta 3 baterías de alineamientos, como son BALiBASE y HomFam (creadas por el entorno de Clustal) y Prefab, creada por el autor de MUSCLE, Robert Edgar. En la siguiente tabla, abreviada de la original, se muestran los resultados promediados sobre el conjunto BALiBASE de 218 familias de proteínas:

Aligner	Av score (218 families)							Tot time (s)
MSAprobs	0.607							12 382.00
Probalign	0.589							10 095.20
MAFFT (auto)	0.588							1475.40
Probcons	0.558							13 086.30
Clustal Ω	0.554							539.91
T-Coffee	0.551							81 041.50
Kalign	0.501							21.88
MUSCLE	0.475							789.57
MAFFT (default)	0.458							68.24
FSA	0.419							53 648.10
Dialign	0.415							3977.44
PRANK	0.376							128 355.00
ClustalW	0.374							766.47

En cuanto a poder decir si efectivamente Clustal Omega es el mejor alineador disponible en la actualidad habrá que esperar el veredicto de la comunidad y ver qué le parecen a Rober Edgar los parámetros de MUSCLE que se usaron en las pruebas, pero no parece superar en precisión a MAFFT en modo automático.
Sin embargo, las tablas del artículo (1 , 2 , 3) muestran que la inclusión de modelos ocultos de Markov (HMMs) y árboles guía mBed produce alineamientos de mucha mayor calidad (y en menor tiempo) que ClustalW, que es más lento para producir peores alineamientos. Clustal Omega puede alinear conjuntos de miles de secuencias, pero por el momento, sólo de aminoácidos, por lo que talvez sigamos usando ClustalW o MAFFT para alinear nucleótidos, no?

Por cierto, al compilar el código fuente de http://www.clustal.org/omega/clustal-omega-1.0.3.tar.gz en mi Ubuntu 10.04 tuve que instalar el paquete libargtable2-dev , un saludo,
Bruno

Perl Moderno?

Hoy me gustaría recomendar 'Modern Perl', que es un librito curioso porque:

1) contiene muchas recetas explicadas a base de ejemplos sobre los diferentes aspectos del lenguaje Perl, reflexionando sobre el famoso principio 'there is more than way to do it' y sobre las ventajas de unas maneras sobre otras de hacer la misma operación. Por ejemplo, se explica que el siguiente bucle:

 my @tripled;  
 my $count = @numbers;  
 for (my $i = 0; $i < $count; $i++)  
 {  
   $tripled[$i] = $numbers[$i] * 3;  
 }  

se puede expresar también como:

 my @tripled = map { $_ * 3 } @numbers;  

También por ejemplo muestra que igual que escribimos a un archivo podemos hacerlo a una variable escalar:

 my $captured_output;  
 open(OUTSTRING,'>',\$captured_output);  

2) es adecuado para principiantes del lenguaje y para gente más experta, ya que reflexiona sobre cuestiones de estilo y eficiencia, y además propone módulos clave de CPAN para facilitarnos la vida y hacer el código más robusto y portable

3) los autores del libro han dispuesto su libre descarga en diferentes formatos, por ejemplo en PDF

Que aproveche,
Bruno

Regulación por microRNAs exógenos de la dieta?

Hola,
uno de los temas principales que estudiamos en nuestro laboratorio es la regulación de la expresión génica, que como sabéis puede darse a varios niveles.
Si hace poco nuestro colega Lorenz Bülow nos contaba en un seminario de la EEAD  la integración de la regulación transcripcional y postranscripcional en la planta modelo Arabidopsis thaliana, organizada en la base de datos relacional AthaMap, hoy descubro un artículo reciente en Cell Research donde los autores publican evidencia de la presencia de cerca de 30 microRNAs de arroz en muestras de sangre de poblaciones humanas y de ganado en China. El artículo, que parte de muestreos masivos de secuencias y luego confirma los resultados por PCR, sugiere de manera convincente que algunos microRNAs expresados en el grano de arroz, dieta fundamental de las poblaciones estudiadas, pueden regular la expresión génica de sus comensales. Seguro que el artículo será puesto a prueba en posteriores análisis y estudios, para validarlo de manera inequívoca, porque estas observaciones desvelan dos hechos que sin duda tendrán mucho impacto:
1) puede haber transferencia de ácidos nucleicos de las plantas a los mamíferos que se las comen, a pesar de la digestión
2) puede haber fenómenos de regulación genética en la naturaleza a través de la dieta sin que medien hormonas, directamente por microRNAs, moléculas en torno a los 22 ribonucleótidos de tamaño, capaces de atravesar los epitelios del tracto digestivo

fuente: http://mcb.berkeley.edu/labs/he/Research.htm

Recomiendo la lectura de la fuente original y si tenéis algo que añadir por favor usad los comentarios, un saludo,
Bruno