Reactome pathway analysis: a high-performance in-memory approach
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.
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.