Určení vhodné datové struktury pro vyřešení daného problému je jedním z hlavních faktorů k dosažení vysoké výkonnosti konečného produktu. Jako Skiena vysvětluje , výběrem špatné datové struktury pro práci může být katastrofální, pokud jde o výkon, ale identifikovat nejlepší datová struktura je obvykle není tak kritické, protože tam může být několik možností, které provádějí podobně.

na Základě rozděl a panuj pravidlo, prvním krokem je rozebrat analýzu problému do různých sub-problémy natolik jednoduchý, musí být vyřešen v polynomiálním čase pomocí identifikace vhodné datové struktury. Zde lze analytický algoritmus rozdělit na čtyři části: (1) kontrola, zda uživatel je protein/chemické identifikátory, které jsou přítomny v Reactome, (2) pro ti, zjištění, zda tyto jsou součástí komplexů a/nebo sad, stejně jako druh projekce, (3) slučování nalezených identifikátory drah (a super-cesty), kde jsou přítomny, a konečně (4) provádějící statistické testování vypočítat pravděpodobnost, že asociace mezi vzorkem identifikátory a našel cestu, je vzhledem k náhodné šance.

dále v této části je každá část podrobně diskutována, aby se určily její zvláštnosti; odhalit zvolenou datovou strukturu a mechanismy přijaté pro její zlepšení; a ukázat, jak propojit každý krok s následujícím krokem, abyste přišli s konečným vylepšeným algoritmem analýzy. Dalším bodem důraz na optimalizaci bude využití paměti každý krok, tak, že naplněné datové struktury mohou být uchovávány v paměti, aby zlepšit výkon dat křížení algoritmy prováděny na horní z nich.

vyhledávání uživatelských identifikátorů v Reactome

anotované fyzické entity (PE) v Reactome mohou být buď jednotlivé entity nebo komplexy. Jednotlivé entity zahrnují proteiny, malé molekuly, RNA, DNA, sacharidy nebo lipidy, zatímco komplexy se skládají z kombinace kterékoli z jednotlivých entit nebo polymerů syntetizovaných z jednotlivých entit. Kromě těchto dvou hlavních kategorií však mohou kurátoři v Reactome seskupit související entity do sad. PEs jsou stavební kameny, které budou později použity jako vstupy, výstupy, katalyzátory nebo regulátory v reakcích.

Identifikátory nebo přistoupení, čísla jsou používány, aby jednoznačně odkazovat na jeden subjekt, ale PEs mají různé sloty držet hlavní identifikátor, sekundární identifikátor, křížové odkazy, synonyma a další identifikátory. Hlavní identifikátor slotu je vždy ručně komentovaný odborníky, kteří kaplan dat v Reactome (kurátoři), a další sloty mohou být buď ručně vyplněný během curation nebo automaticky naplněna během procesu uvolňování. Tato strategie umožňuje ukládat identifikátory pro širokou škálu zdrojů: UniProt, ChEBI, Ensembl, miRBase, GenBank/EMBL/DDBJ, RefPep, RefSeq, EntrezGene, OMIM, InterPro, Affymetrix, Agilent, KEGG Sloučenina, Illumina, atd.

proto je v první části analýzy hlavním požadavkem zlepšit proces zjišťování, zda každý identifikátor ve vzorku uživatele odpovídá jednomu nebo mnoha PEs v Reactome. Identifikátor odpovídá PE, pokud se shoduje s některým z identifikátorů uložených v různých výše uvedených slotech. Ve skutečnosti je nejlepším způsobem, jak tento problém vyřešit, opačný přístup; vytvoření vyhledávací tabulky se všemi odpovídajícími PEs na každý identifikátor křížově odkazované v Reactome. V důsledku toho je dalším důležitým požadavkem minimalizovat využití paměti, aby data mohla být uchovávána v paměti, aby se zlepšil čas dotazu.

výběr dobré datové struktury je pak určen požadavky jak pro implementaci tabulky rychlého vyhledávání, tak pro udržení nízkého využití paměti. Trie je uspořádaná stromová datová struktura, která se používá k ukládání dynamické sady nebo asociativního pole, kde klíče jsou obvykle řetězce . Strom radix je prostorově optimalizovaná datová struktura Trie, kde je každý uzel pouze s jedním dítětem sloučen s jeho rodičem .

Na jedné straně, radix strom má relativně nízké využití paměti pro vyhledávací tabulky, protože společné předpony jsou sdíleny vyhnout se duplikaci dat (Obr. 1). Na druhé straně náklady na porovnání vyhledávacího klíče pro rovnost s klíčem z datové struktury mohou být dominantní náklady, které nelze opomenout. Radix tree string vyhledávací algoritmus se hodí na analýzu algoritmu je původní účel, protože iterace uzly stromu udržuje identifikátor, kteří hledají časově omezeno, aby každý identifikátor a délka existence v Reactome stanovený cíl. V důsledku toho, v případě, že hledaný identifikátor není obsažena v datové struktuře, není třeba číst všechno, jak se děje v hashovací metody, kde hodnota hash řetězce musí být vypočteny v každém případě tím, že čte úplně.

br. 1

Radix stromu zastoupení pro identifikátory P60484, P60467, P60468, P29172, P11087, P11086, P10639, P10636, P10635, P10622, P10620, P12939, P12938, P12931, P05480, P05386, PTEN

stručně řečeno, jakmile uzel stromu je dosaženo po radix tree lookup algoritmus pro daný identifikátor, přítomnost či absence odkazů k PEs označuje, zda přidružených identifikátor je přítomen, nebo není v databázi. Ve skutečnosti jsou zmíněné „odkazy na PE“ skutečně ukazateli na uzly v datové struktuře vybrané pro další část analýzy.

Reactome používá jedinečné primární identifikátory pro PEs, na které odkazuje, zejména UniProt pro proteiny a ChEBI pro chemické entity. Pokud tedy uživatelé odesílají datové sady pomocí těchto referenčních systémů, mapování na PEs je jednoduché. Na základě častých požadavků uživatelů však přijímáme také vstupní data s nejedinečnými identifikátory, zejména názvy genů. Ty jsou pak potenciálně mapovány na více PEs. Každý cílový uzel ve stromu by tedy mohl obsahovat více než jeden ukazatel na další datovou strukturu.

Křížení komplexy/sady složení a druhy projekce

Dosažení souborům jediného subjektu pro daný identifikátor je začátek druhého kroku analýzy. Pokud jsou tyto jednotlivé entity součástí komplexu, jsou také cílem v tomto kroku analýzy. Kromě jednotlivých entit a komplexů existuje další typ PE nazývaných množiny, které je třeba spolu s komplexy také zvážit. Sada je abstraktní reprezentace skupiny dvou nebo více subjektů, které nejsou v interakci s ostatními, ale jsou funkčně ekvivalentní v situaci, kdy je používána, například více členů rodiny enzymů, které mohou potenciálně sloužit jako katalyzátor reakce. Kromě toho mohou komplexy a množiny obsahovat i další komplexy a množiny, aby představovaly mnohem propracovanější struktury způsobující růst složitosti problému.

Dalším specifickým požadavkem je možnost provádět druhů projekce pro sběr výsledků pro Homo sapiens nezávisle druhů, pro které identifikátory jsou k dispozici, aby prospěch z více kompletní Reactome anotace pro Člověka. K tomu je třeba vzít v úvahu druhy orthologs anotované v Reactome. Ortologové jsou entity různých druhů, které se vyvinuly ze společného předka speciací.

poslední požadavek v tomto kroku je sledovat identifikátory mapování mezi předloženy identifikátory, a ty, které se používají v Reactome, aby kaplan jednotlivých subjektů: UniProt přistoupení pro proteiny, Ensembl identifikátor pro geny, CHEBI identifikátory pro malé molekuly a miRBase pro mikrorna. Ačkoli důležitá část tohoto mapování začala zahrnutím známých křížových odkazů jako identifikátorů do stromu radix v předchozím kroku, samotné mapování musí být implementováno v tomto kroku.

Shrnující vystaveny požadavky pro tento krok analýzy, zvolené datové struktury musí model entity složení problém, druh orthologs projekce a subjekty mapování. Směrovaný graf je graf nebo sada uzlů Spojených hranami, kde hrany mají s nimi spojený směr. Pro daný graf G s několika uzly (a, b, c A d), pokud má G šipku od a do b a další šipku od b do c, pak složený graf G 2 má šipku od a do c. Pokud G má šipku z a do b, další šipka z b do c a další z c do d, pak složený graf G 3 má šipku z a do d.

Stavební jednom grafu pro každý druh (Obr. 2a) a propojení všech z nich spojující všechny ortholog uzly (obr. 2b) vytvoří větší graf, kde je pak splněn požadavek na projekci. Vzhledem k uzlu jedinečnost v konečném grafu, pro ty případy, kdy uzel je součástí jednoho nebo více strukturované subjekty, které obsahuje tolik hrany směřující na jiné uzly grafu jako struktury, v nichž je obsažen, takže strukturovaných jednotkách jsou snadno modelovat. Konečně, pokud každý uzel grafu obsahuje hlavní identifikátor přidružené entity (obr. 2c), když je dosaženo z uzlu stromu radix představujícího jiný identifikátor než hlavní, je tato asociace uložena, aby mohla být nabídnuta jako součást výsledku jako požadované mapování po dokončení analýzy.

br. 2

Graf zastoupení, kde P jsou bílkoviny; C jsou komplexy, Y jsou množiny a předseda uzly jsou stejné, ale u jiných druhů. jeden druh graf. b vztah mezi dvěma druhy. c obsah základního uzlu

graf na obr. 2a ukazuje tři proteiny (P1, P2 a P3), dva komplexy (C1 a C2) a dvě sady (S1 a S2). Sledováním okraje od uzlu k uzlu může být S2 buď P2 nebo P3, formálně reprezentováno jako . C1 je komplex, který je díky své hraně od S2 potenciálně dva komplexy: {P1, P2} nebo {P1,P3}, reprezentované jako . Po této dekonstrukci je pak S1 a nakonec C2 .

například, když identifikátor odpovídající s P3 je zpracován a jeho odpovídající uzlu v grafu je dosaženo z radix stromu, to trvá minimální čas zpracování procházet graf a dosáhnout uzlů S2, C1, C1 a C2. Podobně, pokud je cílový protein P1, dosažitelné uzly následující po okrajích grafu jsou C1, S1 a C2. V obou příkladech je každý cílový protein součástí komplexů a množin reprezentovaných projetými uzly.

Zaměstnávat graf zlepšuje algoritmu analýzy nákladů a důležité v budování in-memory analýzy, využití paměti je stále nízké, protože tam není žádný duplikaci dat jako uzel pro daný hlavní identifikátor je pouze v paměti jen jednou. Kromě toho, konečný počet uzlů iterace algoritmu je omezena propojenými osobami za daný identifikátor, vyhnout se dotazování na velké množství dat a průběžné výsledky sloučení, jak je provedeno v databázi přístup.

pokud jde o výše popsaný strom radix, graf také vyžaduje strategii, která umožní algoritmu přejít k dalšímu kroku analýzy. V tomto případě bude každý uzel grafu představující entitu přímo přidruženou k jedné nebo několika cestám obsahovat tolik odkazů na následující datovou strukturu jako různá místa, kde je přítomen. Ačkoli v aktuálním kroku analýzy je nalezena každá entita přidružená k cílovému identifikátoru, pro konečný výsledek a výpočet statistik je třeba použít ještě jednu datovou strukturu, jak je vysvětleno v následující části.

výsledky agregace do organizace cest

každý PE, který byl přímo nebo nepřímo zasažen v předchozím kroku, je spojen s jednou nebo více cestami. Pro výpočet významnosti každé cesty, pro daný vzorek uživatele, je nezbytné určit počet entit nalezených na cestu. Vzhledem k organizaci cest Reaktomu rodič-dítě v hierarchii podobné ontologii, je-li entita přítomna v určité dráze, je také přítomna ve svých super-drahách rekurzivním způsobem, dokud není dosaženo cesty nejvyšší úrovně (tj. pokud je protein přítomen v „metabolismu sacharidů“, je také přítomen v „metabolismu“).

s ohledem na požadavky dříve diskutovali, dobré datové struktury modelu tento krok je dvojí-spojené strom, kde každý uzel představuje cestu, a obsahuje odkazy na své rodiče a děti (Obr. 3). Když je zasažen uzel ve stromu, může být akce rekurzivně propagována až do kořene. Aby se snížila paměťová stopa, jsou v každém uzlu uchovávány pouze identifikátory, názvy a zástupné symboly pro výpočet výsledků.

br. 3

Double-linked stromu představují události hierarchie v Reactome. Kořenový uzel definuje druh a jeho děti představují různé cesty a sub-dráhy v Reactome. Každý uzel obsahuje cestu identifikátor, název, celkový kurátor subjektů a počet subjektů nalézt v uživatelské vzorku

Kromě toho, že vhodné datové struktury pro urychlení sběru výsledků a dobrý držák na statistiky, výsledky, jakmile je analýza dokončena, tato datová struktura také může být serializovány do souboru přetrvávat výsledek. Navíc, příponu souboru do tokenu poskytuje snadný způsob, jak vytvořit jemnější metody, které umožňují filtrování výsledků na straně serveru, aby se pomoci urychlit lehké klienty. V tomto scénáři mohou klienti ponechat token po dokončení počáteční analýzy a v závislosti na potřebách uživatele provést několik požadavků na server odkazující na přidružený token.

Analýza výsledku výpočet statistiky

základní hypotéza v průběhu zastupování analýzy je, že příslušné spoje mohou být detekovány v případě, že podíl rozdílně vyjádřené geny v dané dráhy, převyšuje podíl genů, které by mohly být náhodně se očekávalo . V důsledku toho čtvrtý a poslední krok metody analýzy zahrnuje výpočet statistik. Tento krok nevyžaduje žádnou další datovou strukturu, protože dvojitě propojený strom dokonale odpovídá účelu.

hodnota p ukazuje statistickou významnost každé dráhy zásahu pro daný vzorek a pozadí, pro které byla analýza provedena. V Reactome metodou použitou pro výpočet statistické významnosti je Binomický Test. Spolu s hodnotou p pomáhá False Discovery Rate (FDR) odhadnout falešně pozitivní výsledky a vypočítá se pomocí přístupu Benjamini-Hochberg. Jak již bylo zmíněno výše, zaměřili jsme se na optimalizaci výkonu analýzy Reactome pathway, při zachování základního algoritmu, jak bylo dříve publikováno .