Comment la bioinformatique a résolu le puzzle du génome du SARS-CoV-2

Un problème fondamental en bio-informatique : l'alignement de séquences d'ADN 

Est-ce que des séquences d’ADN se ressemblent ? De « combien » se ressemblent-elles ? C’est en alignant les séquences qu’on peut répondre à ces questions (voir figure 1 ci-dessus, à gauche). L'alignement est le processus algorithmique qui consiste à comparer des séquences, nucléotide par nucléotide, pour identifier les similitudes et les différences. Dans le cas de séquences similaires, les différences correspondent à des mutations, qui sont des événements évolutifs naturels, ou à des erreurs de séquençage : remplacement d'un nucléotide par un autre, insertion d'un nucléotide supplémentaire ou suppression d'un nucléotide.

Comment chercher une aiguille dans une botte de foin ?

Pour identifier l’alignement optimal, qui minimise le nombre de différences entre deux séquences, il est nécessaire d’explorer toutes les combinaisons d’insertions ou suppressions possibles. Néanmoins il en existe un nombre exponentiel en la longueur de la séquence. Par conséquent, l'approche naïve consistant à calculer tous les alignements est infaisable en pratique. L’alignement est résolu comme un problème d'optimisation en utilisant la programmation dynamique, un paradigme algorithmique classique. L’idée est de diviser le problème en sous-problèmes plus petits et de calculer ainsi l'alignement optimal sans recourir à des approximations.

Des alignements peuvent également être calculés entre une séquence requête et une base de données contenant des millions de génomes (voir figure 1 ci-dessus, à droite). Cela permet par exemple d’identifier dans la soupe initiale des lectures de séquençage d'un échantillon pulmonaire celles provenant du génome humain et d’autres parasites respiratoires connus, afin de les écarter. Pour de telles comparaisons à grande échelle, le calcul des alignements exacts par programmation dynamique nécessiterait des mois de calcul. Pour surmonter cette difficulté, les chercheurs et chercheuses en bio-informatique ont proposé des heuristiques efficaces capables de traiter des gigaoctets de données ADN avec un ordinateur de bureau. Le calcul est effectué en organisant la base de données en une structure d'indexation qui répertorie tous les mots d'une longueur donnée, appelés k-mers, provenant des génomes à indexer et qui permet un accès direct à ces mots, à la manière d’un dictionnaire. La conception de telles structures d’index est un sujet de recherche actif. À titre d’exemple, on peut citer les approches par hachage.

Après avoir rapidement identifié les séquences qui partagent des k-mers, des alignements plus précis et plus longs peuvent être réalisés par programmation dynamique. Ce type d'approche permet d'identifier une aiguille dans une botte de foin : des similarités aussi courtes que dix nucléotides entre la séquence d'intérêt et la base de données.

Signification statistique des alignements

Mais, avec de grands volumes de données, des correspondances peuvent se produire par hasard, sans signification biologique. Il est donc crucial d'évaluer la signification statistique des alignements trouvés, ce qui est fait avec des calculs de E-valeurs qui mesurent le nombre d'alignements attendus du seul fait du hasard. Plus ces valeurs sont proches de 0, et moins la correspondance est imputable au hasard. Par exemple, il est possible de trouver des similitudes locales entre le gène de la protéine Spike du SARS-CoV-2 et le génome d’organismes de l'arbre du vivant aussi divers que les bactéries Escherichia coli et Bacillus subtilis, le maïs, le poisson zèbre, ou même un virus non apparenté, comme le VIH. Ces correspondances ont toutes une E-valeur supérieure à 0,01, ce qui n'est pas significatif, tandis que l'alignement entre le gène spike du SARS-CoV-2 et d'autres gènes spike de coronavirus atteint une E-valeur des milliards de milliards de fois plus faible.

Le principe du graphe de De Bruijn appliqué au problème de l'assemblage

La méthode la plus couramment employée pour reconstruire un génome à partir de lectures de séquençage repose sur un « graphe de De Bruijn ». Ce nom vient du mathématicien Nicolaas de Bruijn, qui a introduit cette structure de données dans les années 1940 en tant qu'objet combinatoire. Le graphe de De Bruijn a fait son entrée en bio-informatique soixante ans plus tard, avec l'avènement du séquençage à haut débit. En effet, la quantité de données de séquençage générées classiquement par une expérience (gigaoctets, voire téraoctets) a rendu les méthodes obsolètes et a nécessité un nouveau paradigme pour l'assemblage des génomes.

Les lectures sont découpées en mots d'une longueur fixe k, les k-mers, qui sont plus courts que les lectures entières. Dans l'exemple ci-dessus, nous avons pris k = 4, mais en pratique, la valeur de k varie entre 20 et 130 de telle sorte que la majorité des k-mers soient présents une seule fois dans le génome à reconstruire. Le graphe de l'ensemble des lectures est alors construit en prenant chaque k-mer unique comme sommet et en ajoutant une arête entre deux sommets si les k-mers se chevauchent exactement de k−1 nucléotides. Ce faisant, la taille du graphe ne dépend que du nombre de k-mers distincts, plutôt que du nombre total de lectures. Cela fait une économie conséquente. De plus, les arêtes peuvent être très rapidement calculées et ne nécessitent pas d'être stockées explicitement puisqu'elles sont déduites de la liste des sommets.

La séquence originale du génome est obtenue comme un chemin dans ce graphe. Ce parcours de graphe est lié à la recherche de chemins eulériens, qui sont des chemins où chaque arête est visitée exactement une fois, tout en permettant de visiter plusieurs fois un sommet si nécessaire. Calculer le chemin eulérien est un problème facile, et il existe un algorithme en temps proportionnel au nombre de sommets du graphe pour le calculer. La méthode doit cependant être adaptée pour prendre en compte le caractère expérimental des données : erreurs de séquençage, régions génomiques répétées ou non couvertes par le séquençage.