identifiera en bekväm datastruktur för att lösa ett givet problem är en av de viktigaste faktorerna för att uppnå en högpresterande slutprodukt. Som Skiena förklarar i, att välja fel datastruktur för jobbet kan vara katastrofalt när det gäller prestanda, men att identifiera den allra bästa datastrukturen är vanligtvis inte lika kritisk, eftersom det kan finnas flera val som fungerar på samma sätt.

baserat på divide and conquer-regeln är det första steget att bryta ner analysproblemet i olika delproblem som är enkla att lösa i polynomtid genom att identifiera en bekväm datastruktur. Här kan analysalgoritmen delas upp i fyra delar: (1) Kontrollera om användarens protein-/kemiska identifierare finns i Reactome, (2) för de nuvarande, hitta om dessa är delar av komplex och/eller uppsättningar samt artprojektionen, (3) aggregera de hittade identifierarna i vägarna (och supervägarna) där dessa finns och slutligen (4) utföra den statistiska testningen för att beräkna sannolikheten för att sambandet mellan providentifierarna och den hittade vägen beror på slumpmässig chans.

vidare i detta avsnitt diskuteras varje del i detalj för att bestämma dess särdrag; att exponera den valda datastrukturen och de mekanismer som antagits för dess förbättring; och för att visa hur man ansluter varje steg till följande för att komma fram till den slutliga förbättrade analysalgoritmen. En annan betoning för optimering kommer att vara minnesanvändningen för varje steg, så att de fyllda datastrukturerna kan hållas i minnet för att förbättra prestandan hos de dataöverföringsalgoritmer som implementeras ovanpå dem.

användarprovsidentifierare sök i Reactome

annoterade fysiska enheter (PE) i Reactome kan vara antingen enskilda enheter eller komplex. Enskilda enheter inkluderar proteiner, små molekyler, RNA, DNA, kolhydrater eller lipider, medan komplex består av en kombination av någon av de enskilda enheterna eller polymerer syntetiserade från de enskilda enheterna. Bortsett från dessa två huvudkategorier kan kuratorer i Reactome dock gruppera relaterade enheter i uppsättningar. PEs är byggstenarna som senare kommer att användas som ingångar, utgångar, katalysatorer eller regulatorer i reaktioner.

identifierare eller anslutningsnummer används för att entydigt hänvisa till en enda enhet, men PEs har olika luckor för att hålla huvudidentifieraren, sekundäridentifieraren, korsreferenser, synonymer och andra identifierare. Huvudidentifieringsplatsen kommenteras alltid manuellt av experterna som samlar in data i Reactome (curatorer), och de andra slitsarna kan antingen fyllas manuellt under curation eller automatiskt befolkas under utgivningsprocessen. Denna strategi gör det möjligt att lagra identifierare för ett brett spektrum av resurser: UniProt, Chebi, Ensembl, miRBase, GenBank / EMBL / DDBJ, RefPep, RefSeq, EntrezGene, OMIM, InterPro, Affymetrix, Agilent, KEGG förening, Illumina, etc.

därför är huvudkravet i den första delen av analysen att förbättra processen för att ta reda på om varje identifierare i användarens prov motsvarar en eller flera PEs i Reactome. En identifierare motsvarar en PE om den matchar någon av de identifierare som lagras i de olika spåren som nämns ovan. Faktum är att det bästa sättet att lösa detta problem är att följa omvänd tillvägagångssätt; skapa en uppslagstabell med alla motsvarande PEs per varje identifierare korsrefererade i Reactome. Som en konsekvens är ett annat viktigt krav att minimera minnesanvändningen så att data kan hållas i minnet för att förbättra frågestunden.

valet av en bra datastruktur bestäms sedan av krav både för att implementera en snabb uppslagstabell och för att hålla minnesanvändningen låg. En Trie är en ordnad träddatastruktur som används för att lagra en dynamisk uppsättning eller associativ array där nycklarna vanligtvis är strängar . Ett radix-träd är en rymdoptimerad Trie – datastruktur där varje nod med endast ett barn slås samman med sin förälder .

å ena sidan har ett radix-träd relativt låg minnesanvändning för uppslagstabellen eftersom de vanliga prefixen delas och undviker dataduplikering (Fig. 1). Å andra sidan kan kostnaden för att jämföra en söknyckel för jämlikhet med en nyckel från datastrukturen vara en dominerande kostnad som inte kan försummas. Radix tree string lookup-algoritmen passar analysalgoritmens ursprungliga syfte eftersom iterering över trädnoder håller identifieraren som söker tid begränsad till varje identifierares längd och existens i Reactome-måluppsättningen. Som en konsekvens av detta, om den sökta identifieraren inte finns i datastrukturen, finns det inget behov av att läsa allt som händer i hashningsmetoderna där strängens hashvärde måste beräknas i alla fall genom att läsa den helt.

Radix trädrepresentation för identifierarna P60484, P60467, P60468, P29172, P11087, P11086, P10639, P10636, P10635, p10622, p10620, p12939, p12938, p12931, p05480, p05386, PTEN

Sammanfattningsvis, när en Trädnod har uppnåtts efter Radix-Träduppslagningsalgoritmen för en given identifierare, närvaron eller frånvaron av referenser till PES anger om den associerade identifieraren finns eller inte i databasen. I själva verket är de nämnda ”referenserna till PE” verkligen pekare till noder i datastrukturen som valts för nästa del av analysen.

Reactome använder unika primära identifierare för PEs it-referenser, särskilt UniProt för proteiner och ChEBI för kemiska enheter. Således, om användare skickar in dataset med hjälp av dessa referenssystem, är kartläggningen till PEs enkel. Men efter frekventa användarförfrågningar accepterar vi också indata med icke-unika identifierare, särskilt gennamn. Dessa mappas sedan potentiellt till flera PEs. Således kan varje målnod i trädet innehålla mer än en pekare till nästa datastruktur.

att korsa komplex/uppsättningar sammansättning och artprojektion

att nå den associerade enskilda enheten för en given identifierare är början på det andra steget i analysen. När dessa enskilda enheter är en del av ett komplex är de också ett mål i detta steg i analysen. Förutom de enskilda enheterna och komplexen finns det en annan typ av PE som kallas uppsättningar som tillsammans med komplex också ska övervägas. En uppsättning är en abstrakt representation av en grupp av två eller flera enheter som inte interagerar med varandra men är funktionellt ekvivalenta i den situation där uppsättningen används, till exempel flera medlemmar i en familj av enzymer som var och en potentiellt kan katalysera en reaktion. Dessutom kan komplex och uppsättningar också innehålla andra komplex och uppsättningar för att representera mycket mer detaljerade strukturer som orsakar problemets inveckling att växa.

ett annat specifikt krav är möjligheten att utföra artprojektion för att samla resultaten för Homo sapiens oberoende av de arter för vilka identifierarna tillhandahålls, för att dra nytta av den mer fullständiga reaktomanteckningen för människa. För att göra det måste de orthologer som kommenteras i Reactome beaktas. Ortologer är enheter i olika arter som utvecklats från en gemensam förfader genom speciering.

det sista kravet i detta steg är att hålla reda på identifierarna som kartlägger mellan de inlämnade identifierarna och de som används i Reactome för att kurera de enskilda enheterna: UniProt-anslutningar för proteiner, Ensembl-identifierare för gener, CHEBI-identifierare för små molekyler och miRBase för mikroRNA. Även om en viktig del av denna kartläggning började med att inkludera de kända korsreferenserna som identifierare i radix-trädet i föregående steg, måste själva kartläggningen implementeras i detta steg.

sammanfattar de exponerade kraven för detta steg i analysen, den valda datastrukturen måste modellera entitetskompositionsproblemet, artens orthologsprojektion och entitetsmappningen. En riktad graf är en graf eller en uppsättning noder förbundna med kanter, där kanterna har en riktning associerad med dem. För en given graf G med flera noder (a, b, c och d), om G har en pil från a till b och en annan pil från b till c, har den sammansatta grafen G 2 en pil från A till c. Om G har en pil från A till b, en annan pil från b till c och ännu en från c till d, har den sammansatta grafen G 3 en pil från a till d.

bygga en graf per art (Fig. 2a) och sammankoppling av dem alla som förbinder alla ortolognoder (Fig. 2b) skapar en större graf där projektionskravet sedan uppfylls. På grund av nodens unikhet i den slutliga grafen, för de fall där en nod är en del av en eller flera strukturerade enheter, innehåller den så många kanter som pekar på andra grafnoder som strukturer där den finns, så strukturerade enheter modelleras enkelt. Slutligen, om varje nod i diagrammet innehåller dess associerade enhet huvudidentifierare (Fig. 2c), när den nås från en radix-trädnod som representerar en annan identifierare än den huvudsakliga, lagras denna förening för att erbjudas som en del av resultatet som den nödvändiga kartläggningen när analysen är klar.

Grafrepresentation där P är proteiner; C är komplex, S är uppsättningar och primära noder är desamma men för andra arter. en art graf. B förhållande mellan två arter. c Basnod innehåll

grafen i Fig. 2a visar tre proteiner (P1, P2 och P3), två komplex (C1 och C2) och två uppsättningar (S1 och S2). Genom att följa kanten från nod till nod kan S2 vara antingen P2 eller P3, formellt representerad som . C1 är ett komplex som på grund av sin kant från S2 då är potentiellt två komplex: {P1, P2} eller {P1,P3}, representerad som . Efter denna dekonstruktion är S1 då och slutligen C2 är .

till exempel, när en identifierare som matchar med P3 bearbetas och dess motsvarande nod i grafen nås från radix-trädet, tar det liten bearbetningstid att korsa grafen och nå noderna S2, C1, S1 och C2. På samma sätt, om målproteinet är P1, är de nåbara noderna som följer grafkanterna C1, S1 och C2. I båda exemplen är varje målprotein en del av komplexen och uppsättningarna representerade av de korsade noderna.

att använda en graf förbättrar analysalgoritmens kostnad och, viktigt för att bygga en analys i minnet, hålls minnesanvändningen låg eftersom det inte finns någon dataduplikering eftersom noden för en given huvudidentifierare bara finns i minnet en gång. Dessutom begränsas det slutliga antalet nod-iterationer av algoritmen av de relaterade enheterna för en given identifierare, vilket undviker frågor mot en stor mängd data och mellanresultat som slås samman, vilket görs i databasbaserad metod.

När det gäller radix-trädet som beskrivs ovan kräver grafen också en strategi för att låta algoritmen gå vidare till nästa analyssteg. I det här fallet kommer varje grafnod som representerar en enhet som är direkt associerad med en eller flera vägar att innehålla lika många länkar till följande datastruktur som olika platser där den finns. Även om varje enhet som är associerad med målidentifieraren i det aktuella analyssteget hittas, för slutresultatet och statistikberäkningen finns det fortfarande ytterligare en datastruktur som ska användas, vilket förklaras i följande underavsnitt.

Resultataggregation i pathways organisation

varje PE som direkt eller indirekt träffades i föregående steg är associerad med en eller flera pathways. För att beräkna betydelsen av varje väg, för ett givet användarprov, är det viktigt att bestämma antalet enheter som hittats per väg. På grund av föräldra-barnorganisationen av Reaktomvägarna i en ontologiliknande hierarki, när en enhet är närvarande i en viss väg är den också närvarande i sina supervägar på ett rekursivt sätt tills en toppnivåväg nås (dvs. om ett protein är närvarande i” metabolism av kolhydrater”, är det också närvarande i”Metabolism”).

med hänsyn till de krav som tidigare diskuterats är en bra datastruktur för att modellera detta steg ett dubbellänkt träd, där varje nod representerar en väg och innehåller länkar till dess förälder och barn (Fig. 3). När en nod i trädet träffas kan åtgärden rekursivt förökas hela vägen upp till roten. För att minska minnesavtrycket behålls endast identifierare, namn och platshållare för resultatberäkning i varje nod.

Dubbellänkat träd för att representera händelsehierarkin i Reactome. Rotnoden definierar arten och dess barn representerar de olika vägarna och delvägarna i Reactome. Varje nod innehåller pathway identifier, namn, totalt curated entities och antalet enheter som finns i användarens prov

förutom att vara en bekväm datastruktur för att påskynda insamlingen av resultat och en bra innehavare för statistikresultaten, när analysen är klar kan denna datastruktur också serialiseras till en fil för att fortsätta resultatet. Dessutom ger associering av filen till en token ett enkelt sätt att skapa finare korniga metoder som möjliggör filtrering av resultatet på serversidan för att påskynda lätta klienter. I det här scenariot kan klienterna behålla token när den första analysen är klar och beroende på användarens behov, utföra flera förfrågningar till servern som refererar till den associerade token.

analysresultat statistikberäkning

den grundläggande hypotesen i en överrepresentationsanalys är att relevanta vägar kan detekteras om andelen differentiellt uttryckta gener, inom en given väg, överstiger andelen gener som slumpmässigt kan förväntas . Följaktligen innebär det fjärde och sista steget i analysmetoden statistikberäkningen. Detta steg kräver ingen extra datastruktur eftersom det dubbelbundna trädet passar perfekt till syftet.

p-värdet visar den statistiska signifikansen för varje träffväg för ett givet prov och bakgrunden för vilken analysen har utförts. I Reactome metoden som används för att beräkna den statistiska signifikansen är Binomialtestet. Tillsammans med p-värdet hjälper False Discovery Rate (FDR) att uppskatta de falska positiverna och det beräknas med Benjamini-Hochberg-metoden . Som nämnts ovan har vi fokuserat på att optimera prestandan för Reactome pathway-analysen, samtidigt som den grundläggande algoritmen bibehålls som tidigare publicerats .