Identyfikacja wygodnej struktury danych do rozwiązania danego problemu jest jednym z głównych czynników do osiągnięcia wysokiej wydajności produktu końcowego. Jak wyjaśnia Skiena, wybranie niewłaściwej struktury danych do zadania może być katastrofalne pod względem wydajności, ale identyfikacja najlepszej struktury danych zwykle nie jest tak krytyczna, ponieważ może być kilka wyborów, które działają podobnie.

opierając się na zasadzie dziel i rządź, pierwszym krokiem jest rozbicie problemu analizy na różne problemy na tyle proste, że można je rozwiązać w czasie wielomianowym, identyfikując wygodną strukturę danych. Tutaj algorytm analizy można podzielić na cztery części: (1) sprawdzenie, czy identyfikatory białek/substancji chemicznych użytkownika są obecne w Reactomie, (2) dla obecnych, ustalenie, czy są to części kompleksów i/lub zestawów, jak również projekcja gatunków, (3) agregowanie znalezionych identyfikatorów w szlakach (i super szlakach), w których są obecne, i wreszcie (4) przeprowadzenie testów statystycznych w celu obliczenia prawdopodobieństwa, że związek między identyfikatorami próbki a znalezioną szlakiem wynika z przypadkowego przypadku.

w dalszej części tej sekcji każda część jest szczegółowo omówiona w celu określenia jej specyfiki; aby odsłonić wybraną strukturę danych i mechanizmy przyjęte do jej ulepszenia; i pokazać, jak połączyć każdy krok z następnym, aby wymyślić ostateczny ulepszony algorytm analizy. Kolejnym punktem nacisku na optymalizację będzie wykorzystanie pamięci każdego kroku, tak aby wypełnione struktury danych mogły być przechowywane w pamięci, aby poprawić wydajność algorytmów przetwarzania danych zaimplementowanych na nich.

user sample identifiers search in Reactome

Annotated physical entities (PE) in Reactome can be single entities or complexes. Pojedyncze jednostki obejmują białka, małe cząsteczki, RNA, DNA, węglowodany lub lipidy, podczas gdy kompleksy składają się z kombinacji dowolnych pojedynczych jednostek lub polimerów syntetyzowanych z pojedynczych jednostek. Jednak oprócz tych dwóch głównych kategorii, kuratorzy w Reactome mogą grupować powiązane byty w zbiory. PEs są budulcem, który później będzie używany jako wejścia, wyjścia, katalizatory lub regulatory w reakcjach.

identyfikatory lub numery akcesyjne są używane do jednoznacznego odniesienia do jednego podmiotu, ale PEs mają różne czasy na przechowywanie głównego identyfikatora, wtórnego identyfikatora, odsyłaczy, synonimów i innych identyfikatorów. Główny slot identyfikatora jest zawsze ręcznie adnotowany przez ekspertów, którzy zarządzają danymi w Reactome (kuratorzy), a pozostałe sloty mogą być ręcznie wypełniane podczas kuratorowania lub automatycznie wypełniane podczas procesu uwalniania. Ta strategia umożliwia przechowywanie identyfikatorów dla szerokiego zakresu zasobów: UniProt, ChEBI, Ensembl, miRBase, GenBank / EMBL / DDBJ, RefPep, RefSeq, EntrezGene, OMIM, InterPro, Affymetrix, Agilent, KEGG Compound, Illumina itp.

dlatego w pierwszej części analizy głównym wymogiem jest usprawnienie procesu sprawdzania, czy każdy identyfikator w próbce użytkownika odpowiada jednemu lub wielu PEs w Reactome. Identyfikator odpowiada PE, jeśli pasuje do któregokolwiek z identyfikatorów przechowywanych w różnych slotach wymienionych powyżej. W rzeczywistości najlepszym sposobem rozwiązania tego problemu jest zastosowanie odwrotnego podejścia; Tworzenie tabeli wyszukiwania ze wszystkimi odpowiadającymi PEs dla każdego identyfikatora, do którego odwołuje się w Reactome. W konsekwencji innym ważnym wymogiem jest zminimalizowanie zużycia pamięci, aby dane mogły być przechowywane w pamięci, aby poprawić czas zapytań.

wybór dobrej struktury danych jest następnie określany przez wymagania zarówno do implementacji szybkiej tabeli wyszukiwania, jak i do utrzymania niskiego zużycia pamięci. Trie jest uporządkowaną strukturą danych drzewa, która jest używana do przechowywania dynamicznego zestawu lub tablicy asocjacyjnej, gdzie klucze są zwykle ciągami . Drzewo radix to zoptymalizowana przestrzennie struktura danych Trie, w której każdy węzeł z tylko jednym potomkiem jest scalany z rodzicem .

z jednej strony Drzewo radix ma stosunkowo niskie zużycie pamięci dla tabeli wyszukiwania, ponieważ wspólne przedrostki są współdzielone, unikając duplikacji danych (rys. 1). Z drugiej strony, koszt porównania klucza wyszukiwania dla równości z kluczem ze struktury danych może być kosztem dominującym, którego nie można pominąć. Algorytm Radix tree string lookup pasuje do pierwotnego celu algorytmu analizy, ponieważ iteracja nad węzłami drzewa utrzymuje czas poszukiwania identyfikatora ograniczony do długości każdego identyfikatora i istnienia w zestawie docelowym Reactome. W związku z tym, w przypadku, gdy poszukiwany identyfikator nie jest zawarty w strukturze danych, nie ma potrzeby odczytywania go całego, jak to ma miejsce w metodach haszujących, gdzie wartość hash łańcucha musi być obliczona w każdym przypadku przez jego całkowite odczytanie.

Podsumowując, po osiągnięciu węzła drzewa po algorytmie wyszukiwania drzewa Radix dla danego identyfikatora, obecność lub brak odniesień do PES wskazuje, czy powiązany identyfikator jest obecny w bazie danych. W rzeczywistości wspomniane „odniesienia do PE” są rzeczywiście wskaźnikami do węzłów w strukturze danych wybranej do następnej części analizy.

Reactome używa unikalnych identyfikatorów pierwotnych dla PEs, do których się odwołuje, w szczególności UniProt dla białek i ChEBI dla jednostek chemicznych. Tak więc, jeśli użytkownicy przesyłają zbiory danych za pomocą tych systemów referencyjnych, mapowanie do PEs jest proste. Jednakże, po częstych żądaniach użytkowników, akceptujemy również dane wejściowe z nie unikalnymi identyfikatorami, w szczególności nazwami genów. Następnie są one potencjalnie mapowane do wielu PEs. Tak więc każdy węzeł docelowy w drzewie może zawierać więcej niż jeden wskaźnik do następnej struktury danych.

przemierzanie składu kompleksów/zestawów i projekcji gatunków

dotarcie do powiązanej pojedynczej jednostki dla danego identyfikatora jest początkiem drugiego etapu analizy. Gdy te pojedyncze jednostki są częścią kompleksu, są one również celem na tym etapie analizy. Oprócz pojedynczych Bytów i kompleksów, istnieje inny rodzaj PE zwany zbiorami, które wraz z kompleksami również należy rozpatrywać. Zbiór jest abstrakcyjną reprezentacją grupy dwóch lub więcej bytów, które nie oddziałują ze sobą, ale są funkcjonalnie równoważne w sytuacji, w której zestaw jest używany, na przykład wielu członków rodziny enzymów, z których każdy może potencjalnie katalizować reakcję. Co więcej, kompleksy i zestawy mogą również zawierać inne kompleksy i zestawy, aby reprezentować znacznie bardziej skomplikowane struktury powodujące wzrost zawiłości problemu.

innym specyficznym wymogiem jest możliwość przeprowadzenia projekcji gatunków w celu zebrania wyników dla Homo sapiens niezależnie od gatunków, dla których dostarczane są identyfikatory, aby skorzystać z pełniejszej adnotacji Reaktomu dla człowieka. W tym celu należy wziąć pod uwagę ortologie gatunkowe opisane w Reactome. Ortologowie są bytami u różnych gatunków, które wyewoluowały ze wspólnego przodka przez specjację.

ostatnim wymogiem w tym kroku jest śledzenie mapowania identyfikatorów między przedłożonymi identyfikatorami i tymi używanymi w Reactome do zarządzania pojedynczymi jednostkami: dostępy UniProt dla białek, identyfikator Ensembl dla genów, identyfikatory CHEBI dla małych cząsteczek i miRBase dla mikroRNA. Chociaż ważna część tego mapowania rozpoczęła się od włączenia znanych odsyłaczy jako identyfikatorów w drzewie radix w poprzednim kroku, samo mapowanie musi zostać zaimplementowane w tym kroku.

Podsumowując narażone wymagania dla tego etapu analizy, wybrana struktura danych musi modelować problem składu jednostek, projekcję ortologów gatunków i mapowanie jednostek. Graf kierowany to Graf lub zbiór węzłów połączonych krawędziami, w których krawędzie mają związany z nimi kierunek. Dla danego grafu G z kilkoma węzłami (a, b, c I d), jeśli G ma strzałkę od a do b i inną strzałkę od b do c, to złożony Graf g 2 ma strzałkę od a do c. Jeśli G ma strzałkę od a do b, kolejną strzałkę od b do c i jeszcze jedną strzałkę od c do d, to złożony Wykres g 3 ma strzałkę od a do d.

budowanie jednego grafu na gatunek (rys. 2a) i łącząc je wszystkie łącząc wszystkie węzły ortologi (rys. 2B) tworzy większy wykres, w którym wymóg projekcji jest spełniony. Ze względu na wyjątkowość węzła w końcowym grafie, w przypadkach, w których węzeł jest częścią jednego lub więcej strukturyzowanych elementów, zawiera tyle krawędzi skierowanych do innych węzłów grafu, ile struktur, w których jest zawarty, więc strukturyzowane elementy są łatwo modelowane. Wreszcie, jeśli każdy węzeł wykresu zawiera powiązany z nim główny identyfikator podmiotu (rys. 2C), gdy zostanie osiągnięty z węzła drzewa radix reprezentującego identyfikator inny niż główny, to skojarzenie jest przechowywane, aby być oferowane jako część wyniku jako wymagane mapowanie po zakończeniu analizy.

wykres na Rys. 2a wykazuje trzy białka (P1, P2 i P3), dwa kompleksy (C1 i C2) oraz dwa zestawy (S1 i S2). Idąc wzdłuż krawędzi od węzła do węzła, S2 może być albo P2 albo P3, formalnie reprezentowane jako . C1 jest kompleksem, który ze względu na swoją krawędź od S2, jest wtedy potencjalnie dwoma kompleksami: {P1,P2} lub {P1,P3}, reprezentowanymi jako . Po tej dekonstrukcji S1 jest wtedy, a w końcu C2 jest.

na przykład, gdy identyfikator pasujący do P3 jest przetwarzany, a jego odpowiedni węzeł w grafie jest osiągany z drzewa radix, Przejście grafu i dotarcie do węzłów S2, C1, S1 i C2 zajmuje niewielki czas przetwarzania. Podobnie, jeśli docelowym białkiem jest P1, osiągalne węzły po krawędziach grafu to C1, S1 i C2. W obu przykładach każde białko docelowe jest częścią kompleksów i zestawów reprezentowanych przez przemieszczone węzły.

wykorzystanie grafu poprawia koszt algorytmu analizy i, ważne w budowaniu analizy w pamięci, zużycie pamięci jest utrzymywane na niskim poziomie, ponieważ nie ma duplikacji danych, ponieważ węzeł dla danego głównego identyfikatora jest tylko raz w pamięci. Ponadto ostateczna liczba iteracji węzłów algorytmu jest ograniczona przez powiązane jednostki dla danego identyfikatora, unikając zapytań dotyczących dużej ilości danych i pośrednich wyników scalania, jak to ma miejsce w podejściu opartym na bazie danych.

Jeśli chodzi o drzewo radix opisane powyżej, Wykres wymaga również strategii, aby algorytm mógł przejść do następnego etapu analizy. W takim przypadku każdy węzeł grafu reprezentujący jednostkę bezpośrednio związaną z jedną lub kilkoma ścieżkami będzie zawierał tyle linków do poniższej struktury danych, ile różnych lokalizacji, w których jest obecny. Chociaż w bieżącym etapie analizy znajduje się każdy podmiot powiązany z identyfikatorem celu, dla końcowego wyniku i obliczeń statystycznych nadal należy zastosować jeszcze jedną strukturę danych, jak wyjaśniono w poniższej podsekcji.

wyniki agregacji do organizacji ścieżek

każdy PE, który został bezpośrednio lub pośrednio uderzony w poprzednim kroku, jest powiązany z jednym lub kilkoma ścieżkami. Aby obliczyć znaczenie każdej ścieżki, dla danej próbki Użytkownika, istotne jest określenie liczby jednostek znalezionych na ścieżce. Ze względu na organizację rodzic-dziecko ścieżek Reaktomu w hierarchii podobnej do ontologii, gdy jednostka jest obecna w określonej ścieżce, jest również obecna w swoich super-ścieżkach w sposób rekurencyjny, dopóki ścieżka najwyższego poziomu nie zostanie osiągnięta (tj. jeśli białko jest obecne w „metabolizmie węglowodanów”, jest również obecne w”metabolizmie”).

biorąc pod uwagę wcześniej omówione wymagania, dobrą strukturą danych do modelowania tego kroku jest podwójnie połączone drzewo, gdzie każdy węzeł reprezentuje ścieżkę i zawiera łącza do swojego rodzica i dzieci (rys. 3). Gdy węzeł w drzewie zostanie trafiony, akcja może być rekurencyjnie propagowana aż do korzenia. Aby zmniejszyć ilość pamięci, w każdym węźle przechowywane są tylko identyfikatory, nazwy i symbole zastępcze do obliczania wyników.

oprócz tego, że jest wygodną strukturą danych przyspieszającą zbieranie wyników i dobrym nośnikiem wyników statystycznych, po zakończeniu analizy, ta struktura danych może być również serializowana do pliku, aby utrzymać wynik. Ponadto powiązanie pliku z tokenem zapewnia łatwy sposób tworzenia drobnoziarnistych metod, które umożliwiają filtrowanie wyniku po stronie serwera, aby przyspieszyć działanie lekkich klientów. W tym scenariuszu klienci mogą zatrzymać token po zakończeniu wstępnej analizy i w zależności od potrzeb użytkownika wykonać kilka żądań do serwera odwołujących się do powiązanego tokena.

analiza wynik statystyka kalkulacja

podstawową hipotezą w analizie nadreprezentatywnej jest to, że odpowiednie szlaki mogą być wykryte, jeśli udział genów różnicowo wyrażonych, w ramach danej ścieżki, przekracza udział genów, które mogą być losowo oczekiwane . W związku z tym czwarty i ostatni etap metody analizy obejmuje obliczenia statystyczne. Ten krok nie wymaga żadnej dodatkowej struktury danych, ponieważ podwójnie połączone drzewo idealnie pasuje do celu.

wartość p pokazuje istotność statystyczną każdego szlaku przebytego dla danej próbki oraz tło, dla którego przeprowadzono analizę. W Reaktomie metodą stosowaną do obliczania istotności statystycznej jest test Dwumianowy. Wraz z wartością p Współczynnik fałszywego wykrywania (FDR) pomaga oszacować fałszywie dodatnie wyniki i jest obliczany przy użyciu metody Benjamini-Hochberga . Jak wspomniano wcześniej, skupiliśmy się na optymalizacji wydajności analizy ścieżki Reactome, przy zachowaniu podstawowego algorytmu, jak wcześniej opublikowano .