Å Identifisere en praktisk datastruktur for å løse et gitt problem Er en av hovedfaktorene for å oppnå et sluttprodukt med høy ytelse. Som Skiena forklarer i, kan det være katastrofalt å velge feil datastruktur for jobben når det gjelder ytelse, men å identifisere den aller beste datastrukturen er vanligvis ikke så kritisk, fordi det kan være flere valg som fungerer på samme måte.Basert på splitt og hersk-regelen, er det første trinnet å bryte ned analyseproblemet i forskjellige delproblemer som er enkle nok til å løses i polynomisk tid ved å identifisere en praktisk datastruktur. Her kan analysealgoritmen deles inn i fire deler: (1) kontrollere om brukerens protein / kjemiske identifikatorer er tilstede I Reaktom, (2) for de nåværende, finne ut om disse er deler av komplekser og / eller sett, samt artsprojeksjonen, (3) aggregere de funnet identifikatorene i banene (og superbanene) der disse er til stede og til slutt (4) utføre statistisk testing for å beregne sannsynligheten for at sammenhengen mellom prøveidentifikatorene og den funnet banen skyldes tilfeldig sjanse.

Videre i denne delen diskuteres hver del i detalj for å bestemme dens særegenheter; å avsløre den valgte datastrukturen og mekanismene som er vedtatt for forbedring; og å vise hvordan du kobler hvert trinn til det følgende for å komme opp med den endelige forbedrede analysealgoritmen. Et annet fokuspunkt for optimalisering vil være minnebruken til hvert trinn, slik at de fylte datastrukturene kan holdes i minnet for å forbedre ytelsen til dataoverføringsalgoritmer implementert på toppen av dem.

brukerprøveidentifikatorer søk I Reactome

Annoterte fysiske enheter (PE) I Reactome kan enten være enkeltenheter eller komplekser. Enkeltenheter inkluderer proteiner, små molekyler, RNA, DNA, karbohydrater eller lipider, mens komplekser består av en kombinasjon av noen av de enkelte enhetene eller polymerer syntetisert fra de enkelte enhetene. Bortsett fra disse to hovedkategoriene kan kuratorer i Reactome gruppere relaterte enheter i sett. PEs er byggesteinene som senere vil bli brukt som innganger, utganger, katalysatorer eller regulatorer i reaksjoner.

Identifikatorer eller tiltredelsesnumre brukes til å utvetydig referere til en enkelt enhet, Men PEs har forskjellige spor for å holde hovedidentifikatoren, sekundæridentifikatoren, kryssreferanser, synonymer og andre identifikatorer. Hovedidentifikatorsporet er alltid manuelt annotert av eksperter som kuraterer data I Reactome (kuratorer), og de andre sporene kan enten fylles manuelt under kurering eller fylles automatisk under utgivelsesprosessen. Denne strategien tillater lagring av identifikatorer for et bredt spekter av ressurser: UniProt, Chebi, Ensembl, miRBase, GenBank/EMBL/DDBJ, RefPep, RefSeq, EntrezGene, Omim, InterPro, Affymetrix, Agilent, Kegg Sammensatte, Illumina, etc.

derfor er hovedkravet i første del av analysen å forbedre prosessen med å finne ut om hver identifikator i brukerens prøve tilsvarer en Eller mange PEs I Reaktom. En identifikator tilsvarer EN PE hvis den samsvarer med noen av identifikatorene som er lagret i de forskjellige sporene som er nevnt tidligere. Faktisk er den beste måten å løse dette problemet på, ved å følge omvendt tilnærming; opprette en oppslagstabell med alle de tilsvarende PEs per hver identifikator kryssreferert I Reactome. Som en konsekvens er et annet viktig krav å minimere minnebruken, slik at dataene kan holdes i minnet for å forbedre spørringstiden.valget av en god datastruktur bestemmes da av krav både for å implementere en rask oppslagstabell og for å holde minnebruken lav. En Trie er en ordnet tre datastruktur som brukes til å lagre et dynamisk sett eller assosiativ matrise der tastene er vanligvis strenger . Et radix-tre er en Plassoptimalisert Trie-datastruktur hvor hver node med bare ett barn slås sammen med sin forelder .

på den ene siden har et radix-tre relativt lite minnebruk for oppslagstabellen fordi de vanlige prefiksene deles, og unngår dataduplikasjon(Fig . 1). På den annen side kan kostnaden ved å sammenligne en søkenøkkel for likestilling med en nøkkel fra datastrukturen være en dominerende kostnad som ikke kan overses. Den radix tre streng oppslag algoritme passer analyse algoritmen opprinnelige formål fordi iterating over tre noder holder identifikator søker tid begrenset til hver identifikator lengde og eksistens I reaktom målet sett. Som en konsekvens av dette, hvis den søkte identifikatoren ikke finnes i datastrukturen, er det ikke nødvendig å lese alt som skjer i hashing-metodene der hash-verdien av strengen må beregnes i hvert tilfelle ved å lese den helt.

radixtrerepresentasjon for identifikatorene P60484, P60467, P60468, P29172, P11087, P11086, P10639, P10636, P10635, p10622, p10620, p12939, p12938, p12931, p05480, p05386, pten

pes angir om den tilknyttede identifikatoren er til stede eller ikke i databasen. Faktisk er de nevnte «referansene TIL PE» faktisk pekere til noder i datastrukturen valgt for neste del av analysen.

Reactome bruker unike primære identifikatorer For pes it referanser, spesielt UniProt for proteiner og ChEBI for kjemiske enheter. Således, hvis brukere sender datasett ved hjelp av disse referansesystemene, er kartleggingen til PEs grei. Etter hyppige brukerforespørsler godtar vi imidlertid også inndata med ikke-unike identifikatorer, spesielt gennavn. Disse blir deretter potensielt kartlagt til flere PEs. Dermed kan hver målnode i treet inneholde mer enn en peker til neste datastruktur.

Traversering komplekser / sett sammensetning og arter projeksjon

Å Nå den tilknyttede enkelt enhet for en gitt identifikator er begynnelsen av det andre trinnet i analysen. Når disse enkeltenhetene er en del av et kompleks, er de også et mål i dette trinnet i analysen. Foruten de enkelte enhetene og kompleksene er det en ANNEN TYPE PE kalt sett som sammen med komplekser også skal vurderes. Et sett er en abstrakt representasjon av en gruppe av to eller flere enheter som ikke interagerer med hverandre, men er funksjonelt ekvivalente i situasjonen der settet brukes, for eksempel flere medlemmer av en familie av enzymer som hver potensielt kan katalysere en reaksjon. Videre kan komplekser og sett også inneholde andre komplekser og sett for å representere mye mer forseggjorte strukturer som forårsaker at problemets kompleksitet vokser.Et annet spesifikt krav er muligheten for å utføre artsprojeksjon for å samle resultatene for Homo sapiens uavhengig av arten som identifikatorene er gitt for, for å dra nytte av den mer komplette Reaktomannotasjonen For Menneske. For å gjøre dette må artens orthologer annotert I Reaktom tas i betraktning. Orthologer er enheter i forskjellige arter som utviklet seg fra en felles forfedre ved spesiering.

det siste kravet i dette trinnet er å holde oversikt over identifikatorene som kartlegger mellom de innsendte identifikatorene og de som brukes I Reaktom for å kurere de enkelte enhetene: UniProt-tiltredelser for proteiner, Ensembl-identifikator for gener, CHEBI-identifikatorer for små molekyler og miRBase for mikrornaer. Selv om en viktig del av denne kartleggingen startet med å inkludere de kjente kryssreferansene som identifikatorer i radix-treet i forrige trinn, må kartleggingen selv implementeres i dette trinnet.

Oppsummering av de eksponerte kravene til dette trinnet i analysen, må den valgte datastrukturen modellere enhetenes sammensetningsproblem, artens orthologs-projeksjon og enhetskartlegging. En rettet graf er en graf, eller sett med noder forbundet med kanter, hvor kantene har en retning knyttet til dem. For en gitt graf G med flere noder (a, b, c og d), Hvis G har en pil fra a til b og en annen pil fra b til c, så har den sammensatte grafen G 2 en pil fra a til c. Hvis G har en pil fra a til b, en annen pil fra b til c og enda en fra c til d, så har den sammensatte grafen G 3 en pil fra a til d.

Bygg en graf per art (Fig. 2a) og sammenkoble alle av dem som forbinder alle ortholog noder (Fig. 2b) skaper en større graf hvor projeksjonskravet er så fornøyd. På grunn av nodens unikhet i den endelige grafen, for de tilfellene hvor en node er en del av en eller flere strukturerte enheter, inneholder den så mange kanter som peker til andre grafnoder som strukturer der den er inneholdt, slik at strukturerte enheter enkelt modelleres. Til slutt, hvis hver node i grafen inneholder den tilknyttede enhetens hovedidentifikator(Fig. 2c), når den nås fra en radix-trenode som representerer en annen identifikator enn den viktigste, lagres denne foreningen for å bli tilbudt som en del av resultatet som den nødvendige kartleggingen når analysen er ferdig.

grafrepresentasjon Hvor P er proteiner; C er komplekser, S er sett og prime noder er de samme, men for andre arter. en art graf. b Forholdet mellom to arter. c base node innhold

grafen I Fig. 2a viser tre proteiner (P1, P2 Og P3), to komplekser (C1 Og C2) og to sett (S1 og S2). Ved å følge kanten fra node til node, Kan S2 være Enten P2 Eller P3, formelt representert som . C1 er et kompleks som, på grunn av sin kant Fra S2, er så potensielt to komplekser: {P1,P2} eller {P1,P3}, representert som . Etter denne dekonstruksjonen er S1 da Og til slutt C2 er .For eksempel, når en identifikator som samsvarer Med P3 behandles og den tilsvarende noden i grafen nås fra radix-treet, tar det liten behandlingstid å krysse grafen Og nå nodene S2, C1, S1 og C2. På samme måte, hvis målproteinet Er P1, er de tilgjengelige noder som følger grafkantene C1, S1 og C2. I begge eksemplene er hvert målprotein en del av kompleksene og settene representert av de traverserte noder.Bruk av en graf forbedrer analysealgoritmekostnaden, og viktig i å bygge en minneanalyse holdes minnebruken lav fordi det ikke er dataduplisering da noden for en gitt hovedidentifikator bare er i minnet en gang. I tillegg er det endelige antallet node-iterasjoner av algoritmen begrenset av de relaterte enhetene for en gitt identifikator, og unngår spørringer mot en stor mengde data og mellomliggende resultater sammenslåing, som gjort i den databasebaserte tilnærmingen.

når det gjelder radix-treet beskrevet ovenfor, krever grafen også en strategi for å tillate algoritmen å gå videre til neste analysetrinn. I dette tilfellet vil hver grafnode som representerer en enhet som er direkte knyttet til en eller flere baner, inneholde så mange koblinger til følgende datastruktur som forskjellige steder der den er tilstede. Selv om det i det nåværende analysetrinnet er funnet hver enhet som er tilknyttet målidentifikatoren, for sluttresultatet og statistikkberegningen, er det fortsatt en datastruktur som skal brukes, som forklart i følgende underavsnitt.

Resultataggregering i baneorganisasjonen

Hver PE som ble direkte eller indirekte truffet i forrige trinn, er knyttet til en eller flere baner. For å beregne betydningen av hver vei, for en gitt brukerprøve, er det viktig å bestemme antall enheter funnet per vei. På grunn av foreldre-barn-organiseringen Av Reaktombanene i et ontologilignende hierarki, når en enhet er tilstede i en bestemt vei, er den også tilstede i sine superbaner på rekursiv måte inntil en toppnivåbane er nådd (dvs . hvis et protein er tilstede i «Metabolisme av karbohydrater», er det også tilstede i «Metabolisme»).med tanke på kravene som tidligere ble diskutert, er en god datastruktur for å modellere dette trinnet et dobbeltbundet tre, hvor hver node representerer en vei og inneholder lenker til foreldre og barn (Fig. 3). Når en node i treet treffes, kan handlingen rekursivt forplantes helt opp til roten. Hvis du vil redusere minnefotavtrykket bare identifikatorer, holdes navn og plassholdere for resultatberegning i hver node.

dobbeltbundet tre for å representere hendelseshierarkiet I Reactome. Rotnoden definerer arten og dens barn representerer De forskjellige banene og delbanene I Reaktomet. Hver node inneholder veiidentifikatoren, navnet, de totale kuraterte enhetene og antall enheter som finnes i brukerens utvalg

Bortsett fra å være en praktisk datastruktur for å øke hastigheten på innsamling av resultater og en god holder for statistikkresultatene, når analysen er ferdig, kan denne datastrukturen også serialiseres til en fil for å fortsette resultatet. I tillegg knytte filen til et token gir en enkel måte å lage finere kornet metoder som tillater filtrering av resultatet på serversiden for å hjelpe påskynde lette klienter. I dette scenariet kan klientene beholde tokenet når den første analysen er ferdig, og avhengig av brukerens behov, utføre flere forespørsler til serveren som refererer til det tilknyttede tokenet.

analyse resultat statistikk beregning

den grunnleggende hypotesen i en overrepresentasjonsanalyse er at relevante veier kan detekteres dersom andelen differensielt uttrykte gener, innenfor en gitt vei, overstiger andelen gener som kan forventes tilfeldig . Følgelig innebærer det fjerde og siste trinnet i analysemetoden statistikkberegningen. Dette trinnet krever ingen ekstra datastruktur fordi det dobbeltkoblede treet passer perfekt til formålet.

P-Verdien viser statistisk signifikans for hver treffvei for en gitt prøve og bakgrunnen for hvilken analysen er utført. I Reaktom er Metoden som brukes til å beregne den statistiske signifikansen Binomialtesten. Sammen med p-Verdien bidrar False Discovery Rate (Fdr) til å estimere de falske positivene, og den beregnes ved hjelp Av Benjamini-Hochberg-tilnærmingen . Som nevnt tidligere har vi fokusert på å optimalisere Ytelsen Til Reaktombaneanalysen, samtidig som den grunnleggende algoritmen opprettholdes som tidligere publisert .