Identificare una struttura dati conveniente per risolvere un dato problema è uno dei fattori principali per ottenere un prodotto finale ad alte prestazioni. Come spiega Skiena, scegliere la struttura dati sbagliata per il lavoro può essere disastroso in termini di prestazioni, ma identificare la migliore struttura dati di solito non è così critica, perché ci possono essere diverse scelte che si comportano in modo simile.

In base alla regola divide et impera, il primo passo è abbattere il problema di analisi in diversi sotto-problemi abbastanza semplici da essere risolti in tempo polinomiale identificando una comoda struttura dati. Qui, l’algoritmo di analisi può essere suddiviso in quattro parti: (1) controllare se l’utente proteina/chimico identificatori sono presenti in Reactome, (2) per i presenti, per la ricerca se queste sono parti di complessi e/o imposta così come le specie di proiezione, (3) l’aggregazione trovato identificatori nei percorsi (e super-percorsi in cui queste sono presenti e, infine, (4) esegue i test statistici per calcolare la probabilità che l’associazione tra il campione e gli identificatori trovato il percorso è dovuto alla casualità.

Più avanti in questa sezione ogni parte viene discussa in dettaglio per determinarne le peculiarità; esporre la struttura dei dati scelta e i meccanismi adottati per il suo miglioramento; e mostrare come collegare ogni passaggio a quello successivo per elaborare l’algoritmo di analisi finale migliorato. Un altro punto di enfasi per l’ottimizzazione sarà l’utilizzo della memoria di ogni passaggio, in modo che le strutture di dati riempite possano essere mantenute in memoria per migliorare le prestazioni degli algoritmi di attraversamento dei dati implementati su di essi.

La ricerca degli identificatori di esempio utente in Reactome

Le entità fisiche annotate (PE) in Reactome possono essere singole entità o complessi. Le singole entità includono proteine, piccole molecole, RNA, DNA, carboidrati o lipidi, mentre i complessi consistono in una combinazione di una qualsiasi delle singole entità o polimeri sintetizzati dalle singole entità. Tuttavia, oltre a queste due categorie principali, i curatori di Reactome possono raggruppare entità correlate in set. I PES sono gli elementi costitutivi che in seguito verranno utilizzati come input, output, catalizzatori o regolatori nelle reazioni.

Gli identificatori o i numeri di adesione vengono utilizzati per riferirsi inequivocabilmente a una singola entità, ma i PES hanno slot diversi per contenere l’identificatore principale, l’identificatore secondario, i riferimenti incrociati, i sinonimi e altri identificatori. Lo slot identificativo principale è sempre annotato manualmente dagli esperti che curano i dati in Reactome (curatori), e gli altri slot possono essere riempiti manualmente durante la cura o popolati automaticamente durante il processo di rilascio. Questa strategia consente di memorizzare gli identificatori per una vasta gamma di risorse: UniProt, ChEBI, Ensembl, miRBase, GenBank / EMBL / DDBJ, RefPep, RefSeq, EntrezGene, OMIM, InterPro, Affymetrix, Agilent, Composto di KEGG, Illumina, ecc.

Pertanto, nella prima parte dell’analisi, il requisito principale è quello di migliorare il processo di scoprire se ogni identificatore nel campione dell’utente corrisponde a uno o più PES in Reactome. Un identificatore corrisponde a un PE se corrisponde a uno qualsiasi degli identificatori memorizzati nei diversi slot menzionati in precedenza. In effetti, il modo migliore per risolvere questo problema è seguire l’approccio inverso; creazione di una tabella di ricerca con tutti i PES corrispondenti per ciascun identificatore referenziato in Reactome. Di conseguenza, un altro requisito importante è ridurre al minimo l’utilizzo della memoria in modo che i dati possano essere conservati in memoria per migliorare il tempo di query.

La selezione di una buona struttura dati viene quindi determinata dai requisiti sia per implementare una tabella di ricerca veloce che per mantenere basso l’utilizzo della memoria. Un Trie è una struttura dati ad albero ordinata che viene utilizzata per memorizzare un set dinamico o un array associativo in cui le chiavi sono solitamente stringhe . Un albero radix è una struttura dati Trie ottimizzata per lo spazio in cui ogni nodo con un solo figlio viene unito al suo genitore .

Da un lato, un albero radix ha un utilizzo di memoria relativamente basso per la tabella di ricerca perché i prefissi comuni sono condivisi evitando la duplicazione dei dati (Fig. 1). D’altra parte, il costo del confronto di una chiave di ricerca per l’uguaglianza con una chiave della struttura dati può essere un costo dominante che non può essere trascurato. L’algoritmo di ricerca della stringa dell’albero radix si adatta allo scopo originale dell’algoritmo di analisi perché l’iterazione sui nodi dell’albero mantiene il tempo di ricerca dell’identificatore limitato alla lunghezza e all’esistenza di ciascun identificatore nel set di destinazione Reactome. Di conseguenza, nel caso in cui l’identificatore cercato non sia contenuto nella struttura dati, non è necessario leggerlo tutto come accade nei metodi di hashing in cui il valore hash della stringa deve essere calcolato in ogni caso leggendolo interamente.

Radice di albero di rappresentanza per gli identificatori P60484, P60467, P60468, P29172, P11087, P11086, P10639, P10636, P10635, P10622, P10620, P12939, P12938, P12931, P05480, P05386, PTEN

In sintesi, una volta che un nodo dell’albero è raggiungibile dalla radice dell’albero dell’algoritmo di ricerca di un dato identificativo, la presenza o l’assenza di riferimenti a PEs indica se associato un identificatore è presente o non presente nel database. In realtà, i citati “riferimenti a PE” sono effettivamente puntatori ai nodi nella struttura dati scelta per la parte successiva dell’analisi.

Reactome utilizza identificatori primari univoci per i PES a cui fa riferimento, in particolare UniProt per le proteine e ChEBI per le entità chimiche. Pertanto, se gli utenti inviano set di dati utilizzando questi sistemi di riferimento, la mappatura a PEs è semplice. Tuttavia, a seguito di frequenti richieste degli utenti, accettiamo anche dati di input con identificatori non univoci, in particolare nomi di geni. Questi sono quindi potenzialmente mappati su più PES. Pertanto, ogni nodo di destinazione nell’albero potrebbe contenere più di un puntatore alla struttura dati successiva.

Attraversare la composizione di complessi/insiemi e la proiezione di specie

Raggiungere la singola entità associata per un determinato identificatore è l’inizio del secondo passaggio nell’analisi. Quando queste singole entità fanno parte di un complesso, sono anche un obiettivo in questa fase dell’analisi. Oltre alle singole entità e complessi, c’è un altro tipo di PE chiamato set che, insieme ai complessi, sono anche da considerare. Un insieme è una rappresentazione astratta di un gruppo di due o più entità che non interagiscono tra loro ma sono funzionalmente equivalenti nella situazione in cui viene utilizzato l’insieme, ad esempio più membri di una famiglia di enzimi che potrebbero potenzialmente catalizzare una reazione. Inoltre, complessi e insiemi possono anche contenere altri complessi e insiemi al fine di rappresentare strutture molto più elaborate che causano la complessità del problema a crescere.

Un altro requisito specifico è la possibilità di eseguire la proiezione di specie per raccogliere i risultati per Homo sapiens indipendentemente dalla specie per cui sono forniti gli identificatori, per beneficiare della più completa annotazione del Reactome per l’uomo. Per fare ciò, gli ortologi delle specie annotati in Reactome devono essere presi in considerazione. Gli ortologi sono entità in diverse specie che si sono evolute da un antenato comune per speciazione.

L’ultimo requisito in questo passaggio è quello di tenere traccia degli identificatori mapping tra gli identificatori presentati e quelli utilizzati in Reactome per curare le singole entità: UniProt accessions per le proteine, Ensembl identifier per i geni, CHEBI identificatori per piccole molecole e miRBase per microRNA. Sebbene una parte importante di questa mappatura sia iniziata includendo i riferimenti incrociati noti come identificatori nell’albero delle radix nel passaggio precedente, la mappatura stessa deve essere implementata in questo passaggio.

Riassumendo i requisiti esposti per questa fase dell’analisi, la struttura dati scelta deve modellare il problema di composizione delle entità, la proiezione degli ortologi delle specie e la mappatura delle entità. Un grafico diretto è un grafico o un insieme di nodi collegati da bordi, in cui i bordi hanno una direzione associata a loro. Per un dato grafico G con diversi nodi (a, b, c e d), se G ha una freccia da a a b e un’altra freccia da b a c, allora il grafico composto G 2 ha una freccia da a a c. Se G ha una freccia da a a b, un’altra freccia da b a c e ancora un’altra da c a d, allora il grafico composto G 3 ha una freccia da a a d.

Costruire un grafico per specie (Fig. 2a) e collegandoli tutti collegando tutti i nodi ortolog (Fig. 2b) crea un grafico più grande in cui viene quindi soddisfatto il requisito di proiezione. A causa dell’unicità del nodo nel grafico finale, per quei casi in cui un nodo fa parte di una o più entità strutturate, contiene tanti bordi che puntano ad altri nodi del grafico quante strutture in cui è contenuto, quindi le entità strutturate sono facilmente modellate. Infine, se ogni nodo del grafico contiene l’identificatore principale dell’entità associata (Fig. 2c), quando viene raggiunto da un nodo ad albero radix che rappresenta un identificatore diverso da quello principale, questa associazione viene memorizzata per essere offerta come parte del risultato come mappatura richiesta una volta terminata l’analisi.

Rappresentazione grafica dove P sono proteine; C sono complessi, S sono insiemi e nodi primi sono gli stessi, ma per altre specie. un grafico di una specie. b Relazione tra due specie. c Contenuto nodo base

Il grafico in Fig. 2a mostra tre proteine (P1, P2 e P3), due complessi (C1 e C2) e due set (S1 e S2). Seguendo il bordo da nodo a nodo, S2 potrebbe essere P2 o P3, formalmente rappresentato come . C1 è un complesso che, a causa del suo bordo da S2, è quindi potenzialmente due complessi: {P1, P2} o {P1, P3}, rappresentato come . A seguito di questa decostruzione, S1 è quindi e infine C2 è .

Ad esempio, quando un identificatore corrispondente a P3 viene elaborato e il suo nodo corrispondente nel grafico viene raggiunto dall’albero delle radix, ci vuole un tempo di elaborazione minuscolo per attraversare il grafico e raggiungere i nodi S2, C1, S1 e C2. Allo stesso modo, se la proteina target è P1, i nodi raggiungibili seguendo i bordi del grafico sono C1, S1 e C2. In entrambi gli esempi ogni proteina bersaglio fa parte dei complessi e degli insiemi rappresentati dai nodi attraversati.

L’utilizzo di un grafico migliora il costo dell’algoritmo di analisi e, importante nella creazione di un’analisi in memoria, l’utilizzo della memoria viene mantenuto basso perché non vi è alcuna duplicazione dei dati poiché il nodo per un determinato identificatore principale è in memoria solo una volta. Inoltre, il numero finale di iterazioni del nodo dell’algoritmo è limitato dalle entità correlate per un determinato identificatore, evitando query su una grande quantità di dati e risultati intermedi che si fondono, come fatto nell’approccio basato sul database.

Come per l’albero delle radix descritto sopra, il grafico richiede anche una strategia per consentire all’algoritmo di passare alla fase successiva dell’analisi. In questo caso, ogni nodo grafico che rappresenta un’entità direttamente associata a uno o più percorsi conterrà tanti collegamenti alla seguente struttura dati quante posizioni diverse in cui è presente. Sebbene nella fase di analisi corrente venga trovata ogni entità associata all’identificatore di destinazione, per il risultato finale e il calcolo delle statistiche, esiste ancora un’altra struttura dati da utilizzare, come spiegato nella sottosezione seguente.

Aggregazione dei risultati nell’organizzazione dei percorsi

Ogni PE colpito direttamente o indirettamente nel passaggio precedente è associato a uno o più percorsi. Per calcolare il significato di ogni percorso, per un determinato campione utente, è essenziale determinare il numero di entità trovate per percorso. A causa dell’organizzazione genitore-figlio dei percorsi del Reattoma in una gerarchia simile all’ontologia, quando un’entità è presente in un determinato percorso è presente anche nei suoi super-percorsi in modo ricorsivo fino a raggiungere un percorso di livello superiore (cioè se una proteina è presente nel “Metabolismo dei carboidrati”, è presente anche nel”Metabolismo”).

Tenendo conto dei requisiti precedentemente discussi, una buona struttura dati per modellare questo passaggio è un albero a doppio collegamento, in cui ogni nodo rappresenta un percorso e contiene collegamenti ai suoi genitori e figli (Fig. 3). Quando viene colpito un nodo nell’albero, l’azione può essere propagata ricorsivamente fino alla radice. Per ridurre l’ingombro di memoria in ogni nodo vengono conservati solo identificatori, nomi e segnaposto per il calcolo dei risultati.

Albero a doppio collegamento per rappresentare la gerarchia degli eventi in Reactome. Il nodo radice definisce la specie e i suoi figli rappresentano i diversi percorsi e sotto-percorsi in Reactome. Ogni nodo contiene il sentiero identificativo, il nome, il totale a cura entità e il numero di entità trovato nel manuale utente di esempio

Oltre ad essere una comoda struttura di dati per accelerare la raccolta dei risultati e un buon supporto per i risultati delle statistiche, una volta che l’analisi è finita, questa struttura di dati può anche essere pubblicati in un file di mantenere il risultato. Inoltre, l’associazione del file a un token fornisce un modo semplice per creare metodi a grana fine che consentono di filtrare il risultato sul lato server per accelerare i client leggeri. In questo scenario, i client possono mantenere il token una volta terminata l’analisi iniziale e, a seconda delle esigenze dell’utente, eseguire diverse richieste al server facendo riferimento al token associato.

Calcolo delle statistiche dei risultati dell’analisi

L’ipotesi di base in un’analisi di sovrarappresentazione è che i percorsi rilevanti possono essere rilevati se la proporzione di geni espressi in modo differenziale, all’interno di un determinato percorso, supera la proporzione di geni che potrebbero essere attesi in modo casuale . Di conseguenza, il quarto e ultimo passo del metodo di analisi comporta il calcolo delle statistiche. Questo passaggio non richiede alcuna struttura dati aggiuntiva perché l’albero a doppio collegamento si adatta perfettamente allo scopo.

Il valore p mostra la significatività statistica di ogni percorso hit per un dato campione e lo sfondo per il quale è stata eseguita l’analisi. In Reactome il metodo utilizzato per calcolare la significatività statistica è il test binomiale. Insieme al valore p, il False Discovery Rate (FDR) aiuta a stimare i falsi positivi e viene calcolato utilizzando l’approccio Benjamini-Hochberg . Come accennato in precedenza, ci siamo concentrati sull’ottimizzazione delle prestazioni dell’analisi del percorso Reactome, mantenendo l’algoritmo di base come precedentemente pubblicato .