Reactome Path analysis: a high-performance in memory approach
Identifying a kätevä tietorakenne ratkaista tietyn ongelman on yksi tärkeimmistä tekijöistä saavuttaa korkean suorituskyvyn lopputuotteen. Kuten Skiena selittää, poiminta väärä tietorakenne työtä voi olla tuhoisaa suorituskyvyn kannalta, mutta tunnistaminen parasta tietorakenne ei yleensä ole niin kriittinen, koska voi olla useita valintoja, jotka toimivat samalla tavalla.
hajota ja hallitse-säännön perusteella ensimmäinen vaihe on analyysin ongelman jakaminen erilaisiin osaongelmiin, jotka on tarpeeksi yksinkertainen ratkaistavaksi polynomiaikaan tunnistamalla kätevä tietorakenne. Tässä analysointialgoritmi voidaan jakaa neljään osaan: (1) tarkistetaan, onko Reactomessa käyttäjän proteiini/kemiallinen tunniste, (2) nykyiset tunnisteet, selvitetään, ovatko nämä kompleksien ja/tai sarjojen osia sekä lajiprojektio, (3) kootaan havaitut tunnisteet niissä poluissa (ja superpoluissa), joissa niitä esiintyy, ja lopuksi (4) tehdään tilastollinen testaus sen todennäköisyyden laskemiseksi, että näytteiden tunnisteiden ja löydetyn reitin välinen yhteys johtuu satunnaisesta sattumasta.
tässä jaksossa jokaista osaa käsitellään yksityiskohtaisesti sen erityispiirteiden määrittämiseksi; paljastaa valitun tietorakenteen ja sen parantamiseksi hyväksytyt mekanismit; ja näyttää, miten yhdistää jokainen vaihe seuraavaan, jotta saadaan lopullinen parannettu analysointialgoritmi. Toinen optimoinnin painopiste on kunkin vaiheen muistinkäyttö, jotta täytetyt Tietorakenteet voidaan pitää muistissa niiden päälle toteutettujen datan läpikulkualgoritmien suorituskyvyn parantamiseksi.
käyttäjän otostunnisteiden haku Reaktomessa
Annotated physical entities (PE) Reactomessa voi olla joko yksittäisiä entiteettejä tai komplekseja. Yksittäisiä entiteettejä ovat proteiinit, pienet molekyylit, RNA, DNA, hiilihydraatit tai lipidit, kun taas kompleksit koostuvat minkä tahansa yksittäisen entiteetin yhdistelmästä tai yksittäisistä entiteeteistä syntetisoiduista polymeereistä. Näiden kahden pääluokan lisäksi reactomen kuraattorit voivat kuitenkin ryhmitellä toisiinsa liittyviä kokonaisuuksia sarjoiksi. PEs ovat rakennuspalikoita, joita myöhemmin käytetään syötteinä, ulostuloina, katalyytteinä tai säätelijöinä reaktioissa.
tunnisteita tai liittymisnumeroita käytetään viittaamaan yksiselitteisesti yhteen yksikköön, mutta PEs: llä on eri lähtö-ja saapumisajat, joilla on päätunniste, toissijainen tunniste, ristiviittaukset, synonyymit ja muut tunnisteet. Reactomessa tietoja kuratoivat asiantuntijat (kuraattorit) merkitsevät päätunnisteen paikan aina manuaalisesti, ja muut paikat voidaan joko täyttää käsin kuratoinnin aikana tai asuttaa automaattisesti julkaisuprosessin aikana. Tämä strategia mahdollistaa tunnisteiden tallentamisen monenlaisille resursseille: UniProt, ChEBI, Ensembl, miRBase, GenBank/EMBL/DDBJ, RefPep, RefSeq, EntrezGene, OMIM, InterPro, Affymetrix, Agilent, KEGG Compound, Illumina jne.
siksi analyysin ensimmäisessä osassa tärkein vaatimus on parantaa prosessia, jossa selvitetään, vastaako jokainen käyttäjän otoksessa oleva tunniste yhtä vai montaa Reactomessa olevaa PEs-tunnistetta. Tunniste vastaa PE: tä, jos se täsmää jonkin edellä mainittuihin lähtö-ja saapumisaikoihin tallennetun tunnisteen kanssa. Itse asiassa paras tapa ratkaista tämä ongelma on noudattamalla päinvastainen lähestymistapa; luodaan Hakutaulukko, jossa on kaikki vastaavat henkilötunnukset kutakin Reactomessa ristiviittausta kohti. Tämän seurauksena toinen tärkeä vaatimus on minimoida muistin käyttö, jotta tiedot voidaan säilyttää muistissa kyselyajan parantamiseksi.
hyvän tietorakenteen valintaan vaikuttavat vaatimukset sekä nopean hakutaulukon toteuttamiseksi että muistin käytön pitämiseksi alhaisena. Trie on järjestetty puun tietorakenne, jota käytetään tallentaa dynaaminen joukko tai assosiatiivinen array, jossa avaimet ovat yleensä merkkijonoja . Radix-puu on avaruusoptimoitu Trie-tietorakenne, jossa jokainen solmu, jossa on vain yksi lapsi, yhdistetään vanhempaansa .
toisaalta radix-puulla on suhteellisen Alhainen muistinkäyttö hakutaulukossa, koska yhteiset etuliitteet jaetaan välttäen tietojen päällekkäisyyttä (Kuva. 1). Toisaalta tasa-arvon hakuavaimen vertaaminen tietorakenteen avaimeen voi olla määräävä kustannus, jota ei voi sivuuttaa. Radix tree string lookup-algoritmi sopii analyysialgoritmin alkuperäiseen tarkoitukseen, koska iterointi puun solmujen yli pitää tunnisteen hakuajan rajoittuneena kunkin tunnisteen pituuteen ja olemassaoloon Reactome-kohdejoukossa. Tämän seurauksena, jos haettu tunniste ei sisälly tietorakenteeseen, ei tarvitse lukea sitä kaikkea, kuten tapahtuu tiivistysmenetelmissä, joissa merkkijonon hash-arvo on laskettava joka tapauksessa lukemalla se kokonaan.
Radix tree representation for the identifiers P60484, P60467, P60468, P29172, P11087, P11086, P10639, P10636, P10635, P10622, p10620, p12939, p12938, p12931, P05480, p05386, PTEN
pes ilmoittaa, onko siihen liittyvä tunniste tietokannassa vai ei. Itse asiassa mainitut ”viittaukset PE: hen” ovat todellakin viitteitä analyysin seuraavaan osaan valitun tietorakenteen solmuihin.
Reactome käyttää yksilöllisiä ensisijaisia tunnisteita PEs it-viittauksille, erityisesti uniprot-tunnistetta proteiineille ja ChEBI-tunnistetta kemiallisille yksiköille. Jos käyttäjät lähettävät tietokokonaisuuksia näitä vertailujärjestelmiä käyttäen, yhdistäminen työvoimapalveluihin on helppoa. Toistuvien käyttäjäpyyntöjen jälkeen hyväksymme kuitenkin myös syöttötiedot, joissa on ei-yksilölliset tunnisteet, erityisesti geeninimet. Tämän jälkeen ne on mahdollisesti yhdistetty useisiin henkilöresursseihin. Näin jokainen puun kohdesolmu voi sisältää enemmän kuin yhden osoittimen seuraavaan tietorakenteeseen.
kompleksien/joukkojen koostumus-ja lajiprojektio
vastaavan yksittäisen kokonaisuuden saavuttaminen tietylle tunnisteelle on analyysin toisen vaiheen alku. Kun nämä yksittäiset kokonaisuudet ovat osa kokonaisuutta, ne ovat myös kohde tässä analyysin vaiheessa. Yksittäisten entiteettien ja kompleksien lisäksi on olemassa toinen joukkoiksi kutsuttu PE-tyyppi, joka kompleksien ohella on myös otettava huomioon. Joukko on abstrakti esitys kahden tai useamman entiteetin ryhmästä, jotka eivät ole vuorovaikutuksessa keskenään, mutta ovat toiminnallisesti ekvivalentteja tilanteessa, jossa joukkoa käytetään, esimerkiksi useita entsyymiperheen jäseniä, jotka voisivat kukin mahdollisesti katalysoida reaktiota. Lisäksi kompleksit ja sarjat voivat sisältää myös muita komplekseja ja sarjoja, jotta ne edustaisivat paljon monimutkaisempia rakenteita, jotka aiheuttavat ongelman monimutkaisuuden kasvun.
toinen erityisvaatimus on mahdollisuus suorittaa lajiprojektio Homo sapiensin tulosten keräämiseksi riippumatta lajista, jolle tunnisteet on annettu, jotta voidaan hyötyä täydellisemmästä ihmiselle tarkoitetusta Reactome-merkinnästä. Tätä varten on otettava huomioon Reactomessa merkityt ortologityypit. Ortologit ovat eri lajien entiteettejä, jotka ovat kehittyneet yhteisestä kantamuodosta lajiutumisen kautta.
tämän vaiheen viimeisenä vaatimuksena on seurata lähetettyjen tunnisteiden ja niiden tunnisteiden välistä kartoitusta, joita käytetään Reactomessa yksittäisten yksiköiden kuratointiin: uniprot-tunnisteet proteiineille, Ensembl-tunniste geeneille, chebi-tunnisteet pienille molekyyleille ja miRBase micrornoille. Vaikka merkittävä osa kartoituksesta aloitettiin sisällyttämällä tunnetut ristiviittaukset tunnisteiksi radix-puuhun edellisessä vaiheessa, itse kartoitus on toteutettava tässä vaiheessa.
analysoinnin tämän vaiheen altistuneiden vaatimusten tiivistämiseksi valitun tietorakenteen tulee mallintaa entiteettien koostumusongelma, lajien orthologs-projektio ja entiteettien kartoitus. Suunnattu graafi on kuvaaja eli reunoilla yhdistettyjen solmujen joukko, jossa reunoilla on niihin liittyvä suunta. Jos g: ssä on nuoli a: sta b: hen ja toinen nuoli B: stä c: hen, muodostetussa graafissa G 2 on nuoli A: sta c: hen. Jos G: ssä on nuoli A: sta b: hen, toinen nuoli b: stä c: hen ja vielä toinen C: stä d: hen, niin muodostetussa kaaviossa G 3 on nuoli A: sta D: hen.
rakentaen yhden graafin per laji (Kuva. 2a) ja yhdistää ne kaikki yhdistää kaikki ortholog solmut (Kuva. 2b) luo suuremman kuvaajan, jossa projektiovaatimus on sitten täytetty. Lopullisen kaavion solmun ainutlaatuisuuden vuoksi niissä tapauksissa, joissa solmu on osa yhtä tai useampaa strukturoitua kokonaisuutta, se sisältää yhtä monta muihin graafin solmuihin viittaavaa reunaa kuin rakenteet, joihin se sisältyy, joten strukturoidut kokonaisuudet ovat helposti mallinnettavissa. Lopuksi, jos jokainen graafin solmu sisältää siihen liittyvän entiteetin päätunnuksen (Fig. 2c), kun se saavutetaan radix-puun solmusta, joka edustaa muuta kuin pääasiallista tunnistetta, tämä assosiaatio tallennetaan, jotta se voidaan tarjota osana tulosta vaadittuna kartoituksena, kun analyysi on valmis.
Graafiesitys, jossa P ovat proteiineja; C ovat komplekseja, S ovat joukkoja ja alkusolmut ovat samat, mutta muilla lajeilla. yhden lajin kaavio. b kahden lajin välinen suhde. c Perussolmun sisältö
kuvaaja kuviossa. 2a: ssa on kolme proteiinia (P1, P2 ja P3), kaksi kompleksia (C1 ja C2) ja kaksi joukkoa (S1 ja S2). Seuraamalla reunaa solmusta solmuun, S2 voisi olla joko P2 tai P3, muodollisesti edustettuna as . C1 on kompleksi, joka särmänsä vuoksi S2: sta on tällöin mahdollisesti kaksi kompleksia: {P1, P2} tai {P1, P3}, edustettuna as . Tämän dekonstruktion jälkeen S1 on silloin ja lopuksi C2 on .
esimerkiksi, kun käsitellään tunnistetta, joka täsmää P3: n kanssa, ja sitä vastaava solmu kaaviossa saavutetaan radix-puusta, vie pienen käsittelyajan kulkea graafin läpi ja saavuttaa solmut S2, C1, s1 ja C2. Samoin, jos kohdeproteiini on P1, graafin reunoja seuraavat tavoitettavat solmut ovat C1, S1 ja C2. Molemmissa esimerkeissä jokainen kohdeproteiini kuuluu komplekseihin ja joukkoihin, joita risteävät solmut edustavat.
graafin käyttäminen parantaa analyysialgoritmin kustannuksia ja, tärkeää muistianalyysin rakentamisessa, muistin käyttö pidetään alhaisena, koska tietojen päällekkäisyyttä ei ole, koska tietyn päätunnisteen solmu on muistissa vain kerran. Lisäksi algoritmin solmuterointien lopullista lukumäärää rajoittavat toisiinsa liittyvät yksiköt tietyn tunnisteen osalta välttäen kyselyt suurta tietomäärää ja välitulosten yhdistymistä vastaan, kuten tietokantapohjaisessa lähestymistavassa tehdään.
kuten edellä kuvatussa radix-puussa, graafi vaatii myös strategian, jonka avulla algoritmi voi siirtyä seuraavaan analyysivaiheeseen. Tällöin jokainen yhteen tai useampaan polkuun suoraan liittyvää oliota edustava graafisolmu sisältää yhtä monta linkkiä seuraavaan tietorakenteeseen kuin eri paikkoihin, joissa se esiintyy. Vaikka nykyisessä analyysivaiheessa löydetään jokainen kohdetunnisteeseen liittyvä yhteisö, lopullisessa tuloksessa ja tilastolaskennassa käytetään vielä yhtä tietorakennetta, kuten seuraavassa alajaksossa selitetään.
tulokset yhdistetään reittiorganisaatioon
jokainen PE, johon edellisessä vaiheessa osui suoraan tai välillisesti, liittyy yhteen tai useampaan reittiin. Jotta voidaan laskea kunkin reitin merkitys tietyn käyttäjänäytteen osalta, on tärkeää määrittää, kuinka monta yksikköä löytyy reittiä kohti. Ontologian kaltaisessa hierarkiassa Reaktomipolkujen vanhemman ja lapsen organisoitumisesta johtuen, kun Olio on läsnä tietyllä reitillä, se on läsnä myös superpolkuissaan rekursiivisesti, kunnes saavutetaan ylätason polku (ts. jos proteiini on läsnä ”hiilihydraattien aineenvaihdunnassa”, se on läsnä myös”aineenvaihdunnassa”).
edellä esitetyt vaatimukset huomioon ottaen hyvä tietorakenne tämän vaiheen mallintamiseksi on kaksoissidoksinen puu, jossa jokainen solmu edustaa polkua ja sisältää linkkejä vanhempaansa ja lapsiinsa (Kuva. 3). Kun puun solmuun osuu, toiminta voi rekursiivisesti edetä juureen asti. Muistijäljen pienentämiseksi kussakin solmussa pidetään vain tunnisteita, nimiä ja paikkamerkkejä tulosten laskemiseksi.
Kaksoissidoksinen puu edustamaan Tapahtumahierarkiaa Reactomessa. Juurisolmu määrittelee lajin ja sen lapset edustavat eri reittejä ja alapolkuja Reactomessa. Jokainen solmu sisältää reitin tunnisteen, nimen, kuratoitujen kokonaisyksiköiden määrän ja käyttäjän otoksesta löytyvien yksiköiden määrän
sen lisäksi, että se on kätevä tietorakenne tulosten keräämisen nopeuttamiseksi ja hyvä haltija tilastotuloksille, analyysin valmistuttua tämä tietorakenne voidaan myös sarjoittaa tiedostoon tuloksen säilyttämiseksi. Lisäksi, liittämällä tiedoston token tarjoaa helpon tavan luoda hienompaa rakeinen menetelmiä, joiden avulla suodatus tuloksen palvelimen puolella auttaa nopeuttamaan kevyt asiakkaita. Tässä skenaariossa asiakkaat voivat pitää Tokenin, kun alustava analyysi on valmis ja riippuen käyttäjän tarpeista, suorittaa useita pyyntöjä palvelimelle viittaamalla siihen liittyvään tokeniin.
analyysin tuloslaskelma
yliedustusanalyysin perushypoteesi on, että relevantit reitit voidaan havaita, jos eri tavoin ilmaistujen geenien osuus tietyllä reitillä ylittää satunnaisesti odotettavien geenien osuuden . Näin ollen analyysimenetelmän neljäs ja viimeinen vaihe sisältää tilastolaskennan. Tämä vaihe ei vaadi ylimääräistä tietorakennetta, koska kaksoissidottu puu sopii täydellisesti tarkoitukseen.
p-arvo kertoo kunkin osumareitin tilastollisen merkitsevyyden tietylle näytteelle ja taustan, jolle analyysi on tehty. Reactomessa tilastollisen merkitsevyyden laskemiseen käytetään binomikoetta. Yhdessä p-arvon kanssa False Discovery Rate (FDR) auttaa arvioimaan vääriä positiivisia ja se lasketaan Benjamini-Hochberg-menetelmällä . Kuten edellä mainittiin, olemme keskittyneet optimoimaan suorituskykyä Reactome polku analyysi, säilyttäen perus algoritmi kuten aiemmin julkaistu .