Assemblage (bio-informatique)

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].

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.

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 reposent 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].