identifikation af en praktisk datastruktur til løsning af et givet problem er en af de vigtigste faktorer for at opnå et højtydende slutprodukt. Som Skiena forklarer i, at vælge den forkerte datastruktur til jobbet kan være katastrofalt med hensyn til ydeevne, men at identificere den allerbedste datastruktur er normalt ikke så kritisk, fordi der kan være flere valg, der fungerer på samme måde.

baseret på delings-og erobringsreglen er det første trin at nedbryde analyseproblemet i forskellige underproblemer, der er enkle nok til at blive løst i polynomisk tid ved at identificere en praktisk datastruktur. Her kan analysealgoritmen opdeles i fire dele: (1) Kontrol af, om brugerens protein/kemiske identifikatorer er til stede i Reaktom, (2) for de nuværende, at finde ud af, om disse er dele af komplekser og/eller sæt samt artsprojektionen, (3) aggregering af de fundne identifikatorer i de veje (og superveje), hvor disse er til stede, og endelig (4) udførelse af den statistiske test for at beregne sandsynligheden for, at sammenhængen mellem prøveidentifikatorerne og den fundne vej skyldes tilfældig chance.

yderligere i dette afsnit diskuteres hver del detaljeret for at bestemme dens særegenheder; at afsløre den valgte datastruktur og de mekanismer, der er vedtaget for dens forbedring; og for at vise, hvordan man forbinder hvert trin til det følgende for at komme med den endelige forbedrede analysealgoritme. Et andet punkt for optimering vil være hukommelsesforbruget for hvert trin, så de udfyldte datastrukturer kan opbevares i hukommelsen for at forbedre ydeevnen for de datakrydsningsalgoritmer, der implementeres oven på dem.

Brugereksempelidentifikatorer Søg i Reactome

annoterede fysiske enheder (PE) i Reactome kan enten være enkeltenheder eller komplekser. Enkelte enheder inkluderer proteiner, små molekyler, RNA, DNA, kulhydrater eller lipider, mens komplekser består af en kombination af en hvilken som helst af de enkelte enheder eller polymerer syntetiseret fra de enkelte enheder. Bortset fra disse to hovedkategorier kan kuratorer i Reactome imidlertid gruppere relaterede enheder i sæt. PEs er de byggesten, der senere vil blive brugt som input, output, katalysatorer eller regulatorer i reaktioner.

identifikatorer eller tiltrædelsesnumre bruges til utvetydigt at henvise til en enkelt enhed, men PEs har forskellige slots til at indeholde hovedidentifikatoren, sekundær identifikator, krydsreferencer, synonymer og andre identifikatorer. Hovedidentifikatorspalten kommenteres altid manuelt af eksperterne, der kuraterer data i Reactome (kuratorer), og de andre slots kan enten udfyldes manuelt under kuration eller automatisk udfyldes under frigivelsesprocessen. Denne strategi gør det muligt at gemme identifikatorer til en bred vifte af ressourcer: Det er en af de mest almindelige årsager til, at der ikke er nogen tvivl om, at der ikke er nogen tvivl om, at der ikke er nogen tvivl om, at der ikke er nogen tvivl om, at der ikke er nogen tvivl om, at der ikke er nogen tvivl om, at der ikke er nogen tvivl om, at der ikke er nogen tvivl om, at der ikke er nogen tvivl om, at der ikke er nogen tvivl om, at der ikke er nogen tvivl om, at der ikke er nogen tvivl om, at der ikke er nogen tvivl om, at der ikke er nogen tvivl om, at der ikke er nogen tvivl om, at der ikke er nogen tvivl.

derfor er hovedkravet i den første del af analysen at forbedre processen med at finde ud af, om hver identifikator i brugerens prøve svarer til en eller mange PEs i Reactome. En identifikator svarer til en PE, hvis den matcher nogen af de identifikatorer, der er gemt i de forskellige slots, der er nævnt ovenfor. Faktisk er den bedste måde at løse dette problem på ved at følge den omvendte tilgang; oprettelse af en opslagstabel med alle de tilsvarende PEs pr. Som en konsekvens er et andet vigtigt krav at minimere hukommelsesforbruget, så dataene kan opbevares i hukommelsen for at forbedre forespørgselstiden.

valget af en god datastruktur bestemmes derefter af krav både for at implementere en hurtig opslagstabel og for at holde hukommelsesforbruget lavt. En Trie er en ordnet trædatastruktur, der bruges til at gemme et dynamisk sæt eller associativt array, hvor tasterne normalt er strenge . Et træ er en rumoptimeret Trie – datastruktur, hvor hver node med kun et barn fusioneres med sin forælder .

på den ene side har et Radik-træ relativt lavt hukommelsesforbrug til opslagstabellen, fordi de almindelige præfikser deles og undgår dataduplikation (Fig. 1). På den anden side kan omkostningerne ved at sammenligne en søgenøgle for lighed med en nøgle fra datastrukturen være en dominerende pris, som ikke kan overses. Algoritmen til opslag af trestreng passer til analysealgoritmens oprindelige formål, fordi iterering over trænoder holder identifikatoren, der søger tid, begrænset til hver identifikators længde og eksistens i Reactome-målsættet. Som en konsekvens af dette, hvis den søgte identifikator ikke er indeholdt i datastrukturen, er der ikke behov for at læse det hele, som det sker i hashingmetoderne, hvor hashværdien af strengen skal beregnes i alle tilfælde ved at læse den helt.

Trærepræsentation for identifikatorerne P60484, P60467, P60468, P29172, P11087, P11086, P10639, P10636, P10635, p10622, p10620, p12939, p12938, p12931, p05480, p05386, PTEN

pes angiver, om den tilknyttede identifikator er til stede eller ej i databasen. Faktisk er de nævnte” referencer til PE ” faktisk henvisninger til noder i datastrukturen valgt til næste del af analysen.

Reactome bruger unikke primære identifikatorer til PEs it-referencerne, især UniProt for proteiner og ChEBI for kemiske enheder. Således, hvis brugere sender datasæt ved hjælp af disse referencesystemer, er kortlægningen til PEs ligetil. Imidlertid, efter hyppige brugeranmodninger, vi accepterer også inputdata med ikke-unikke identifikatorer, især gennavne. Disse kortlægges derefter potentielt til flere PEs. Således kan hver målknude i træet indeholde mere end en markør til den næste datastruktur.

krydsning af komplekser/sæt sammensætning og artsprojektion

at nå den tilknyttede enkelt enhed for en given identifikator er begyndelsen på det andet trin i analysen. Når disse enkelte enheder er en del af et kompleks, er de også et mål i dette trin i analysen. Udover de enkelte enheder og komplekser er der en anden type PE kaldet Sæt, som sammen med komplekser også skal overvejes. Et sæt er en abstrakt repræsentation af en gruppe på to eller flere enheder, der ikke interagerer med hinanden, men er funktionelt ækvivalente i den situation, hvor sættet bruges, for eksempel flere medlemmer af en familie af tegn, der hver potentielt kan katalysere en reaktion. Desuden kan komplekser og sæt også indeholde andre komplekser og sæt for at repræsentere meget mere detaljerede strukturer, der får problemets intricacy til at vokse.

et andet specifikt krav er muligheden for at udføre artsprojektion for at indsamle resultaterne for Homo sapiens uafhængigt af den art, som identifikatorerne leveres til, for at drage fordel af den mere komplette Reactome-annotation for mennesker. For at gøre dette skal artsortologerne, der er kommenteret i Reactome, tages i betragtning. Ortologer er enheder i forskellige arter, der udviklede sig fra en fælles forfader ved speciering.

det sidste krav i dette trin er at holde styr på identifikatorerne kortlægning mellem de indsendte identifikatorer og dem, der anvendes i Reactome til at kuratere de enkelte enheder: UniProt-tiltrædelser for proteiner, Ensembl-identifikator for gener, CHEBI-identifikatorer for små molekyler og miRBase for mikroRNA ‘ er. Selvom en vigtig del af denne kortlægning startede med at inkludere de kendte krydsreferencer som identifikatorer i det foregående trin, selve kortlægningen skal implementeres i dette trin.

sammenfatning af de eksponerede krav til dette trin i analysen skal den valgte datastruktur modellere enhedernes sammensætningsproblem, artsortologernes projektion og enhedernes kortlægning. En rettet graf er en graf eller et sæt noder forbundet med kanter, hvor kanterne har en retning forbundet med dem. For en given graf G med flere noder (A, b, c og d), hvis G har en pil fra A til b og en anden pil fra b til c, så har den sammensatte graf G 2 en pil fra A til c. Hvis G har en pil fra A til b, en anden pil fra b til c og endnu en fra c til d, så har den sammensatte graf G 3 en pil fra A til d.

opbygning af en graf pr.Art (Fig. 2a) og sammenkobling af dem alle, der forbinder alle ortologknudepunkterne (Fig. 2b) opretter en større graf, hvor projektionskravet derefter opfyldes. På grund af nodens unikke karakter i den endelige graf, for de tilfælde, hvor en knude er en del af en eller flere strukturerede enheder, indeholder den så mange kanter, der peger på andre grafnoder som strukturer, hvori den er indeholdt, så strukturerede enheder Let modelleres. Endelig, hvis hver knude i grafen indeholder dens tilknyttede enhed hovedidentifikator (Fig. 2c), når den nås fra en Radik-træknude, der repræsenterer en anden identifikator end den vigtigste, gemmes denne tilknytning for at blive tilbudt som en del af resultatet som den krævede kortlægning, når analysen er afsluttet.

Grafrepræsentation, hvor P er proteiner; C er komplekser, S er sæt og prime noder er de samme, men for andre arter. en art graf. B forholdet mellem to arter. C Base node indhold

grafen i Fig. 2a viser tre proteiner (P1, P2 og P3), to komplekser (C1 og C2) og to sæt (S1 og S2). Ved at følge kanten fra node til node kunne S2 være enten P2 eller P3, formelt repræsenteret som . C1 er et kompleks, der på grund af dets kant fra S2 derefter potentielt er to komplekser: {P1,P2} eller {P1,P3}, repræsenteret som . Efter denne dekonstruktion er S1 derefter og endelig C2 er .

for eksempel, når en identifikator, der matcher med P3, behandles, og dens tilsvarende node i grafen nås fra radiktræet, tager det minimal behandlingstid at krydse grafen og nå knudepunkterne S2, C1, S1 og C2. Ligeledes, hvis målproteinet er P1, er de tilgængelige noder, der følger grafkanterne, C1, S1 og C2. I begge eksempler er hvert målprotein en del af komplekserne og sætene repræsenteret af de krydsede knuder.

anvendelse af en graf forbedrer analysealgoritmeomkostningerne, og vigtigt ved opbygning af en analyse i hukommelsen holdes hukommelsesforbruget lavt, fordi der ikke er nogen dataduplikation, da noden for en given hovedidentifikator kun er i hukommelsen en gang. Derudover er det endelige antal node-iterationer af algoritmen begrænset af de relaterede enheder for en given identifikator, hvilket undgår forespørgsler mod en stor mængde data og mellemresultater, der smelter sammen, som det gøres i den databasebaserede tilgang.

hvad angår radiktræet beskrevet ovenfor, kræver grafen også en strategi for at give algoritmen mulighed for at gå videre til det næste analysetrin. I dette tilfælde vil hver grafnode, der repræsenterer en enhed, der er direkte tilknyttet en eller flere veje, indeholde lige så mange links til følgende datastruktur som forskellige steder, hvor den er til stede. Selvom der i det aktuelle analysetrin findes hver enhed, der er knyttet til målidentifikatoren, er der for det endelige resultat og statistikberegningen stadig en datastruktur, der skal bruges, som forklaret i det følgende underafsnit.

resultater aggregering i stierne organisation

hver PE, der blev direkte eller indirekte ramt i det foregående trin, er forbundet med en eller flere veje. For at beregne betydningen af hver vej for en given brugerprøve er det vigtigt at bestemme antallet af enheder, der findes pr. På grund af forældre-barn-organisationen af Reaktomveje i et ontologilignende hierarki, når en enhed er til stede i en bestemt vej, er den også til stede i dens superveje på en rekursiv måde, indtil en topniveau-vej er nået (dvs. hvis et protein er til stede i” metabolisme af kulhydrater”, er det også til stede i”metabolisme”).

under hensyntagen til de tidligere diskuterede krav er en god datastruktur til at modellere dette trin et dobbeltbundet træ, hvor hver knude repræsenterer en sti og indeholder links til dens forælder og børn (Fig. 3). Når en knude i træet er ramt, kan handlingen rekursivt formeres helt op til roden. For at reducere hukommelsesfodaftrykket opbevares kun identifikatorer, navne og pladsholdere til beregning af resultater i hver node.

Dobbeltlinket træ for at repræsentere hændelseshierarkiet i Reactome. Rodknuden definerer arten, og dens børn repræsenterer de forskellige veje og underveje i Reactome. Hver node indeholder vejidentifikatoren, navnet, de samlede kuraterede enheder og antallet af enheder, der findes i brugerens prøve

bortset fra at være en bekvem datastruktur til at fremskynde indsamlingen af resultater og en god holder til statistikresultaterne, når analysen er afsluttet, kan denne datastruktur også serialiseres til en fil for at fortsætte resultatet. Derudover giver tilknytning af filen til et token en nem måde at oprette finere kornede metoder, der tillader filtrering af resultatet på serversiden for at hjælpe med at fremskynde lette klienter. I dette scenarie kan klienterne beholde tokenet, når den indledende analyse er afsluttet, og afhængigt af brugerens behov, udføre flere anmodninger til serveren, der henviser til det tilknyttede token.

analyse resultat statistik beregning

den grundlæggende hypotese i en overrepræsentationsanalyse er, at relevante veje kan detekteres, hvis andelen af differentielt udtrykte gener inden for en given vej overstiger andelen af gener, der tilfældigt kunne forventes . Derfor involverer det fjerde og sidste trin i analysemetoden statistikberegningen. Dette trin kræver ingen ekstra datastruktur, fordi det dobbeltbundne træ passer perfekt til formålet.

p-værdien viser den statistiske signifikans af hver hitvej for en given prøve og baggrunden for hvilken analysen er udført. I Reactome er den metode, der bruges til at beregne den statistiske signifikans Binomial Test. Sammen med p-værdien hjælper False Discovery Rate (FDR) med at estimere de falske positiver, og den beregnes ved hjælp af Benjamini-Hochberg-metoden . Som nævnt ovenfor har vi fokuseret på at optimere ydeevnen for Reaktomvejsanalysen, samtidig med at den grundlæggende algoritme opretholdes som tidligere offentliggjort .