Assemblage (bio-informatique)

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Page d'aide sur l'homonymie Pour les articles homonymes, voir Assemblage.

En bio-informatique, l'assemblage consiste à aligner et/ou fusionner des fragments d'ADN ou d'ARN issus d'une plus longue séquence afin de reconstruire la séquence originale. Il s'agit d'une étape d'analyse in silico qui succède au séquençage de l'ADN ou de l'ARN d'un organisme unique, d'une colonie de clones (bactériens par exemple), ou encore d'un mélange complexe d'organismes.

Le problème de l'assemblage peut être comparé à celui de la reconstruction du texte d'un livre à partir de plusieurs copies de celui-ci, préalablement déchiquetées en petits morceaux.

Paradigmes d'assemblage[modifier | modifier le code]

Les stratégies d'assemblage peuvent être organisées en 3 principaux paradigmes[1].

Glouton[modifier | modifier le code]

Historiquement la première stratégie d'assemblage, celle-ci consiste à faire systématiquement le meilleur choix disponible sans possibilité de revenir sur ce choix plus tard. Le principal défaut de cette stratégie est qu'elle mène à des optimums locaux sans prendre en compte la relation globale entre les fragments. La plupart des assembleurs gloutons utilisent des heuristiques pour éviter le mauvais assemblage de séquences répétées. La plupart des premiers assembleurs tels que Phrap[2] ou TIGR[3] reposent sur ce paradigme, ainsi que quelques outils plus récents comme VCAKE[4].

"Overlap-Layout-Consensus" (OLC)[modifier | modifier le code]

Cette stratégie d'assemblage se déroule en 3 étapes:

  1. Construction d'un graphe d'intervalles de chevauchement de fragments. Chaque fragment est un nœud du graphe, et une arête est créée entre deux fragments lorsque ceux-ci se chevauchent.
  2. Simplification du graphe. Des sous-graphes denses sont identifiés comme une collection de fragment qui se chevauchent entre eux et qui proviennent probablement de la même séquence originale.
  3. Extraction des séquences consensus. Une séquence consensus (contig) est générée à partir de l'ensemble des fragments de chaque sous-graphe.

Une variante de cette stratégie consiste à supprimer les liens transitifs du graphe de chevauchement pour construire un string graph.

Ce paradigme a notamment été rendu populaire par les travaux de Gene Myers intégrés dans l'assembleur Celera[5]. Les assembleurs de ce type ont dominé le monde de l'assemblage jusqu'à l'émergence des nouvelles technologies de séquençage (NGS). Ces dernières sont caractérisés par la production d'une très grande quantité de petits fragments (de quelques dizaines à plusieurs centaines de nucléotides), et les limites computationnelles de l'approche OLC ont rendu difficile l'application de cette stratégie aux données de séquençage moderne. Récemment, l'assembleur SGA[6] a introduit une nouvelle approche plus efficace basée sur des structures performantes pour l'indexation de chaines de caractère.

Graphe de De Bruijn[modifier | modifier le code]

Les assembleurs basés sur un graphe de De Bruijn modélisent la relation entre des sous-chaines exactes extraites des fragments de séquençage. Dans un graphe de De Bruijn les nœuds sont des mots de taille k (k-mers), et les arêtes sont les chevauchements de taille k-1 entre les k-mers. Par exemple les 5-mers ACTAG et CTAGT partagent exactement 4 lettres. Les fragments ne sont pas directement modélisés dans ce paradigme, mais sont implicitement représentés par des chemins dans le graphe de De Bruijn.

Puisque les assembleurs basés sur ce paradigme repose sur l'identification de chevauchements exacts, ceux-ci sont particulièrement sensibles à la présence d'erreurs de séquençage. Par conséquent, ces méthodes nécessitent l'utilisation d'étapes de correction des erreurs de séquençage avant et pendant l'assemblage afin d'obtenir des assemblages de haute qualité[1].

Cette approche a été popularisée par l'assembleur Euler, et a ensuite dominé le monde de l'assemblage des données modernes de séquençage à courts fragments, avec des outils comme Velvet[7], SOAPdenovo[8] et ALLPATHS[9].

Assemblage de-novo vs. avec référence[modifier | modifier le code]

Domaines d'application[modifier | modifier le code]

Génomique[modifier | modifier le code]

Transcriptomique[modifier | modifier le code]

Méta-génomique[modifier | modifier le code]

Assembleurs disponibles[modifier | modifier le code]

Nom Type Technologies Auteur Publié / Dernière mise à jour Licence* Site
ABySS (grands) génomes Solexa, SOLiD Simpson, J. et al. 2008 / 2014 NC-A lien
ALLPATHS-LG (grands) génomes Solexa, SOLiD Gnerre, S. et al. 2011 OS lien
AMOS génomes Sanger, 454 Salzberg, S. et al. 2002? / 2011 OS lien
Arapan-M génomes moyens (ex. E.coli) All Sahli, M. & Shibuya, T. 2011 / 2012 OS lien
Arapan-S (petits) génomes (virus et bactéries) All Sahli, M. & Shibuya, T. 2011 / 2012 OS lien
Celera WGA Assembler / CABOG (grands) génomes Sanger, 454, Solexa Myers, G. et al.; Miller G. et al. 2004 / 2015 OS lien
CLC Genomics Workbench & CLC Assembly Cell génomes Sanger, 454, Solexa, SOLiD CLC bio 2008 / 2010 / 2014 C lien
Cortex génomes Solexa, SOLiD Iqbal, Z. et al. 2011 OS lien
DNA Baser Assembler (petits) génomes Sanger, 454 Heracle BioSoft SRL 06.2015 C lien
DNA Dragon génomes Illumina, SOLiD, Complete Genomics, 454, Sanger SequentiX 2011 C lien
DNAnexus génomes Illumina, SOLiD, Complete Genomics DNAnexus 2011 C lien
Edena génomes Illumina D. Hernandez, P. François, L. Farinelli, M. Osteras, and J. Schrenzel. 2008/2013 OS lien
Euler génomes Sanger, 454 (Solexa ?) Pevzner, P. et al. 2001 / 2006? (C / NC-A?) lien
Euler-sr génomes 454, Solexa Chaisson, MJ. et al. 2008 NC-A lien
Fermi (grands) génomes Illumina Li, H. 2012 OS lien
Forge (grands) génomes, EST, metagénomes 454, Solexa, SOLID, Sanger Platt, DM, Evers, D. 2010 OS lien
Geneious génomes Sanger, 454, Solexa, Ion Torrent, Complete Genomics, PacBio, Oxford Nanopore, Illumina Biomatters Ltd 2009 / 2013 C lien
Graph Constructor (grands) génomes Sanger, 454, Solexa, SOLiD Convey Computer Corporation 2011 C lien
IDBA (Iterative De Bruijn graph short read Assembler) (grands) génomes Sanger, 454,Solexa Yu Peng, Henry C. M. Leung, Siu-Ming Yiu, Francis Y. L. Chin 2010 (C / NC-A?) lien
LIGR Assembler (derived from TIGR Assembler) génomes Sanger - 2009/ 2012 OS lien
MaSuRCA (Maryland Super Read - Celera Assembler) (grands) génomes Sanger, Illumina, 454 Aleksey Zimin, Guillaume Marçais, Daniela Puiu, Michael Roberts, Steven L. Salzberg, James A. Yorke 2012 / 2013 OS lien
MIRA (Mimicking Intelligent Read Assembly) génomes, ESTs Sanger, 454, Solexa Chevreux, B. 1998 / 2014 OS lien
NextGENe (petits génomes ?) 454, Solexa, SOLiD Softgenetics 2008 C lien
Newbler génomes, ESTs 454, Sanger 454/Roche 2009/2012 C lien
PADENA génomes 454, Sanger 454/Roche 2010 OS lien
PASHA (grands) génomes Illumina Liu, Schmidt, Maskell 2011 OS lien
Phrap génomes Sanger, 454, Solexa Green, P. 1994 / 2008 C / NC-A lien
TIGR Assembler génomes Sanger - 1995 / 2003 OS « lien »(ArchiveWikiwixArchive.isGoogleQue faire ?)
Ray[10] génomes Illumina, mix of Illumina and 454, paired or not Sébastien Boisvert, François Laviolette & Jacques Corbeil. 2010 OS [GNU General Public License] lien
Sequencher génomes traditional and next generation sequence data Gene Codes Corporation 1991 / 2009 / 2011 C lien
SeqMan NGen (grands) génomes, exomes, transcriptomes, metagénomes, ESTs Illumina, ABI SOLiD, Roche 454, Ion Torrent, Solexa, Sanger DNASTAR 2007 / 2014 C lien
SGA (grands) génomes Illumina, Sanger (Roche 454?, Ion Torrent?) Simpson, J.T. et al. 2011 / 2012 OS lien
SHARCGS (petits) génomes Solexa Dohm et al. 2007 / 2007 OS lien
SOPRA génomes Illumina, SOLiD, Sanger, 454 Dayarian, A. et al. 2010 / 2011 OS lien
SparseAssembler (grands) génomes Illumina, 454, Ion torrent Ye, C. et al. 2012 / 2012 OS lien
SSAKE (petits) génomes Solexa (SOLiD? Helicos?) Warren, R. et al. 2007 / 2014 OS lien
SOAPdenovo génomes Solexa Li, R. et al. 2009 / 2013 OS lien
SPAdes (petits) génomes, single-cell Illumina, Solexa, Sanger, 454, Ion Torrent, PacBio, Oxford Nanopore Bankevich, A et al. 2012 / 2015 OS lien
Staden gap4 package BACs (, petits génomes ?) Sanger Staden et al. 1991 / 2008 OS lien
Taipan (petits) génomes Illumina Schmidt, B. et al. 2009 / 2009 OS lien
VCAKE (petits) génomes Solexa (SOLiD?, Helicos?) Jeck, W. et al. 2007 / 2009 OS lien
Phusion assembler (grands) génomes Sanger Mullikin JC, et al. 2003 / 2006 OS lien
Quality Value Guided SRA (QSRA) génomes Sanger, Solexa Bryant DW, et al. 2009 / 2009 OS lien
Velvet (petits) génomes Sanger, 454, Solexa, SOLiD Zerbino, D. et al. 2007 / 2011 OS lien
Canu[11] génomes PacBio, Oxford Nanopore Koren, S. et al. 2017 / 2018 OS lien
*Licences: OS = Open Source; C = Commercial; C / NC-A = Commercial mais gratuit pour non-commercial et académiques; Parenthèses = probablement C / NC-A

Voir aussi[modifier | modifier le code]

Notes et références[modifier | modifier le code]

  1. a et b (en) Niranjan Nagarajan et Mihai Pop, « Sequence assembly demystified », Nature Reviews Genetics, vol. 14,‎ , p. 157–167 (ISSN 1471-0056, DOI 10.1038/nrg3367, lire en ligne)
  2. « Phred, Phrap, and Consed », sur www.phrap.org (consulté le 1er mars 2016)
  3. « JCVI: Abstract », sur www.jcvi.org (consulté le 1er mars 2016)
  4. « VCAKE », sur SourceForge (consulté le 1er mars 2016)
  5. « wgs-assembler », sur wgs-assembler.sourceforge.net (consulté le 1er mars 2016)
  6. « jts/sga », sur GitHub (consulté le 1er mars 2016)
  7. « Velvet: a sequence assembler for very short reads », sur www.ebi.ac.uk (consulté le 1er mars 2016)
  8. BGI,Bioinformatics Center,SOAP Team,GentleYang, « SOAP :: Short Oligonucleotide Analysis Package », sur soap.genomics.org.cn (consulté le 1er mars 2016)
  9. « ALLPATHS-LG | High quality genome assembly from low cost data », sur www.broadinstitute.org (consulté le 1er mars 2016)
  10. (en) Sébastien Boisvert, François Laviolette et Jacques Corbeil, « Ray: simultaneous assembly of reads from a mix of high-throughput sequencing technologies », Journal of Computational Biology, vol. 17, no 11,‎ , p. 1519–33 (PMID 20958248, PMCID 3119603, DOI 10.1089/cmb.2009.0238)
  11. (en) Sergey Koren, Brian P. Walenz, Konstantin Berlin et Jason R. Miller, « Canu: scalable and accurate long-read assembly via adaptive k-mer weighting and repeat separation », Genome Research, vol. 27, no 5,‎ , p. 722–736 (ISSN 1088-9051 et 1549-5469, PMID 28298431, DOI 10.1101/gr.215087.116, lire en ligne)