Les technologies de séquençage permettent d’obtenir la séquence (suite de symboles) qui représente une molécule d’ADN, d’ARN ou encore de protéines. La bioinformatique permet d’analyser ces séquences grâce à des algorithmes issus du domaine d’algorithmique du texte (stringology en anglais). Avec la révolution des technologies de séquençage à haut débit, le volume de séquences à traiter explose. Les projets de génomique ou de transcriptomique produisent chacun des centaines de millions de séquences (aussi appelées lectures). Nous concevons des algorithmes performants pour analyser les séquences biologiques à grande échelle. Ces algorithmes sont implantés dans des logiciels de bioinformatique qui allient efficacité et sensibilité, par exemple pour
- corriger les erreurs de séquençage (LoRDEC, LoRMA)
- trouver la position d’une séquence dans un génome (CRAC, MPSCAN)
- comparer des génomes (QOD, YOC)
- pour l’assemblage et l’échaffaudage de génomes (SAVAGE, SCAFFOLDER)
- pour la recherche de motif de fixation de protéines.
Ces logiciels sont diffusés au travers de notre plateforme de bioinformatique ATGC. Ils sont ensuite utilisés sur des données réelles pour des études en biologie moléculaire, en biodiversité, en biologie évolutive. Par exemple,
- le projet du génome d’une micro-algue marine
- étudier la réplication du génome des vertébrés
- ou les transcriptomes humain, d’animaux ou de plantes.
La Figure 1 présente un résultat d’application dans un projet génomique : Visualisation circulaire des chromsomes du génome de O. tauri une pico-algue présente dans toutes les mers du globe. (Blanc-Mathieu et al., BMC Genomics, 15:1103 10.1186/1471-2164-15-1103, 2014)
L’efficacité de ces outils provient souvent de l’utilisation de structures de données d’indexation, comme l’arbre des suffixes, la transformée de Burrows-Wheeler, ou les arbres à ondelettes. Par exemple, nous avons proposé des algorithmes pour
- construire de graphes d’assemblage (Figure 2)
- calculer des superchaines (Figures 3, 4)
- comparer des séquences à des graphes.
Figure 2 : Représentation d’un graphe de De Bruijn dans une structure d’arbre des suffixes généralisée. (Cazaux et al., J. Computer System & Sciences, http://dx.doi.org/10.1016/j.jcss.2016.06.008, 2016).
La plupart des questions informatiques appartiennent à la catégorie des problèmes d’optimisation et sont difficiles. On cherche alors des algorithmes d’approximation et on étudie leur ratio d’approximation qui mesure une distance à une solution optimale. Les algorithmes gloutons en sont un exemple.
Figure 3 : Pour un ensemble de trois séquences P := { ATCA, AGTA, CTGA } et leurs complémentaires inversés, représentation du (classique) graphe des chevauchements (Cazaux et al., Data Compression Conf. 2016).
Figure 4 : Pour un ensemble de trois séquences P := { ATCA, AGTA, CTGA } et leurs complémentaires inversés, représentations du graphe des chevauchements, qui contient les mêmes informations que le graphe de chevauchements, mais utilise une mémoire espace linéaire (Cazaux et al., Data Compression Conf. 2016).
