Identifier une structure de données pratique pour résoudre un problème donné est l’un des principaux facteurs pour obtenir un produit final haute performance. Comme l’explique Skiena dans, choisir la mauvaise structure de données pour le travail peut être désastreux en termes de performances, mais identifier la meilleure structure de données n’est généralement pas aussi critique, car plusieurs choix peuvent fonctionner de la même manière.

Sur la base de la règle diviser pour régner, la première étape consiste à décomposer le problème d’analyse en différents sous-problèmes assez simples pour être résolus en temps polynomial en identifiant une structure de données pratique. Ici, l’algorithme d’analyse peut être divisé en quatre parties: (1) vérifier si les identifiants protéiques / chimiques de l’utilisateur sont présents dans le Réactome, (2) pour les identifiants actuels, déterminer s’il s’agit de parties de complexes et / ou d’ensembles ainsi que la projection d’espèces, (3) agréger les identifiants trouvés dans les voies (et super-voies) où ceux-ci sont présents et enfin (4) effectuer les tests statistiques pour calculer la probabilité que l’association entre les identifiants d’échantillon et la voie trouvée soit due au hasard.

Plus loin dans cette section, chaque partie est discutée en détail pour déterminer ses particularités; exposer la structure de données choisie et les mécanismes adoptés pour son amélioration; et montrer comment connecter chaque étape à la suivante pour arriver à l’algorithme d’analyse amélioré final. Un autre point d’importance pour l’optimisation sera l’utilisation de la mémoire de chaque étape, de sorte que les structures de données remplies puissent être conservées en mémoire pour améliorer les performances des algorithmes de traversée de données mis en œuvre au-dessus d’elles.

Recherche d’identifiants d’échantillon d’utilisateur dans le Reactome

Les entités physiques annotées (PE) dans le Reactome peuvent être des entités simples ou des complexes. Les entités uniques comprennent des protéines, de petites molécules, de l’ARN, de l’ADN, des glucides ou des lipides, tandis que les complexes consistent en une combinaison de l’une des entités uniques ou de polymères synthétisés à partir des entités uniques. Cependant, en dehors de ces deux catégories principales, les conservateurs de Reactome peuvent regrouper des entités associées en ensembles. Les PES sont les éléments constitutifs qui seront plus tard utilisés comme entrées, sorties, catalyseurs ou régulateurs dans les réactions.

Les identifiants ou numéros d’accession sont utilisés pour désigner sans équivoque une seule entité, mais les EP ont des emplacements différents pour contenir l’identifiant principal, l’identifiant secondaire, les références croisées, les synonymes et d’autres identifiants. L’emplacement principal de l’identifiant est toujours annoté manuellement par les experts qui gèrent les données dans Reactome (conservateurs), et les autres emplacements peuvent être remplis manuellement pendant la conservation ou remplis automatiquement pendant le processus de publication. Cette stratégie permet de stocker des identifiants pour un large éventail de ressources: UniProt, ChEBI, Ensemble, miRBase, GenBank/EMBL/DDBJ, RefPep, RefSeq, EntrezGene, OMIM, InterPro, Affymetrix, Agilent, Composé de KEGG, Illumina, etc.

Par conséquent, dans la première partie de l’analyse, l’exigence principale est d’améliorer le processus de recherche si chaque identifiant de l’échantillon de l’utilisateur correspond à un ou plusieurs PEs dans le Réactome. Un identifiant correspond à un PE s’il correspond à l’un quelconque des identifiants stockés dans les différents emplacements mentionnés ci-dessus. En fait, la meilleure façon de résoudre ce problème est de suivre l’approche inverse; création d’une table de recherche avec tous les PEs correspondants pour chaque identifiant référencé dans Reactome. En conséquence, une autre exigence importante est de minimiser l’utilisation de la mémoire afin que les données puissent être conservées en mémoire pour améliorer le temps de requête.

La sélection d’une bonne structure de données est alors déterminée par les exigences à la fois pour implémenter une table de recherche rapide et pour maintenir une utilisation de la mémoire faible. Un Trie est une structure de données arborescente ordonnée qui est utilisée pour stocker un ensemble dynamique ou un tableau associatif où les clés sont généralement des chaînes. Une arborescence radix est une structure de données Trie optimisée pour l’espace où chaque nœud avec un seul enfant est fusionné avec son parent.

D’une part, un arbre radix a une utilisation de mémoire relativement faible pour la table de recherche car les préfixes communs sont partagés évitant la duplication des données (Fig. 1). D’autre part, le coût de la comparaison d’une clé de recherche d’égalité avec une clé de la structure de données peut être un coût dominant qui ne peut être négligé. L’algorithme de recherche de chaînes d’arborescence radix correspond à l’objectif initial de l’algorithme d’analyse car l’itération sur des nœuds d’arborescence limite le temps de recherche de l’identifiant à la longueur et à l’existence de chaque identifiant dans l’ensemble cible du Réactome. En conséquence, dans le cas où l’identifiant recherché n’est pas contenu dans la structure de données, il n’est pas nécessaire de tout lire comme cela se produit dans les méthodes de hachage où la valeur de hachage de la chaîne doit être calculée dans tous les cas en la lisant entièrement.

Représentation arborescente Radix pour les identifiants P60484, P60467, P60468, P29172, P11087, P11086, P10639, P10636, P10635, P10622, P10620, P12939, P12938, P12931, P05480, P05386, PTEN

En résumé, une fois qu’un nœud d’arbre est atteint en suivant l’algorithme de recherche d’arbre radix pour un identifiant donné, la présence ou l’absence de références à PEs indique si l’identifiant associé est présent ou non dans la base de données. En fait, les « références à PE » mentionnées sont en effet des pointeurs vers des nœuds de la structure de données choisie pour la partie suivante de l’analyse.

Reactome utilise des identificateurs primaires uniques pour les références PEs it, en particulier UniProt pour les protéines et ChEBI pour les entités chimiques. Ainsi, si les utilisateurs soumettent des ensembles de données à l’aide de ces systèmes de référence, le mappage vers PEs est simple. Cependant, à la suite de demandes fréquentes des utilisateurs, nous acceptons également des données d’entrée avec des identifiants non uniques, en particulier des noms de gènes. Ceux-ci sont ensuite potentiellement mappés à plusieurs PEs. Ainsi, chaque nœud cible de l’arborescence peut contenir plus d’un pointeur vers la structure de données suivante.

Traverser des complexes/ensembles de composition et de projection d’espèces

Atteindre l’entité unique associée pour un identifiant donné est le début de la deuxième étape de l’analyse. Lorsque ces entités uniques font partie d’un complexe, elles sont également une cible dans cette étape de l’analyse. Outre les entités et complexes uniques, il existe un autre type de PE appelé ensembles qui, avec les complexes, doivent également être considérés. Un ensemble est une représentation abstraite d’un groupe de deux entités ou plus qui n’interagissent pas entre elles mais qui sont fonctionnellement équivalentes dans la situation où l’ensemble est utilisé, par exemple plusieurs membres d’une famille d’enzymes qui pourraient chacune potentiellement catalyser une réaction. De plus, les complexes et ensembles peuvent également contenir d’autres complexes et ensembles afin de représenter des structures beaucoup plus élaborées provoquant une augmentation de la complexité du problème.

Une autre exigence spécifique est la possibilité d’effectuer une projection d’espèces pour collecter les résultats pour Homo sapiens indépendamment de l’espèce pour laquelle les identifiants sont fournis, afin de bénéficier de l’annotation de Réactome plus complète pour l’Homme. Pour ce faire, les orthologues d’espèces annotés dans le Réactome doivent être pris en compte. Les orthologues sont des entités de différentes espèces qui ont évolué à partir d’un ancêtre commun par spéciation.

La dernière exigence dans cette étape est de garder une trace de la cartographie des identifiants entre les identifiants soumis et ceux utilisés dans Reactome pour organiser les entités uniques: accessions UniProt pour les protéines, identificateur d’ensemble pour les gènes, identificateurs CHEBI pour les petites molécules et miRBase pour les microARN. Bien qu’une partie importante de ce mappage ait commencé par inclure les références croisées connues comme identifiants dans l’arborescence radix à l’étape précédente, le mappage lui-même doit être mis en œuvre dans cette étape.

Résumant les exigences exposées pour cette étape de l’analyse, la structure de données choisie doit modéliser le problème de composition des entités, la projection des orthologues des espèces et la cartographie des entités. Un graphe dirigé est un graphe, ou un ensemble de nœuds reliés par des arêtes, où les arêtes ont une direction qui leur est associée. Pour un graphe G donné à plusieurs noeuds (a, b, c et d), si G a une flèche de a à b et une autre flèche de b à c, alors le graphe composé G2 a une flèche de a à c. Si G a une flèche de a à b, une autre flèche de b à c et encore une autre de c à d, alors le graphe composé G3 a une flèche de a à d.

Construire un graphe par espèce (Fig. 2a) et les interconnectant tous reliant tous les noeuds ortholog (Fig. 2b) crée un graphique plus grand où l’exigence de projection est alors satisfaite. En raison de l’unicité du nœud dans le graphe final, dans les cas où un nœud fait partie d’une ou plusieurs entités structurées, il contient autant d’arêtes pointant vers d’autres nœuds de graphe que de structures dans lesquelles il est contenu, de sorte que les entités structurées sont facilement modélisées. Enfin, si chaque noeud du graphe contient son identifiant principal d’entité associé (Fig. 2c), lorsqu’elle est atteinte à partir d’un nœud d’arbre radix représentant un identifiant autre que le principal, cette association est mémorisée pour être proposée dans le cadre du résultat comme le mappage requis une fois l’analyse terminée.

Représentation graphique où P sont des protéines; C sont des complexes, S sont des ensembles et les nœuds premiers sont les mêmes mais pour les autres espèces. un graphique d’une espèce. b Relation entre deux espèces. contenu du nœud de base c

Le graphique de la Fig. 2a montre trois protéines (P1, P2 et P3), deux complexes (C1 et C2) et deux ensembles (S1 et S2). En suivant le bord d’un nœud à l’autre, S2 pourrait être P2 ou P3, formellement représenté comme . C1 est un complexe qui, du fait de son bord par rapport à S2, est alors potentiellement deux complexes : {P1,P2} ou {P1, P3}, représenté par. Suite à cette déconstruction, S1 l’est alors et enfin C2 l’est.

Par exemple, lorsqu’un identifiant correspondant à P3 est traité et que son nœud correspondant dans le graphe est atteint depuis l’arbre radix, il faut un temps de traitement infime pour parcourir le graphe et atteindre les nœuds S2, C1, S1 et C2. De même, si la protéine cible est P1, les nœuds accessibles suivant les arêtes du graphe sont C1, S1 et C2. Dans les deux exemples, chaque protéine cible fait partie des complexes et ensembles représentés par les nœuds traversés.

L’utilisation d’un graphique améliore le coût de l’algorithme d’analyse et, important dans la construction d’une analyse en mémoire, l’utilisation de la mémoire est maintenue faible car il n’y a pas de duplication de données car le nœud d’un identifiant principal donné n’est en mémoire qu’une seule fois. De plus, le nombre final d’itérations de nœuds de l’algorithme est limité par les entités associées pour un identifiant donné, évitant les requêtes sur une grande quantité de données et la fusion de résultats intermédiaires, comme cela se fait dans l’approche basée sur une base de données.

Comme pour l’arbre radix décrit ci-dessus, le graphe nécessite également une stratégie pour permettre à l’algorithme de passer à l’étape d’analyse suivante. Dans ce cas, chaque nœud graphique représentant une entité directement associée à une ou plusieurs voies contiendra autant de liens vers la structure de données suivante que de différents emplacements où elle est présente. Bien que dans l’étape d’analyse en cours, chaque entité associée à l’identifiant cible soit trouvée, pour le résultat final et le calcul statistique, il reste encore une structure de données à utiliser, comme expliqué dans la sous-section suivante.

Agrégation des résultats dans l’organisation des voies

Chaque PE touché directement ou indirectement à l’étape précédente est associé à une ou plusieurs voies. Pour calculer la signification de chaque voie, pour un échantillon d’utilisateur donné, il est essentiel de déterminer le nombre d’entités trouvées par voie. En raison de l’organisation parent-enfant des voies du Réactome dans une hiérarchie de type ontologique, lorsqu’une entité est présente dans une certaine voie, elle est également présente dans ses super-voies de manière récursive jusqu’à ce qu’une voie de niveau supérieur soit atteinte (i.e. si une protéine est présente dans le « Métabolisme des glucides », elle l’est également dans le « métabolisme »).

Compte tenu des exigences précédemment discutées, une bonne structure de données pour modéliser cette étape est un arbre à double liaison, où chaque nœud représente une voie et contient des liens vers son parent et ses enfants (Fig. 3). Lorsqu’un nœud de l’arborescence est touché, l’action peut être propagée récursivement jusqu’à la racine. Pour réduire l’empreinte mémoire, seuls les identifiants, les noms et les espaces réservés pour le calcul des résultats sont conservés dans chaque nœud.

Arbre à double liaison pour représenter la hiérarchie des événements dans le Reactome. Le nœud racine définit l’espèce et ses enfants représentent les différentes voies et sous-voies du Réactome. Chaque nœud contient l’identifiant de voie, le nom, le total des entités organisées et le nombre d’entités trouvées dans l’échantillon de l’utilisateur

En plus d’être une structure de données pratique pour accélérer la collecte des résultats et un bon détenteur des résultats statistiques, une fois l’analyse terminée, cette structure de données peut également être sérialisée dans un fichier pour conserver le résultat. En outre, l’association du fichier à un jeton fournit un moyen facile de créer des méthodes plus fines qui permettent de filtrer le résultat côté serveur pour accélérer les clients légers. Dans ce scénario, les clients peuvent conserver le jeton une fois l’analyse initiale terminée et en fonction des besoins de l’utilisateur, effectuer plusieurs requêtes au serveur référençant le jeton associé.

Calcul des statistiques des résultats de l’analyse

L’hypothèse de base d’une analyse de surreprésentation est que des voies pertinentes peuvent être détectées si la proportion de gènes exprimés différentiellement, au sein d’une voie donnée, dépasse la proportion de gènes pouvant être attendus au hasard. Par conséquent, la quatrième et dernière étape de la méthode d’analyse implique le calcul des statistiques. Cette étape ne nécessite aucune structure de données supplémentaire car l’arbre à double liaison correspond parfaitement à l’objectif.

La valeur p montre la signification statistique de chaque voie de succès pour un échantillon donné et le contexte pour lequel l’analyse a été effectuée. Dans le Reactome, la méthode utilisée pour calculer la signification statistique est le Test binomial. Avec la valeur p, le Taux de fausses découvertes (FDR) aide à estimer les faux positifs et il est calculé en utilisant l’approche Benjamini-Hochberg. Comme mentionné plus haut, nous nous sommes concentrés sur l’optimisation des performances de l’analyse de la voie du Réactome, tout en maintenant l’algorithme de base tel que précédemment publié.