Algorithmes et méthodes d'assemblage de génomes

L'assemblage de génomes est le problème computationnel de la reconstruction d'un génome à partir des nombreuses lectures (reads) courtes ou longues qui se chevauchent, produites par séquençage, étant donné qu'aucune technologie actuelle ne permet de lire un chromosome entier de bout en bout. Les algorithmes qui le résolvent déterminent avec quelle complétude et précision un génome peut être reconstitué à partir de données de séquence brutes.

Definition

L'assemblage de génomes est la reconstruction algorithmique de la séquence d'un génome par la détection des chevauchements entre les lectures de séquençage et leur fusion en séquences contiguës plus longues (contigs), lesquelles peuvent ensuite être ordonnées et orientées en scaffolds, soit sans (de novo), soit avec (guidé par référence) une référence existante.

Scope

Cette entrée couvre les deux paradigmes algorithmiques dominants, l'approche chevauchement-agencement-consensus (overlap-layout-consensus) et le graphe de De Bruijn, la distinction entre l'assemblage de novo et l'assemblage guidé par référence, ainsi que les concepts de contigs et de scaffolds. Il s'agit d'un sujet méthodologique axé sur l'étape de reconstruction computationnelle et n'aborde pas les protocoles de laboratoire ni l'utilisation clinique.

Core questions

• Pourquoi les lectures de séquençage doivent-elles être assemblées plutôt que lues directement comme des chromosomes entiers ?
• En quoi les approches chevauchement-agencement-consensus et graphe de De Bruijn diffèrent-elles ?
• Qu'est-ce qui limite la complétude de l'assemblage, et comment les répétitions et la longueur des lectures sont-elles importantes ?

Key concepts

• Assemblage par chevauchement-agencement-consensus
• Assemblage par graphe de De Bruijn
• k-mers
• Contigs et scaffolds
• Assemblage de novo versus assemblage guidé par référence
• Résolution des répétitions
• Contiguïté de l'assemblage (par ex., N50)

Mechanisms

Les algorithmes d'assemblage reconstruisent un génome en exploitant les chevauchements entre les lectures. Les méthodes de chevauchement-agencement-consensus (overlap-layout-consensus) calculent les chevauchements par paires entre les lectures, les agencent en une disposition (layout) et en dérivent une séquence consensus; cette approche était adaptée aux lectures plus longues et a sous-tendu les premiers assemblages de génomes entiers par shotgun. Les méthodes basées sur le graphe de De Bruijn, quant à elles, décomposent les lectures en sous-séquences de longueur fixe (k-mers) et représentent le génome comme des chemins à travers un graphe de k-mers qui se chevauchent, ce qui s'adapte efficacement aux très grands nombres de lectures courtes produites par le séquençage à haut débit. Les régions répétitives plus longues que la longueur des lectures créent des ambiguïtés qui fragmentent les assemblages; par conséquent, des lectures plus longues et des informations de paires sont utilisées pour les résoudre et pour lier les contigs en scaffolds.

Clinical relevance

L'assemblage de génomes est le fondement computationnel qui transforme les données de séquençage brutes en séquences contiguës utilisées pour construire des génomes de référence et pour étudier des organismes précédemment non caractérisés. Cette entrée est un matériel de référence et éducatif décrivant le fonctionnement de l'assemblage et ne constitue pas une directive pour une procédure clinique ou diagnostique.

Evidence & guidelines

La littérature méthodologique est principalement basée sur des articles originaux et des revues, plutôt que sur des lignes directrices : Idury et Waterman (1995) ont introduit une formulation graphique préfigurant l'assemblage de De Bruijn, Zerbino et Birney (2008) ont établi l'assemblage par graphe de De Bruijn pour les lectures courtes avec Velvet, et l'assemblage par shotgun du génome humain entier (Venter et al., 2001) illustre le paradigme chevauchement-agencement-consensus à grande échelle.

History

Les premiers assembleurs utilisaient des méthodes de chevauchement-agencement-consensus bien adaptées aux lectures relativement longues du séquençage Sanger, comme dans l'assemblage par shotgun du génome humain entier en 2001. Le passage au séquençage à haut débit de lectures courtes a fait des méthodes basées sur le graphe de De Bruijn, anticipées par des formulations graphiques du milieu des années 1990 et concrétisées dans des outils tels que Velvet (2008), le paradigme dominant, tandis que le retour ultérieur des lectures longues a ravivé l'intérêt pour les approches basées sur les chevauchements pour la résolution des répétitions.

Key figures

• Michael Waterman
• Daniel Zerbino
• Ewan Birney
• Eugene Myers

Seminal works

• idury-1995
• zerbino-2008
• venter-2001-asm

Frequently asked questions

Quelle est la différence entre l'assemblage de novo et l'assemblage guidé par référence ?

L'assemblage de novo reconstruit un génome à partir des seules lectures, sans utiliser de séquence préalable, tandis que l'assemblage guidé par référence aligne ou assemble les lectures contre un génome de référence existant pour faciliter la reconstruction.

Pourquoi les régions répétitives sont-elles difficiles à assembler ?

Lorsqu'une répétition est plus longue que les lectures qui la couvrent, l'algorithme ne peut pas déterminer de quelle copie une lecture provient, ce qui crée des chemins ambigus qui fragmentent l'assemblage en fragments plus courts; des lectures plus longues aident à résoudre ces répétitions.