Recherche sur le Genotype Representation Graph (GRG) : Un nouveau cadre pour améliorer l’efficacité de l’analyse des données biologiques

Contexte académique et motivation de la recherche

Avec les progrès rapides des technologies de séquençage, la collecte de données génomiques à grande échelle est devenue de plus en plus courante, en particulier dans le domaine des études d’association des maladies humaines. La demande d’analyse des données génomiques ne cesse de croître. À la fin de 2023, la UK Biobank a publié environ 500 000 génomes complets sur sa plateforme de cloud computing, dont 200 000 ont déjà été phasés. Ces ensembles de données massifs offrent des opportunités scientifiques sans précédent, mais posent également de nouveaux défis : comment encoder et analyser efficacement des données génomiques aussi vastes ? Les structures de données tabulaires traditionnelles (comme le format de fichier VCF) rencontrent des limites en termes de stockage et d’efficacité de calcul, ce qui rend difficile la gestion des besoins croissants en données.

Dans ce contexte, les scientifiques ont proposé de nouvelles méthodes de représentation et de traitement des données pour optimiser les taux de compression et les performances de calcul. Cette étude vise à développer une nouvelle structure de données avec une efficacité de compression et de calcul plus élevée pour répondre aux besoins d’analyse des données à l’échelle des biobanques.

Source de l’article

Cet article, intitulé “Enabling Efficient Analysis of Biobank-scale Data with Genotype Representation Graphs”, a été réalisé par Drew Dehaas, Ziqing Pan et Xinzhu Wei, et publié dans Nature Computational Science. Les auteurs sont affiliés au département de biologie computationnelle de l’Université Cornell, Dehaas et Pan étant les premiers coauteurs de cet article, tandis que Xinzhu Wei est l’auteur correspondant.

Détail du processus de recherche et des méthodes techniques

Le cœur du développement de la recherche : le Genotype Representation Graph (GRG)

L’équipe de recherche a proposé une structure de données appelée Genotype Representation Graph (GRG), qui vise à résoudre les problèmes d’efficacité de stockage et d’analyse des données génotypiques en restructurant ces données sous forme de graphe par rapport aux encodages tabulaires traditionnels. Le GRG est un graphe acyclique dirigé (directed acyclic graph, DAG) entièrement connecté et hiérarchisé, capable de représenter de manière non destructive (losslessly) les polymorphisme du génome entier phasé.

Caractéristiques clés de la structure du GRG :

1. Types de nœuds : Les nœuds sont divisés en nœuds échantillons (Sample Node), nœuds de mutations (Mutation Node) et nœuds internes (Internal Node). Les nœuds échantillons représentent des génomes haploïdes, et les mutations spécifiques (déviations par rapport à la séquence de référence) sont encodées sous forme de nœuds de mutations.
2. Propriété de graphe acyclique dirigé : Dans le graphe construit par le GRG, il n’existe pas de chemins redondants, et un nœud de mutation à un nœud échantillon est relié par un chemin unique.
3. Conception hiérarchique : Les nœuds internes couvrent efficacement les informations génotypiques partagées par plusieurs échantillons, permettant une compression et évitant des relations redondantes complexes.

Méthodes de recherche et processus expérimental

L’équipe de recherche a conçu une série d’étapes expérimentales pour la construction et la validation du GRG, incluant le développement d’algorithmes, des tests sur données simulées et des applications sur des données biologiques réelles.

(1) Algorithme de construction du GRG

L’algorithme de construction comprend quatre étapes clés : 1. Segmentation du génome : Le génome est d’abord divisé en segments de longueur fixe, chaque segment mesurant 50 à 150 kilobases (kilobase pairs, kbp). 2. Construction d’un graphe arborescent local (Tree GRG, TGRG) : Un arbre de relations ancestrales est créé pour chaque segment, en utilisant la distance de Hamming (Hamming Distance) pour mesurer la similarité des mutations entre les échantillons. 3. Mapping des mutations (Mutation Mapping) : Basé sur l’arbre local, chaque segment de données de mutations est localisé précisément et mappé sur les nœuds correspondants du graphe arborescent local. 4. Fusion du graphe global : Tous les graphes arborescents locaux sont fusionnés en un GRG global, et les numéros de nœuds et la structure du graphe sont optimisés.

Cet algorithme utilise également des filtres de Bloom (Bloom Filter) et des arbres BK (BK-tree) efficaces pour accélérer la recherche de nœuds voisins, réduisant considérablement les coûts de construction.

(2) Tests sur données simulées

Pour tester les performances du GRG, l’équipe de recherche a généré des données génomiques simulées contenant de 10 à 1 million d’échantillons haploïdes à l’aide de l’outil msprime, avec des taux de mutation et de recombinaison fixés à 10^-8 (par paire de bases/génération). Les expériences ont validé l’efficacité de la construction du GRG, la taille des fichiers et les besoins en mémoire vive. Les résultats montrent que le GRG ne nécessite que 10 Go de mémoire pour 1 million d’échantillons, et que la taille des fichiers générés est de 5 à 26 Go (par chromosome), démontrant une scalabilité élevée.

(3) Application sur les données de la UK Biobank

L’équipe a en outre testé l’utilité du GRG sur les données de la UK Biobank contenant 200 000 génomes phasés. En utilisant la parallélisation multithread (avec un CPU de 70 cœurs), la construction du GRG pour les 22 chromosomes a pris seulement 14 heures, et la taille des fichiers était 13 fois plus petite que celle des fichiers VCF, compressant le volume total de données à moins de 160 Go.

(4) Parcours du graphe et calcul dynamique

Le parcours du graphe GRG prend en charge les algorithmes de programmation dynamique, permettant la réutilisation des résultats intermédiaires de calcul. Par exemple, pour la fréquence allélique (Allele Frequency) et les études d’association pangénomique (Genome-Wide Association Study, GWAS), le parcours vers le haut ou vers le bas des nœuds peut considérablement accélérer les calculs. Il est intéressant de noter que cette méthode ressemble à la stratégie de résolution récursive des sous-problèmes en optimisation numérique.

Implémentation logicielle et extension de l’écosystème

L’équipe de recherche a développé une bibliothèque d’outils open-source appelée GRGL pour soutenir la construction et le calcul du GRG, simplifiant considérablement le traitement des données génomiques à grande échelle.

Résultats de la recherche et principales découvertes

1. Efficacité du stockage des fichiers : Comparé aux formats traditionnels VCF et BGEN, le GRG a atteint un taux de compression de 13 fois sur les données de 200 000 génomes de la UK Biobank, et les fichiers compressés ne nécessitent aucune décompression supplémentaire, ce qui rend le traitement plus efficace.
2. Efficacité de calcul : Sur les données simulées et réelles, la méthode de programmation dynamique du GRG a permis d’analyser la fréquence allélique 220 fois plus vite que le format VCF, et l’analyse GWAS a été 2,6 fois plus rapide que les outils traditionnels de calcul matriciel.
3. Validation de la scalabilité : Le GRG prend en charge le traitement des données génomiques d’un million d’échantillons, avec des performances de stockage et de calcul augmentant de manière sous-linéaire avec la taille de l’échantillon, démontrant une excellente scalabilité tant sur les données simulées que sur celles de la UK Biobank.

Synthèse et valeur de la recherche

Cet article présente une méthode efficace de représentation des données génomiques via le GRG, offrant de nouvelles possibilités pour l’analyse des données biologiques à grande échelle. Basé sur le modèle génératif de la diversité génétique biologique et combiné aux concepts de la théorie des graphes, le GRG permet à la fois une compression maximale des données et une amélioration de l’efficacité de calcul. Ses valeurs potentielles comprennent : 1. Compression des données : Atténue efficacement les pressions de stockage et de transmission des données à l’échelle des biobanques. 2. Accélération des calculs : Améliore l’efficacité des tâches statistiques génétiques centrales telles que l’analyse d’association pangénomique et le calcul de la fréquence allélique. 3. Extensibilité future : Le GRG peut non seulement prendre en charge les données humaines, mais aussi être étendu à d’autres espèces, y compris la compression et l’analyse des séquences virales (comme le SARS-CoV-2).

Le GRG proposé dans cette recherche ouvre une nouvelle voie dans le domaine des structures de données et montre le potentiel d’application des structures de graphes en génétique statistique. Le cadre d’analyse des données basé sur le GRG aura un impact profond sur les recherches futures en bioinformatique et en génomique.