La respuesta depende completamente de qué tipo de algoritmo de ensamblaje se está enfocando. Presumiblemente, su pregunta está más centrada en el ensamblaje de novo , por lo que cubriré esos algoritmos. Además, cuando se habla de “complejidad computacional”, me refiero principalmente a la complejidad del tiempo.
Para algoritmos de solapamiento-diseño-consenso (OLC) como los que se encuentran en Celera Assembler / CABOG / WGS Assembler (wgs-assembler) y MaSuRCA (UMD Genome group), el paso más complejo computacionalmente tiende a ser la determinación de las superposiciones entre lecturas. Ingenuamente, este paso requiere O ([matemática] n ^ {2} [/ matemática]) alineaciones por pares, donde [matemática] n [/ matemática] es el número de lecturas, y cada alineación por parejas es O ([matemática] nm [ / math]) donde [math] n [/ math] y [math] m [/ math] son las longitudes de las lecturas, si se implementa un algoritmo exacto. En realidad, se emplean ciertas optimizaciones (por ejemplo, programación dinámica, indexación, etc.) para reducir la complejidad del tiempo, pero esto sigue siendo un cuello de botella.
Entonces, imagínese el tiempo requerido para realizar este paso para un conjunto de lectura Illumina moderno de ~ 400M lecturas de 215 nt. Ahora considere agregar en otras bibliotecas de lectura (por ejemplo, algunas lecturas de 454 fragmentos o pares de parejas). Realmente necesita un clúster para manejar esta cantidad de datos.
- ¿Cuáles son los nucleótidos encontrados en el ADN y el ARN? ¿Cuáles son las reglas del emparejamiento de bases para esos nucleótidos?
- ¿Qué es la PCR en tiempo real (biología)? ¿Cómo funciona técnicamente?
- ¿Qué es la regulación genética?
- ¿Cómo es el procedimiento para solicitar un doctorado en el campo de la biología molecular en los Estados Unidos? ¿Cómo se ve el programa de doctorado?
- ¿Dónde se puede encontrar el ARN de transferencia?
El profesor Ben Langmead de UMD y JHU tiene excelentes diapositivas en los algoritmos OLC y DBG:
http://www.cs.jhu.edu/~langmea/r…
Para algoritmos de Bruijn Graph (DBG) como los que se encuentran en Velvet (un ensamblador de secuencias para lecturas muy cortas), SOAPdenovo (Short Oligonucleotide Analysis Package), Minia (implementación de la representación gráfica de Bruijn “eficiente en el espacio y exacta basada en un Bloom filtro “), Ray (Ray – Ensambles de genoma paralelo para secuenciación paralela de ADN) y muchos otros, el paso más complejo desde el punto de vista computacional es probablemente la construcción del Gráfico de Bruijn (que también es el paso que más espacio consume). La complejidad espacial de este paso es el factor más restrictivo, ya que los algoritmos DBG tienden a ser mucho más rápidos que los algoritmos OLC con suficiente memoria. Algoritmos como Minia y SparseAssembler (SparseAssembler) abordan el problema de la complejidad espacial de los algoritmos DBG, sacrificando un poco de precisión y tiempo de ejecución por menores requisitos de memoria.
Aquí, tiene algunas diapositivas más del Prof. Langmead: http://www.cs.jhu.edu/~langmea/r…
Para algoritmos alternativos como los que se encuentran en String Graph Assembler (jts / sga) y fermi (lh3 / fermi), el paso más complejo computacionalmente tiende a ser el paso de construcción del gráfico, como con los algoritmos DBG, también debido a depender de una estructura gráfica ( específicamente, un gráfico de cadena). Incluso los codiciosos algoritmos de ensamblaje como SSAKE (http://www.bcgsc.ca/platform/bio…), VCAKE (VCAKE) y otros son más lentos durante la construcción del gráfico.
Por lo que dice en los detalles de la pregunta, supongo que se beneficiaría de leer muchas de las diapositivas del Prof. Langmead, así que aquí está la página de índice para ellas:
http://www.langmead-lab.org/teac…
Una cosa a tener en cuenta:
El principal problema con los programas modernos de ensamblaje de novo no es la complejidad computacional, sino la recapitulación de la verdad biológica. Es decir, las regiones repetitivas, regiones de heterocigosidad, variantes estructurales, etc., no están perfectamente preservadas por la mayoría de estos algoritmos.
Los biólogos pueden aprender a usar clústeres informáticos o servidores más grandes, especialmente porque la industria informática está haciendo que la memoria y los núcleos sean más baratos cada año, por lo que la complejidad computacional es ahora un problema mucho menor que hace una década. Lo que tenemos más problemas para hacer es modificar los algoritmos existentes para recrear la verdad biológica. El problema del ensamblaje del genoma no es tan simple como resolver el problema de secuencia / supercuerda común más corto, ni es tan simple como encontrar caminatas de Eulerian en un DBG. Entonces, el problema actual en bioinformática es encontrar un algoritmo que conserve esta información adicional.
