Reactome pathway analysis: nagy teljesítményű memória megközelítés
a kényelmes adatstruktúra azonosítása egy adott probléma megoldására az egyik fő tényező a nagy teljesítményű végtermék eléréséhez. Ahogy Skiena elmagyarázza , a rossz adatstruktúra kiválasztása a munkához katasztrofális lehet a teljesítmény szempontjából, de a legjobb adatstruktúra azonosítása általában nem olyan kritikus, mert több olyan választás is lehet, amelyek hasonlóan teljesítenek.
a divide and conquer szabály alapján az első lépés az elemzési probléma különböző részproblémákra bontása, amely elég egyszerű ahhoz, hogy polinom időben megoldható legyen egy kényelmes adatstruktúra azonosításával. Itt az elemzési algoritmus négy részre osztható: (1) annak ellenőrzése, hogy a felhasználó fehérje/kémiai azonosítói jelen vannak-e a Reaktomban, (2) a jelenlegi azonosítók esetében, annak megállapítása, hogy ezek komplexek és/vagy halmazok részei-e, valamint a fajprojekció, (3) a talált azonosítók összesítése azokban az útvonalakban (és szuper-útvonalakban), ahol ezek jelen vannak, és végül (4) statisztikai vizsgálat elvégzése annak kiszámításához, hogy a mintaazonosítók és a talált útvonal közötti összefüggés véletlenszerű véletlennek köszönhető-e.
tovább ebben a szakaszban az egyes részeket részletesen tárgyaljuk annak sajátosságainak meghatározása érdekében; feltárni a kiválasztott adatstruktúrát és a fejlesztéshez alkalmazott mechanizmusokat; és megmutatni, hogyan lehet az egyes lépéseket összekapcsolni a következővel, hogy előálljon a végső továbbfejlesztett elemzési algoritmus. Az optimalizálás másik hangsúlyos pontja az egyes lépések memóriahasználata lesz, így a kitöltött adatstruktúrák a memóriában tarthatók, hogy javítsák a tetején megvalósított adatáthaladó algoritmusok teljesítményét.
felhasználói minta azonosítók keresés a Reaktomban
jegyzetekkel ellátott fizikai entitások (PE) a Reaktomban lehetnek egyedi entitások vagy komplexek. Az egyes entitások közé tartoznak a fehérjék, kis molekulák, RNS, DNS, szénhidrátok vagy lipidek, míg a komplexek az egyes entitások bármelyikének kombinációjából vagy az egyes entitásokból szintetizált polimerekből állnak. E két fő kategórián kívül azonban a Reactome kurátorai csoportosíthatják a kapcsolódó entitásokat halmazokba. Az ÁFSz-ek azok az építőelemek, amelyeket később bemenetként, kimenetként, katalizátorként vagy szabályozóként használnak a reakciókban.
az azonosítókat vagy a csatlakozási számokat arra használják, hogy egyértelműen egyetlen entitásra utaljanak, de az ÁFSz-eknek különböző helyeik vannak a fő azonosító, másodlagos azonosító, kereszthivatkozások, szinonimák és egyéb azonosítók tárolására. A fő azonosító helyet mindig manuálisan kommentálják azok a szakértők, akik az adatokat a Reactome-ban kurálják (kurátorok), a többi helyet pedig manuálisan tölthetik ki a kuráció során, vagy automatikusan kitölthetik a kiadási folyamat során. Ez a stratégia lehetővé teszi az azonosítók tárolását az erőforrások széles skálájához: UniProt, ChEBI, Ensembl, miRBase, GenBank/EMBL/DDBJ, RefPep, RefSeq, EntrezGene, OMIM, InterPro, Affymetrix, Agilent, KEGG Compound, Illumina stb.
ezért az elemzés első részében a fő követelmény annak megállapítása, hogy a felhasználói mintában szereplő egyes azonosítók megfelelnek-e egy vagy több PE-nek a Reactome-ban. Az azonosító akkor felel meg a PE-nek, ha megegyezik a fent említett különböző résekben tárolt azonosítók bármelyikével. Valójában a probléma megoldásának legjobb módja a fordított megközelítés követése; keresési táblázat létrehozása az összes megfelelő PE-vel minden egyes azonosítónként, amelyre a Reactome hivatkozik. Ennek következtében egy másik fontos követelmény a memóriahasználat minimalizálása, hogy az adatok a memóriában tárolhatók legyenek a lekérdezési idő javítása érdekében.
a jó adatstruktúra kiválasztását ezután a követelmények határozzák meg mind a gyors keresési táblázat megvalósításához, mind a memóriahasználat alacsony szinten tartásához. A Trie egy rendezett fa adatstruktúra, amelyet dinamikus halmaz vagy asszociatív tömb tárolására használnak, ahol a kulcsok általában húrok . A radix fa egy térre optimalizált Trie adatstruktúra, ahol minden csomópont csak egy gyermekkel egyesül a szülőjével .
egyrészt egy radix fa viszonylag alacsony memóriahasználattal rendelkezik a keresési táblához, mert a közös előtagok megosztottak, elkerülve az adatok duplikációját (ábra. 1). Másrészt az egyenlőség keresőkulcsának az adatstruktúrából származó kulccsal való összehasonlításának költsége domináns költség lehet, amelyet nem lehet elhanyagolni. A radix tree string keresési algoritmus megfelel az elemzési algoritmus eredeti céljának, mivel a fa csomópontokon történő iterálás az azonosító keresési idejét az egyes azonosítók hosszára és létezésére korlátozza a Reactome célkészletben. Ennek következtében abban az esetben, ha a keresett azonosító nem szerepel az adatstruktúrában, nincs szükség az egész elolvasására, mint a kivonatolási módszereknél, ahol a húr hash értékét minden esetben teljes egészében ki kell számítani.
a P60484, P60467, P60468, P29172, P11087, P11086, P10639, P10636, P10635, p10622, p10620, p12939, p12938, p12931, p05480, p05386, pten
összefoglalva, ha egy fa csomópontot elérünk a Radix fa keresési algoritmust követve egy adott azonosítóhoz, a A pes azt jelzi, hogy a társított azonosító jelen van-e vagy sem az adatbázisban. Valójában az említett “hivatkozások a PE-re” valóban az elemzés következő részéhez kiválasztott adatstruktúra csomópontjaira mutatnak.
a Reactome egyedi elsődleges azonosítókat használ a PEs it referenciákhoz, különösen az uniprot a fehérjékhez és a Chebi a kémiai entitásokhoz. Így, ha a felhasználók adatkészleteket nyújtanak be ezekkel a referenciarendszerekkel, a PEs-hez való leképezés egyszerű. A gyakori felhasználói kéréseket követően azonban nem egyedi azonosítókkal, különösen génnevekkel ellátott bemeneti adatokat is elfogadunk. Ezeket ezután potenciálisan több PE-hez rendelik. Így a fa minden célcsomópontja egynél több mutatót tartalmazhat a következő adatstruktúrára.
komplexek/halmazok bejárása összetétel és fajprojekció
az adott azonosítóhoz társított egyetlen entitás elérése az elemzés második lépésének kezdete. Ha ezek az egyes entitások egy komplex részét képezik, akkor az elemzés ezen lépésében is célpontok. Az egyes entitások és komplexek mellett létezik egy másik típusú PE is, amelyet halmazoknak nevezünk, amelyeket a komplexekkel együtt szintén figyelembe kell venni. A halmaz két vagy több entitás csoportjának absztrakt ábrázolása, amelyek nem kölcsönhatásba lépnek egymással, de funkcionálisan egyenértékűek abban a helyzetben, amikor a halmazt használják, például egy enzimcsalád több tagja, amelyek mindegyike potenciálisan katalizálhat egy reakciót. Továbbá a komplexek és halmazok tartalmazhatnak más komplexeket és halmazokat is annak érdekében, hogy sokkal bonyolultabb struktúrákat képviseljenek, amelyek a probléma bonyolultságának növekedését okozzák.
egy másik speciális követelmény a fajprojekció elvégzésének lehetősége a Homo sapiens eredményeinek összegyűjtése érdekében, függetlenül attól a fajtól, amelyre az azonosítókat megadták, hogy kihasználhassák az emberre vonatkozó teljesebb Reactome annotációt. Ehhez figyelembe kell venni a Reactome-ban kommentált ortológusokat. Az ortológusok különböző fajok entitásai, amelyek egy közös ősből fejlődtek ki speciáció.
ebben a lépésben az utolsó követelmény az, hogy nyomon kövessük az azonosítók leképezését a benyújtott azonosítók és a Reactome-ban használt azonosítók között az egyes entitások kurálására: uniprot-hozzáférések a fehérjékhez, Ensembl-azonosító a génekhez, Chebi-azonosítók a kis molekulákhoz és miRBase a mikroRNS-ekhez. Bár ennek a leképezésnek egy fontos része azzal kezdődött, hogy az előző lépésben az ismert kereszthivatkozásokat azonosítóként belefoglalták a radixfába, magát a leképezést ebben a lépésben kell végrehajtani.
az elemzés ezen lépésének kitett követelményeit összegezve a kiválasztott adatstruktúrának modelleznie kell az entitások összetételének problémáját, a faj ortológusok vetületét és az entitások leképezését. Az irányított gráf egy gráf, vagy élek által összekapcsolt csomópontok halmaza,ahol az éleknek van egy irányuk. Egy adott g gráf esetében, amelynek több csomópontja van (a, b, c és d), Ha G-nek van egy nyílja a-tól b-ig, és egy másik nyílja b-től c-ig, akkor a G 2-nek van egy nyílja a-tól c-ig. Ha G-nek van egy nyílja a-tól b-ig, egy másik nyíl b-től c-ig, és még egy másik c-től d-ig, akkor a G 3 komponált gráfnak van egy nyílja a-tól d-ig.
fajonként egy gráf felépítése (ábra. 2a), és összekapcsolja őket, összekapcsolva az összes ortholog csomópontot (ábra. 2b) létrehoz egy nagyobb gráfot, ahol a vetítési követelmény teljesül. A végső gráf csomópont-egyedisége miatt azokban az esetekben, amikor egy csomópont egy vagy több strukturált entitás része, annyi élt tartalmaz, amely más gráfcsomópontokra mutat, mint azok a struktúrák, amelyekben benne van, így a strukturált entitások könnyen modellezhetők. Végül, ha a grafikon minden csomópontja tartalmazza a társított entitás fő azonosítóját (ábra. 2c), amikor egy radix fa csomópontból érkezik, amely a főtől eltérő azonosítót képvisel, ezt az asszociációt tárolják annak érdekében, hogy az elemzés befejezése után az eredmény részeként felajánlják a szükséges leképezésként.
Gráfábrázolás, ahol P fehérjék; C komplexek, S halmazok és prímcsomópontok ugyanazok, csak más fajoknál. egy faj grafikon. b kapcsolat két faj között. c Alapcsomópont tartalma
a grafikon ábra. A 2A három fehérjét (P1, P2 és P3), két komplexet (C1 és C2) és két készletet (S1 és S2) mutat. A csomóponttól a csomópontig tartó él követésével S2 lehet P2 vagy P3, formálisan ábrázolva . C1 egy olyan komplex, amely az S-től való éle miatt2, akkor potenciálisan két komplex: {P1, P2} vagy {P1 ,P3}, mint. Ezt a dekonstrukciót követően S1 akkor, végül C2 .
például, amikor egy P3-Mal egyező azonosítót feldolgozunk, és a gráf megfelelő csomópontját a radixfáról érjük el, a gráfon való áthaladáshoz és az S2, C1, S1 és C2 csomópontok eléréséhez minimális feldolgozási időre van szükség. Hasonlóképpen, ha a célfehérje P1, akkor a gráf éleit követő elérhető csomópontok C1, S1 és C2. Mindkét példában minden célfehérje része a komplexeknek és halmazoknak, amelyeket az áthaladó csomópontok képviselnek.
a gráf alkalmazása javítja az elemzési algoritmus költségeit, és fontos a memóriában lévő elemzés elkészítésekor, hogy a memóriahasználat alacsony maradjon, mert nincs adat duplikáció, mivel egy adott főazonosító csomópontja csak egyszer van a memóriában. Ezenkívül az algoritmus csomópont iterációinak végső számát a kapcsolódó entitások korlátozzák egy adott azonosítóhoz, elkerülve a nagy mennyiségű adat és a közbenső eredmények összevonását, ahogy az az adatbázis alapú megközelítésben történik.
ami a fent leírt radix fát illeti, a grafikonhoz stratégia is szükséges, hogy az algoritmus továbbléphessen a következő elemzési lépésre. Ebben az esetben minden olyan gráfcsomópont, amely egy vagy több útvonalhoz közvetlenül társított entitást képvisel, annyi linket tartalmaz a következő adatstruktúrához, mint a különböző helyek, ahol jelen van. Bár a jelenlegi elemzési lépésben a célazonosítóhoz társított minden entitás megtalálható, a végeredményhez és a statisztikai számításhoz még egy adatstruktúrát kell használni, amint azt a következő alszakasz ismerteti.
eredmények összesítése a pathways organization-be
minden PE, amelyet az előző lépésben közvetlenül vagy közvetve eltaláltak, egy vagy több pathways-hez kapcsolódik. Az egyes útvonalak jelentőségének kiszámításához egy adott felhasználói minta esetében elengedhetetlen az útvonalonként talált entitások számának meghatározása. A Reaktom utak szülő-gyermek szerveződése miatt egy ontológia-szerű hierarchiában, amikor egy entitás egy bizonyos útvonalon van jelen, akkor a szuperútjain is rekurzív módon van jelen, amíg el nem ér egy felső szintű utat (azaz. ha egy fehérje jelen van a” szénhidrátok metabolizmusában”, akkor az”anyagcserében” is jelen van).
figyelembe véve a korábban tárgyalt követelményeket, egy jó adatstruktúra a lépés modellezéséhez egy kettős összekapcsolt fa, ahol minden csomópont egy útvonalat képvisel, és linkeket tartalmaz a szülőjéhez és gyermekeihez (ábra. 3). Amikor a fa egy csomópontját eltalálják, a művelet rekurzívan szaporítható egészen a gyökérig. A memória lábnyom csökkentése érdekében az egyes csomópontokban csak az azonosítók, nevek és helyőrzők kerülnek tárolásra az eredmények kiszámításához.
kettős kapcsolt fa az eseményhierarchia képviseletére a Reactome-ban. A gyökércsomópont meghatározza a fajt, gyermekei pedig a Reactome különböző útvonalait és alútjait képviselik. Minden csomópont tartalmazza az útvonalazonosítót, a nevet, az összes kurált entitást és a felhasználó mintájában található entitások számát
amellett, hogy kényelmes adatstruktúra az eredmények gyűjtésének felgyorsítására és a statisztikai eredmények jó birtokosa, az elemzés befejezése után ez az adatstruktúra is sorosítható fájlba az eredmény megmaradása érdekében. Ezenkívül a fájl tokenhez való társítása egyszerű módja annak, hogy finomabb szemcsés módszereket hozzon létre, amelyek lehetővé teszik az eredmény szűrését a szerver oldalon, hogy elősegítsék a könnyű ügyfelek felgyorsítását. Ebben az esetben az ügyfelek megtarthatják a tokent a kezdeti elemzés befejezése után, és a felhasználó igényeitől függően több kérést is végrehajthatnak a kiszolgálónak a társított Tokenre hivatkozva.
elemzési eredmény statisztikai számítás
a túlreprezentációs elemzés alapvető hipotézise az, hogy a releváns utak kimutathatók, ha a differenciálisan expresszált gének aránya egy adott útvonalon belül meghaladja a véletlenszerűen várható gének arányát . Következésképpen az elemzési módszer negyedik és utolsó lépése a statisztikai számítás. Ez a lépés nem igényel extra adatstruktúrát, mivel a kettős összekapcsolt fa tökéletesen illeszkedik a célhoz.
A p-érték mutatja az egyes találati útvonalak statisztikai szignifikanciáját egy adott mintára, valamint azt a hátteret, amelyre az elemzést elvégezték. A Reactome-ban a statisztikai szignifikancia kiszámításához használt módszer a binomiális teszt. A p-értékkel együtt a hamis felfedezési Arány (FDR) segít megbecsülni a hamis pozitív eredményeket, és a Benjamini-Hochberg megközelítéssel számítják ki . Mint már említettük, a Reactome pathway analysis teljesítményének optimalizálására összpontosítottunk, miközben megtartottuk az alap algoritmust a korábban közzétett módon .