identificarea unei structuri de date convenabile pentru a rezolva o problemă dată este unul dintre principalii factori pentru a obține un produs final de înaltă performanță. După cum explică Skiena în , alegerea structurii de date greșit pentru locuri de muncă poate fi dezastruoasă în termeni de performanță, dar identificarea cea mai bună structură de date nu este, de obicei, la fel de critică, deoarece pot exista mai multe opțiuni care funcționează în mod similar.

bazat pe regula divide and conquer, primul pas este descompunerea problemei de analiză în diferite sub-probleme suficient de simple pentru a fi rezolvate în timp polinomial prin identificarea unei structuri de date convenabile. Aici, algoritmul de analiză poate fi împărțit în patru părți: (1) verificarea dacă identificatorii proteici/chimici ai utilizatorului sunt prezenți în Reactom, (2) pentru cei prezenți, constatarea dacă acestea sunt părți ale complexelor și/sau seturilor, precum și proiecția speciilor, (3) agregarea identificatorilor găsiți în căile (și super-căile) în care acestea sunt prezente și, în final, (4) efectuarea testelor statistice pentru a calcula probabilitatea ca asocierea dintre identificatorii eșantionului și calea Găsită să se datoreze întâmplării aleatorii.

Mai departe în această secțiune fiecare parte este discutată în detaliu pentru a determina particularitățile sale; pentru a expune structura de date aleasă și mecanismele adoptate pentru îmbunătățirea acesteia; și pentru a arăta cum să conectați fiecare pas la următorul pentru a veni cu algoritmul final de analiză îmbunătățit. Un alt punct de accent pentru optimizare va fi utilizarea memoriei fiecărui pas, astfel încât structurile de date completate să poată fi păstrate în memorie pentru a îmbunătăți performanța algoritmilor de traversare a datelor implementați deasupra acestora.

user sample identifiers căutare în Reactome

entitățile fizice adnotate (PE) în Reactome pot fi fie entități unice, fie complexe. Entitățile unice includ proteine, molecule mici, ARN, ADN, carbohidrați sau lipide, în timp ce complexele constau dintr-o combinație a oricăreia dintre entitățile unice sau polimeri sintetizați din entitățile unice. Cu toate acestea, în afară de aceste două categorii principale, curatorii din Reactome pot grupa entitățile conexe în seturi. PEs sunt elementele de bază care ulterior vor fi utilizate ca intrări, ieșiri, catalizatori sau regulatori în reacții.

identificatorii sau numerele de aderare sunt utilizate pentru a se referi fără echivoc la o singură entitate, dar SPO au sloturi diferite pentru a deține identificatorul principal, identificatorul secundar, referințele încrucișate, sinonimele și alți identificatori. Slotul principal de identificare este întotdeauna adnotat manual de experții care curăță datele în Reactome (curatori), iar celelalte sloturi pot fi completate manual în timpul curățării sau populate automat în timpul procesului de eliberare. Această strategie permite stocarea identificatorilor pentru o gamă largă de resurse: Uniprot, ChEBI, Ensembl, miRBase, GenBank/EMBL/DDBJ, RefPep, RefSeq, EntrezGene, OMIM, InterPro, Affymetrix, Agilent, compus KEGG, Illumina, etc.

prin urmare, în prima parte a analizei, cerința principală este de a îmbunătăți procesul de a afla dacă fiecare identificator din eșantionul utilizatorului corespunde unuia sau mai multor PEs în Reactom. Un identificator corespunde unui PE dacă se potrivește cu oricare dintre identificatorii stocați în diferitele sloturi menționate mai sus. De fapt, cel mai bun mod de a rezolva această problemă este urmând abordarea inversă; crearea unui tabel de căutare cu toate PEs corespunzătoare pentru fiecare identificator de referință încrucișată în Reactome. În consecință, o altă cerință importantă este de a minimiza utilizarea memoriei, astfel încât datele să poată fi păstrate în memorie pentru a îmbunătăți timpul de interogare.

selectarea unei structuri de date bune este apoi determinată de cerințele atât pentru a implementa un tabel de căutare rapidă, cât și pentru a menține utilizarea memoriei scăzută. Un Trie este o structură ordonată de date arbore care este utilizată pentru a stoca un set dinamic sau o matrice asociativă în care tastele sunt de obicei șiruri . Un arbore radix este o structură de date Trie optimizată în spațiu în care fiecare nod cu un singur copil este fuzionat cu părintele său .

Pe de o parte, un arbore radix are o utilizare relativ scăzută a memoriei pentru tabelul de căutare, deoarece prefixele comune sunt partajate evitând duplicarea datelor (Fig. 1). Pe de altă parte, costul comparării unei chei de căutare pentru egalitate cu o cheie din structura datelor poate fi un cost dominant care nu poate fi neglijat. Algoritmul de căutare a șirurilor de arbori radix se potrivește scopului inițial al algoritmului de analiză, deoarece iterarea peste nodurile arborelui menține timpul de căutare a identificatorului limitat la lungimea și existența fiecărui identificator în setul țintă Reactome. Ca o consecință a acestui fapt, în cazul în care identificatorul căutat nu este conținut în structura de date, nu este nevoie să citiți totul așa cum se întâmplă în metodele de hashing în care valoarea hash a șirului trebuie calculată în fiecare caz citind-o în întregime.

reprezentarea arborelui Radix pentru identificatorii P60484, P60467, P60468, P29172, P11087, P11086, P10639, P10636, P10635, p10622, p10620, p12939, p12938, p12931, p05480, p05386, PTEN

În rezumat, odată ce un nod arbore este atins în urma algoritmului de căutare copac Radix pentru un identificator dat, prezența sau absența referințelor la pes indică dacă identificatorul asociat este prezent sau nu în baza de date. De fapt, „referințele menționate la PE” sunt într-adevăr indicii către noduri din structura de date aleasă pentru următoarea parte a analizei.Reactome utilizează identificatori primari unici pentru referințele it ale SPOFM, în special UniProt pentru proteine și ChEBI pentru entitățile chimice. Astfel, dacă utilizatorii trimit seturi de date folosind aceste sisteme de referință, maparea la PEs este simplă. Cu toate acestea, în urma solicitărilor frecvente ale utilizatorilor, acceptăm și date de intrare cu identificatori non-unici, în special nume de gene. Acestea sunt apoi potențial mapate la mai multe PEs. Astfel, fiecare nod țintă din arbore ar putea conține mai mult de un pointer la următoarea structură de date.

compoziția complexelor/seturilor de traversare și proiecția speciilor

atingerea entității unice asociate pentru un identificator dat este începutul celei de-a doua etape a analizei. Atunci când aceste entități unice fac parte dintr-un complex, ele sunt, de asemenea, o țintă în această etapă a analizei. Pe lângă entitățile și complexele unice, există un alt tip de pe numit seturi care, împreună cu complexele, trebuie luate în considerare și ele. O mulțime este o reprezentare abstractă a unui grup de două sau mai multe entități care nu interacționează între ele, dar sunt echivalente din punct de vedere funcțional în situația în care este utilizat setul, de exemplu mai mulți membri ai unei familii de enzime care ar putea cataliza fiecare o reacție. Mai mult, complexele și seturile pot conține și alte complexe și seturi pentru a reprezenta structuri mult mai elaborate care determină creșterea complexității problemei.

o altă cerință specifică este posibilitatea de a efectua proiecția speciilor pentru a colecta rezultatele pentru Homo sapiens independent de specia pentru care sunt furnizați identificatorii, pentru a beneficia de adnotarea Reactomului mai completă pentru om. Pentru a face acest lucru, trebuie luate în considerare ortologii speciilor adnotați în Reactom. Ortologii sunt entități din diferite specii care au evoluat dintr-un strămoș comun prin speciație.

ultima cerință din această etapă este de a urmări cartografierea identificatorilor între identificatorii prezentați și cei utilizați în Reactome pentru a curăța entitățile unice: aderări UniProt pentru proteine, identificator Ensembl pentru gene, identificatori CHEBI pentru molecule mici și miRBase pentru microARN. Deși o parte importantă a acestei mapări a început prin includerea referințelor încrucișate cunoscute ca identificatori în arborele radix în etapa anterioară, maparea în sine trebuie implementată în această etapă.

rezumând cerințele expuse pentru această etapă a analizei, structura de date aleasă trebuie să modeleze problema compoziției entităților, proiecția ortologilor speciilor și cartografierea entităților. Un grafic direcționat este un grafic sau un set de noduri conectate prin margini, unde marginile au o direcție asociată cu ele. Pentru un grafic dat G cu mai multe noduri (A, b, c și d), Dacă G are o săgeată de la A la b și o altă săgeată de la b la c, atunci graficul compus G 2 are o săgeată de la A la c. Dacă G are o săgeată de la A la b, o altă săgeată de la b la c și încă una de la c la d, atunci graficul compus G 3 are o săgeată de la A la d.

construind un grafic pe specie (Fig. 2a) și interconectarea tuturor nodurilor ortholog (Fig. 2b) creează un grafic mai mare în cazul în care cerința de proiecție este apoi îndeplinită. Datorită unicității nodului din graficul final, pentru acele cazuri în care un nod face parte dintr-una sau mai multe entități structurate, acesta conține tot atâtea muchii care indică alte noduri de grafic ca structuri în care este conținut, astfel încât entitățile structurate sunt ușor modelate. În cele din urmă, dacă fiecare nod al graficului conține identificatorul principal al entității asociate (Fig. 2c), când se ajunge de la un nod arbore radix reprezentând un alt identificator decât cel principal, această asociere este stocată pentru a fi oferită ca parte a rezultatului ca mapare necesară odată ce analiza este terminată.

reprezentarea grafurilor unde P sunt proteine; C sunt complexe, s sunt seturi și nodurile prime sunt aceleași, dar pentru alte specii. un grafic cu o singură specie. B relația dintre două specii. conținutul nodului de bază c

graficul din Fig. 2a prezintă trei proteine (P1, P2 și P3), două complexe (C1 și C2) și două seturi (s1 și s2). Urmând marginea de la nod la nod, S2 ar putea fi fie P2, fie P3, reprezentat formal ca . C1 este un complex care, datorită marginii sale de la S2,este apoi potențial două complexe: {P1,P2} sau {P1, P3}, reprezentat ca . În urma acestei deconstrucții, S1 este atunci și în cele din urmă C2 este .

de exemplu, atunci când un identificator care se potrivește cu P3 este procesat și nodul său corespunzător din grafic este atins din arborele radix, este nevoie de un timp de procesare minuscul pentru a traversa Graficul și a ajunge la nodurile s2, C1, s1 și C2. La fel, dacă proteina țintă este P1, nodurile accesibile care urmează marginile graficului sunt C1, s1 și C2. În ambele exemple, fiecare proteină țintă face parte din complexele și seturile reprezentate de nodurile traversate.

utilizarea unui grafic îmbunătățește costul algoritmului de analiză și, important în construirea unei analize în memorie, utilizarea memoriei este menținută scăzută, deoarece nu există duplicare a datelor, deoarece nodul pentru un identificator principal dat este doar în memorie o singură dată. În plus, numărul final de iterații de noduri ale algoritmului este limitat de entitățile conexe pentru un identificator dat, evitând interogările împotriva unei cantități mari de date și rezultate intermediare care fuzionează, așa cum se face în abordarea bazată pe baza de date.

în ceea ce privește arborele radix descris mai sus, graficul necesită, de asemenea, o strategie pentru a permite algoritmului să treacă la următorul pas de analiză. În acest caz, fiecare nod grafic reprezentând o entitate asociată direct la una sau mai multe căi va conține cât mai multe legături către următoarea structură de date ca locații diferite în care este prezentă. Deși în etapa actuală de analiză se găsește fiecare entitate asociată cu identificatorul țintă, pentru rezultatul final și calculul statisticilor, mai există încă o structură de date care trebuie utilizată, așa cum se explică în subsecțiunea următoare.

agregarea rezultatelor în organizarea căilor

fiecare EP care a fost lovit direct sau indirect în etapa anterioară este asociat cu una sau mai multe căi. Pentru a calcula semnificația fiecărei căi, pentru un eșantion de utilizator dat, este esențial să se determine numărul de entități găsite pe cale. Datorită organizării părinte-copil a căilor Reactome într-o ierarhie asemănătoare ontologiei, atunci când o entitate este prezentă într-o anumită cale, este prezentă și în super-căile sale într-un mod recursiv până când se atinge o cale de nivel superior (adică. dacă o proteină este prezentă în” metabolismul carbohidraților”, este prezentă și în”Metabolism”).

luând în considerare cerințele discutate anterior, o structură de date bună pentru a modela acest pas este un arbore dublu legat, în care fiecare nod reprezintă o cale și conține legături către părintele și copiii săi (Fig. 3). Când un nod din copac este lovit, acțiunea poate fi propagată recursiv până la rădăcină. Pentru a reduce amprenta de memorie numai identificatori, nume și substituenți pentru calculul rezultatelor sunt păstrate în fiecare nod.

arbore dublu legat pentru a reprezenta ierarhia evenimentelor în Reactom. Nodul rădăcină definește specia și copiii săi reprezintă diferitele căi și sub-căi în Reactom. Fiecare nod conține identificatorul căii, numele, numărul total de entități curate și numărul de entități găsite în eșantionul utilizatorului

În afară de a fi o structură de date convenabilă pentru a accelera colectarea rezultatelor și un bun suport pentru rezultatele statisticilor, odată ce analiza este terminată, această structură de date poate fi, de asemenea, serializată într-un fișier pentru a persista rezultatul. În plus, asocierea fișierului la un jeton oferă o modalitate ușoară de a crea metode cu granulație mai fină care permit filtrarea rezultatului pe partea serverului pentru a ajuta la accelerarea clienților cu greutate redusă. În acest scenariu, clienții pot păstra tokenul odată ce analiza inițială este terminată și, în funcție de nevoile utilizatorului, pot efectua mai multe solicitări către server care fac referire la tokenul asociat.

calculul statisticilor rezultatelor analizei

ipoteza de bază într-o analiză supra-reprezentare este că căile relevante pot fi detectate dacă proporția de gene exprimate diferențiat, într-o cale dată, depășește proporția de gene care ar putea fi așteptate aleatoriu . În consecință, al patrulea și ultimul pas al metodei de analiză implică calculul statisticilor. Acest pas nu necesită nicio structură suplimentară de date, deoarece arborele dublu legat se potrivește perfect scopului.

valoarea p arată semnificația statistică a fiecărei căi hit pentru un eșantion dat și fundalul pentru care a fost efectuată analiza. În Reactome metoda utilizată pentru a calcula semnificația statistică este testul Binomial. Împreună cu valoarea p, rata de descoperire falsă (FDR) ajută la estimarea falselor pozitive și se calculează folosind abordarea Benjamin-Hochberg . După cum sa menționat mai sus, ne-am concentrat pe optimizarea performanței analizei căii Reactome, menținând în același timp algoritmul de bază așa cum a fost publicat anterior .