Ensambladores de secuencias de novo

Software en bioinformática

Los ensambladores de secuencias de novo son un tipo de programa que ensambla secuencias de nucleótidos cortas en secuencias más largas sin el uso de un genoma de referencia . Estos se utilizan con mayor frecuencia en estudios bioinformáticos para ensamblar genomas o transcriptomas . Dos tipos comunes de ensambladores de novo son los ensambladores de algoritmos voraces y los ensambladores de gráficos de De Bruijn .

Tipos de ensambladores de novo

Existen dos tipos de algoritmos que estos ensambladores utilizan habitualmente: greedy , que apunta a óptimos locales , y algoritmos de método de grafos, que apuntan a óptimos globales . Los distintos ensambladores se adaptan a necesidades particulares, como el ensamblaje de genomas bacterianos (pequeños), genomas eucariotas (grandes) o transcriptomas.

Los ensambladores de algoritmos voraces son ensambladores que encuentran óptimos locales en alineaciones de lecturas más pequeñas . Los ensambladores de algoritmos voraces suelen presentar varios pasos: 1) cálculo de la distancia por pares de lecturas, 2) agrupamiento de lecturas con mayor superposición, 3) ensamblaje de lecturas superpuestas en contigs más grandes y 4) repetición. Estos algoritmos normalmente no funcionan bien para conjuntos de lecturas más grandes, ya que no alcanzan fácilmente un óptimo global en el ensamblaje y no funcionan bien en conjuntos de lecturas que contienen regiones repetidas. ^[1] Los primeros ensambladores de secuencias de novo, como SEQAID ^[2] (1984) y CAP ^[3] (1992), usaban algoritmos voraces, como los algoritmos de superposición-diseño-consenso (OLC). Estos algoritmos encuentran superposición entre todas las lecturas, usan la superposición para determinar un diseño (o mosaico) de las lecturas y luego producen una secuencia de consenso. Algunos programas que utilizaban algoritmos OLC incorporaban filtración (para eliminar pares de lectura que no se superponían) y métodos heurísticos para aumentar la velocidad de los análisis.

Los ensambladores de métodos de grafos ^[4] vienen en dos variedades: de cadenas y De Bruijn. Los ensambladores de métodos de grafos de cadenas y de grafos De Bruijn fueron presentados en un taller de DIMACS ^{[5] en 1994 por} Waterman ^[6] y Gene Myers ^[7] . Estos métodos representaron un importante paso adelante en el ensamblaje de secuencias, ya que ambos utilizan algoritmos para alcanzar un óptimo global en lugar de un óptimo local. Si bien ambos métodos avanzaron hacia mejores ensamblajes, el método de grafos De Bruijn se ha convertido en el más popular en la era de la secuenciación de próxima generación. Durante el ensamblaje del grafo De Bruijn, las lecturas se dividen en fragmentos más pequeños de un tamaño específico, k. Luego, los k-meros se utilizan como bordes en el ensamblaje del grafo. Los nodos se construyen como (k-1)-meros conectados por un borde. Luego, el ensamblador construirá secuencias basadas en el grafo De Bruijn. Los ensambladores de grafos De Bruijn generalmente funcionan mejor en conjuntos de lecturas más grandes que los ensambladores de algoritmos voraces (especialmente cuando contienen regiones repetidas).

Programas de uso común

Se diseñan distintos ensambladores para distintos tipos de tecnologías de lectura. Las lecturas de tecnologías de segunda generación (llamadas tecnologías de lectura corta) como Illumina son típicamente cortas (con longitudes del orden de 50-200 pares de bases) y tienen tasas de error de alrededor del 0,5-2%, siendo los errores principalmente errores de sustitución. Sin embargo, las lecturas de tecnologías de tercera generación como PacBio y tecnologías de cuarta generación como Oxford Nanopore (llamadas tecnologías de lectura larga) son más largas, con longitudes de lectura típicamente de miles o decenas de miles y tienen tasas de error mucho más altas de alrededor del 10-20%, siendo los errores principalmente inserciones y eliminaciones. Esto requiere diferentes algoritmos para el ensamblaje de tecnologías de lectura corta y larga.

Maratón de asambleas

Existen numerosos programas para el ensamblaje de secuencias de novo y muchos de ellos se han comparado en el Assemblathon. El Assemblathon es un esfuerzo periódico y colaborativo para probar y mejorar los numerosos ensambladores disponibles. Hasta el momento, se han completado dos assemblatones (2011 y 2013) y un tercero está en marcha (a fecha de abril de 2017). Equipos de investigadores de todo el mundo eligen un programa y ensamblan genomas simulados (Assemblathon 1) y los genomas de organismos modelo que se han ensamblado y anotado previamente (Assemblathon 2). A continuación, los ensamblajes se comparan y evalúan utilizando numerosas métricas.

Maratón de asamblea 1

En 2011 se llevó a cabo el primer Ensamblathon ^[23] , en el que participaron 59 ensamblajes de 17 grupos diferentes y los organizadores. El objetivo de este Ensamblathon era ensamblar de la forma más precisa y completa un genoma que constaba de dos haplotipos (cada uno con tres cromosomas de 76,3, 18,5 y 17,7 Mb, respectivamente) que se generó utilizando Evolver. Se utilizaron numerosas métricas para evaluar los ensamblajes, entre ellas: NG50 (punto en el que se alcanza el 50 % del tamaño total del genoma cuando se suman las longitudes de los andamios desde el más largo hasta el más corto), LG50 (número de andamios que son mayores o iguales a la longitud N50), cobertura del genoma y tasa de error de sustitución.

• Software comparado: ABySS, Phusion2, phrap, Velvet, SOAPdenovo, PRICE, ALLPATHS-LG
• Análisis N50: los ensamblajes del Plant Genome Assembly Group (utilizando el ensamblador Meraculous) y ALLPATHS, Broad Institute, EE. UU. (utilizando ALLPATHS-LG) obtuvieron el mejor rendimiento en esta categoría, por un orden de magnitud por encima de otros grupos. Estos ensamblajes obtuvieron un N50 de >8 000 000 de bases.
• Cobertura del genoma por ensamblaje: para esta métrica, el ensamblaje de BGI a través de SOAPdenovo tuvo el mejor desempeño, con un 98,8 % del genoma total cubierto. Todos los ensambladores tuvieron un desempeño relativamente bueno en esta categoría, con todos los grupos excepto tres con una cobertura del 90 % o más, y la cobertura total más baja fue del 78,5 % (Dept. of Comp. Sci., University of Chicago, EE. UU. a través de Kiki).
• Errores de sustitución: el conjunto con la tasa de error de sustitución más baja fue enviado por el equipo del Wellcome Trust Sanger Institute, Reino Unido, utilizando el software SGA.
• En general: ningún ensamblador obtuvo un rendimiento significativamente mejor que los demás en todas las categorías. Si bien algunos ensambladores sobresalieron en una categoría, no lo hicieron en otras, lo que sugiere que aún hay mucho margen de mejora en la calidad del software de ensamblador.

Maratón de asamblea 2

El Assemblathon 2 ^[24] mejoró el Assemblathon 1 al incorporar los genomas de múltiples vertebrados (un ave ( Melopsittacus undulatus ), un pez ( Maylandia zebra ) y una serpiente ( Boa constrictor constrictor )) con genomas estimados en 1,2, 1,0 y 1,6 Gbp de longitud) y la evaluación mediante más de 100 métricas. Cada equipo tuvo cuatro meses para ensamblar su genoma a partir de datos de secuencia de próxima generación (NGS), incluidos datos de secuencia de Illumina y Roche 454 .

• Comparación de software: ABySS, ALLPATHS-LG, PRICE, Ray y SOAPdenovo
• Análisis N50: para el ensamblaje del genoma de las aves, los equipos del Centro de Secuenciación del Genoma Humano del Baylor College of Medicine y ALLPATHS tuvieron los NG50 más altos, con más de 16.000.000 y más de 14.000.000 pb, respectivamente.
• Presencia de genes centrales: la mayoría de los ensamblajes tuvieron un buen desempeño en esta categoría (~80% o más), y solo uno cayó a poco más del 50% en su ensamblaje del genoma de las aves (Universidad Estatal de Wayne a través de HyDA).
• En general: en general, el Centro de secuenciación del genoma humano del Baylor College of Medicine, que utiliza una variedad de métodos de ensamblaje (SeqPrep, KmerFreq, Quake, BWA, Newbler, ALLPATHS-LG, Atlas-Link, Atlas-GapFill, Phrap, CrossMatch, Velvet, BLAST y BLASR), obtuvo el mejor rendimiento en los ensamblajes de aves y peces. En el ensamblaje del genoma de la serpiente, el Wellcome Trust Sanger Institute, que utilizó SGA, obtuvo el mejor rendimiento. En todos los ensamblajes, SGA, BCM, Meraculous y Ray presentaron ensamblajes y evaluaciones competitivos. Los resultados de los muchos ensamblajes y evaluaciones descritos aquí sugieren que, si bien un ensamblador puede tener un buen rendimiento en una especie, puede no tener un rendimiento tan bueno en otra. Los autores hacen varias sugerencias para el ensamblaje: 1) utilizar más de un ensamblador, 2) utilizar más de una métrica para la evaluación, 3) seleccionar un ensamblador que se destaque en métricas de mayor interés (por ejemplo, N50, cobertura), 4) N50 bajos o tamaños de ensamblaje bajos pueden no ser preocupantes, dependiendo de las necesidades del usuario, y 5) evaluar los niveles de heterocigosidad en el genoma de interés.

Véase también

• Ensamblaje de secuencias
• Alineación de secuencias
• Montaje del transcriptoma de novo

Referencias

1. J. Bang-Jensen; G. Gutin; A. Yeo (2004). "Cuando el algoritmo voraz falla". Optimización discreta . 1 (2): 121–127. doi : 10.1016/j.disopt.2004.03.007 .
2. Peltola, Hannu; Söderlund, Hans; Ukkonen, Esko (11 de enero de 1984). "SEQAID: un programa de ensamblaje de secuencias de ADN basado en un modelo matemático". Investigación de ácidos nucleicos . 12 (1Parte 1): 307–321. doi :10.1093/nar/12.1Part1.307. ISSN  0305-1048. PMC 321006 . PMID  6320092. 
3. Huang, Xiaoqiu (1992-09-01). "Un programa de ensamblaje de contig basado en la detección sensible de superposiciones de fragmentos". Genomics . 14 (1): 18–25. doi :10.1016/S0888-7543(05)80277-0. PMID  1427824.
4. Compeau, Phillip EC; Pavel A. Pevzner; Glenn Tesler (2011). "Cómo aplicar los grafos de De Bruijn al ensamblaje del genoma". Nature Biotechnology . 29 (11): 987–991. doi :10.1038/nbt.2023. PMC 5531759 . PMID  22068540. 
5. "Taller DIMACS sobre métodos combinatorios para el mapeo y secuenciación de ADN". Octubre de 1994.
6. Idury, RM; Waterman, MS (1 de enero de 1995). "Un nuevo algoritmo para el ensamblaje de secuencias de ADN". Revista de biología computacional . 2 (2): 291–306. CiteSeerX 10.1.1.79.6459 . doi :10.1089/cmb.1995.2.291. ISSN  1066-5277. PMID  7497130. 
7. Myers, EW (1 de enero de 1995). "Hacia la simplificación y formulación precisa del ensamblaje de fragmentos". Revista de biología computacional . 2 (2): 275–290. doi :10.1089/cmb.1995.2.275. ISSN  1066-5277. PMID  7497129.
8. Simpson, Jared T.; et al. (2009). "ABySS: un ensamblador paralelo para datos de secuencias de lectura corta". Genome Research . 19 (6): 1117–1123. doi :10.1101/gr.089532.108. PMC 2694472 . PMID  19251739. 
9. Birol, Inanç; et al. (2009). "Ensamblaje de transcriptoma de novo con ABySS". Bioinformática . 25 (21): 2872–2877. doi : 10.1093/bioinformatics/btp367 . PMID  19528083.
10. Koren, Sergey, Brian P. Walenz, Konstantin Berlin, Jason R. Miller, Nicholas H. Bergman y Adam M. Phillippy. "Canu: ensamblaje escalable y preciso de lecturas largas mediante ponderación adaptativa de k-meros y separación de repeticiones". Genome research 27, no. 5 (2017): 722-736. Disponible aquí
11. Love, R. Rebecca; Weisenfeld, Neil I.; Jaffe, David B.; Besansky, Nora J .; Neafsey, Daniel E. (diciembre de 2016). "Evaluación de DISCOVAR de novo utilizando una muestra de mosquito para el ensamblaje rentable del genoma de lectura corta". BMC Genomics . 17 (1): 187. doi : 10.1186/s12864-016-2531-7 . ISSN  1471-2164. PMC 4779211 . PMID  26944054. 
12. Chin, Chen-Shan, Paul Peluso, Fritz J. Sedlazeck, Maria Nattestad, Gregory T. Concepcion, Alicia Clum, Christopher Dunn et al. "Ensamblaje de genoma diploide en fases con secuenciación de moléculas individuales en tiempo real". Nature methods 13, no. 12 (2016): 1050-1054. Disponible aquí
13. Kolmogorov, Mikhail; Yuan, Jeffrey; Lin, Yu; Pevzner, Pavel A. (1 de abril de 2019). "Ensamblaje de lecturas largas y propensas a errores utilizando gráficos de repetición" (PDF) . Nature Biotechnology . 37 (5): 540–546. doi :10.1038/s41587-019-0072-8. ISSN  1087-0156. PMID  30936562. S2CID  89616540.
14. Chin, Chen-Shan, David H. Alexander, Patrick Marks, Aaron A. Klammer, James Drake, Cheryl Heiner, Alicia Clum et al. "Ensamblajes de genomas microbianos terminados y no híbridos a partir de datos de secuenciación SMRT de lectura larga". Nature methods 10, no. 6 (2013): 563-569. Disponible en línea
15. Cheng, Haoyu; Concepcion, Gregory T.; Feng, Xiaowen; Zhang, Haowen; Li, Heng (febrero de 2021). "Ensamblaje de novo resuelto por haplotipos utilizando gráficos de ensamblaje en fase con hifiasm". Nature Methods . 18 (2): 170–175. arXiv : 2008.01237 . doi :10.1038/s41592-020-01056-5. ISSN  1548-7105. PMC 7961889 . PMID  33526886. 
16. Kamath, Govinda M., Ilan Shomorony, Fei Xia, Thomas A. Courtade y N. Tse David. "HINGE: el ensamblaje de lecturas largas logra una resolución óptima de repetición". Genome research 27, no. 5 (2017): 747-756. Disponible aquí
17. Zimin, Aleksey V.; Marçais, Guillaume; Puiú, Daniela; Roberts, Michael; Salzberg, Steven L.; Yorke, James A. (noviembre de 2013). "El ensamblador del genoma MaSuRCA". Bioinformática . 29 (21): 2669–2677. doi : 10.1093/bioinformática/btt476. ISSN  1367-4803. PMC 3799473 . PMID  23990416. 
18. Steinegger, Martin; Mirdita, Milot; Söding, Johannes (24 de junio de 2019). "El ensamblaje a nivel de proteína aumenta la recuperación de la secuencia de proteínas de muestras metagenómicas muchas veces" (PDF) . Nature Methods . 16 (7): 603–606. doi : 10.1038/s41592-019-0437-4 . hdl :21.11116/0000-0003-E0DD-7. PMID  31235882.
19. Boisvert, Sébastien; François Laviolette; Jacques Corbeil (2010). "Ray: ensamblaje simultáneo de lecturas de una combinación de tecnologías de secuenciación de alto rendimiento". Journal of Computational Biology . 17 (11): 1519–1533. doi :10.1089/cmb.2009.0238. PMC 3119603 . PMID  20958248. 
20. Bankevich, Anton; Nurk, Sergey; Antipov, Dmitry; Gurevich, Alexey A.; Dvorkin, Mikhail; Kulikov, Alexander S.; Lesin, Valery M.; Nikolenko, Sergey I.; Pham, Son; Prjibelski, Andrey D.; Pyshkin, Alexey V. (mayo de 2012). "SPAdes: un nuevo algoritmo de ensamblaje del genoma y sus aplicaciones a la secuenciación de células individuales". Revista de biología computacional . 19 (5): 455–477. doi :10.1089/cmb.2012.0021. ISSN  1066-5277. PMC 3342519 . PMID  22506599. 
21. Grabherr, Manfred G.; et al. (2011). "Ensamblaje del transcriptoma de longitud completa a partir de datos de ARN-Seq sin un genoma de referencia". Nature Biotechnology . 29 (7): 644–652. doi :10.1038/nbt.1883. PMC 3571712 . PMID  21572440. 
22. Zerbino, DR; Birney, E. (21 de febrero de 2008). "Velvet: Algoritmos para el ensamblaje de lecturas cortas de novo utilizando grafos de Bruijn". Genome Research . 18 (5): 821–829. doi :10.1101/gr.074492.107. ISSN  1088-9051. PMC 2336801 . PMID  18349386. 
23. Earl, Dent; et al. (diciembre de 2011). "Assemblathon 1: una evaluación competitiva de los métodos de ensamblaje de lectura corta de novo". Genome Research . 21 (12): 2224–2241. doi :10.1101/gr.126599.111. PMC 3227110 . PMID  21926179. 
24. Bradnam, Keith R.; et al. (2013). "Assemblathon 2: evaluación de métodos de novo de ensamblaje del genoma en tres especies de vertebrados". GigaScience . 2 (1): 10. arXiv : 1301.5406 . doi : 10.1186/2047-217X-2-10 . PMC 3844414 . PMID  23870653.