Die Identifizierung einer geeigneten Datenstruktur zur Lösung eines bestimmten Problems ist einer der Hauptfaktoren, um ein hochleistungsfähiges Endprodukt zu erzielen. Wie Skiena in erklärt , Die Auswahl der falschen Datenstruktur für den Job kann in Bezug auf die Leistung katastrophal sein, aber die Ermittlung der besten Datenstruktur ist normalerweise nicht so kritisch, weil es mehrere Möglichkeiten geben kann, die ähnlich funktionieren.

Basierend auf der Divide and Conquer-Regel besteht der erste Schritt darin, das Analyseproblem in verschiedene Teilprobleme aufzuteilen, die einfach genug sind, um in Polynomzeit gelöst zu werden, indem eine geeignete Datenstruktur identifiziert wird. Hier kann der Analysealgorithmus in vier Teile unterteilt werden: (1) Überprüfen, ob die Protein- / chemischen Identifikatoren des Benutzers im Reaktom vorhanden sind, (2) für die vorliegenden, Feststellen, ob es sich um Teile von Komplexen und / oder Sätzen sowie um die Speziesprojektion handelt, (3) Aggregieren der gefundenen Identifikatoren in den Pfaden (und Super-Pfaden), in denen diese vorhanden sind, und schließlich (4) Durchführen der statistischen Tests zur Berechnung der Wahrscheinlichkeit, dass die Assoziation zwischen den Probenidentifikatoren und dem gefundenen Pfad zufällig ist.

Weiter in diesem Abschnitt wird jeder Teil im Detail diskutiert, um seine Besonderheiten zu bestimmen; die gewählte Datenstruktur und die Mechanismen für ihre Verbesserung aufzudecken; und zu zeigen, wie man jeden Schritt mit dem folgenden verbindet, um den endgültigen verbesserten Analysealgorithmus zu entwickeln. Ein weiterer Schwerpunkt für die Optimierung wird die Speichernutzung jedes Schritts sein, so dass die gefüllten Datenstrukturen im Speicher gehalten werden können, um die Leistung der darauf implementierten Datendurchlaufalgorithmen zu verbessern.

User sample identifiers search in Reactome

Annotierte physikalische Entitäten (PE) in Reactome können entweder einzelne Entitäten oder Komplexe sein. Einzelne Entitäten umfassen Proteine, kleine Moleküle, RNA, DNA, Kohlenhydrate oder Lipide, während Komplexe aus einer Kombination einer der einzelnen Entitäten oder aus den einzelnen Entitäten synthetisierten Polymeren bestehen. Abgesehen von diesen beiden Hauptkategorien können Kuratoren in Reactome verwandte Entitäten in Gruppen gruppieren. PEs sind die Bausteine, die später als Inputs, Outputs, Katalysatoren oder Regler in Reaktionen eingesetzt werden.

Identifikatoren oder Beitrittsnummern werden verwendet, um eindeutig auf eine einzelne Entität zu verweisen, aber PEs haben unterschiedliche Slots, um die Hauptkennung, die sekundäre Kennung, Querverweise, Synonyme und andere Kennungen aufzunehmen. Der Haupt-ID-Slot wird immer manuell von den Experten kommentiert, die Daten in Reactome kuratieren (Kuratoren), und die anderen Slots können entweder während der Kuration manuell gefüllt oder während des Freigabeprozesses automatisch gefüllt werden. Diese Strategie ermöglicht das Speichern von Bezeichnern für eine Vielzahl von Ressourcen: UniProt, ChEBI, Ensembl, miRBase, GenBank/EMBL/DDBJ, RefPep, RefSeq, EntrezGene, OMIM, InterPro, Affymetrix, Agilent, KEGG Verbindung, Illumina, etc.

Daher besteht die Hauptanforderung im ersten Teil der Analyse darin, den Prozess zu verbessern, um herauszufinden, ob jeder Identifikator in der Probe des Benutzers einem oder mehreren PEs in Reactome entspricht. Ein Identifikator entspricht einem PE, wenn er mit einem der Identifikatoren übereinstimmt, die in den verschiedenen zuvor erwähnten Slots gespeichert sind. Tatsächlich ist der beste Weg, dieses Problem zu lösen, der umgekehrte Ansatz; erstellen einer Nachschlagetabelle mit allen entsprechenden PEs pro Bezeichner, auf die in Reactome verwiesen wird. Infolgedessen besteht eine weitere wichtige Anforderung darin, die Speichernutzung zu minimieren, damit die Daten im Speicher gehalten werden können, um die Abfragezeit zu verbessern.

Die Auswahl einer guten Datenstruktur wird dann durch die Anforderungen bestimmt, sowohl eine schnelle Nachschlagetabelle zu implementieren als auch die Speichernutzung gering zu halten. Ein Trie ist eine geordnete Baumdatenstruktur, die zum Speichern eines dynamischen Satzes oder assoziativen Arrays verwendet wird, in dem die Schlüssel normalerweise Zeichenfolgen sind. Ein Radix-Baum ist eine raumoptimierte Trie-Datenstruktur, bei der jeder Knoten mit nur einem Kind mit seinem übergeordneten Element zusammengeführt wird.

Einerseits hat ein Radix-Baum eine relativ geringe Speichernutzung für die Nachschlagetabelle, da die gemeinsamen Präfixe gemeinsam genutzt werden, um Datenduplizierung zu vermeiden (Abb. 1). Andererseits können die Kosten für den Vergleich eines Suchschlüssels auf Gleichheit mit einem Schlüssel aus der Datenstruktur dominante Kosten sein, die nicht vernachlässigt werden können. Der Radix Tree String Lookup-Algorithmus passt zum ursprünglichen Zweck des Analysealgorithmus, da die Iteration über Baumknoten die Identifikatorsuchzeit auf die Länge und Existenz jedes Identifikators im Reaktom-Zielsatz beschränkt hält. Wenn der gesuchte Bezeichner nicht in der Datenstruktur enthalten ist, muss er nicht vollständig gelesen werden, wie dies bei den Hashing-Methoden der Fall ist, bei denen der Hash-Wert der Zeichenfolge in jedem Fall durch vollständiges Lesen berechnet werden muss.

Radix-Baumdarstellung für die Bezeichner P60484, P60467, P60468, P29172, P11087, P11086, P10639, P10636, P10635, P10622, P10620, P12939, P12938, P12931, P05480, P05386, PTEN

Zusammenfassend zeigt das Vorhandensein oder Nichtvorhandensein von Verweisen auf PEs, sobald ein Baumknoten nach dem Radix-Baumsuchalgorithmus für einen gegebenen Bezeichner erreicht ist, an, ob der zugehörige Bezeichner im Baumknoten vorhanden ist oder nicht datenbank. Tatsächlich sind die erwähnten „Referenzen auf PE“ tatsächlich Zeiger auf Knoten in der Datenstruktur, die für den nächsten Teil der Analyse ausgewählt wurden.

Reactome verwendet eindeutige primäre Identifikatoren für die PEs, auf die es verweist, insbesondere UniProt für Proteine und ChEBI für chemische Entitäten. Wenn Benutzer Datensätze mit diesen Referenzsystemen einreichen, ist die Zuordnung zu PEs einfach. Aufgrund häufiger Nutzeranfragen akzeptieren wir jedoch auch Eingabedaten mit nicht eindeutigen Kennungen, insbesondere Gennamen. Diese werden dann möglicherweise mehreren PEs zugeordnet. Somit könnte jeder Zielknoten im Baum mehr als einen Zeiger auf die nächste Datenstruktur enthalten.

Durchqueren von Komplexen / Mengenzusammensetzung und Speziesprojektion

Das Erreichen der zugehörigen einzelnen Entität für einen bestimmten Identifikator ist der Beginn des zweiten Schritts in der Analyse. Wenn diese einzelnen Entitäten Teil eines Komplexes sind, sind sie auch ein Ziel in diesem Schritt der Analyse. Neben den einzelnen Entitäten und Komplexen gibt es eine andere Art von Entitäten, die als Sets bezeichnet werden und zusammen mit Komplexen ebenfalls zu berücksichtigen sind. Eine Menge ist eine abstrakte Darstellung einer Gruppe von zwei oder mehr Entitäten, die nicht miteinander interagieren, aber in der Situation, in der die Menge verwendet wird, funktionell äquivalent sind, z. B. mehrere Mitglieder einer Familie von Enzymen, die jeweils eine Reaktion katalysieren könnten. Darüber hinaus können Komplexe und Mengen auch andere Komplexe und Mengen enthalten, um viel aufwändigere Strukturen darzustellen, wodurch die Komplexität des Problems zunimmt.Eine weitere spezifische Anforderung ist die Möglichkeit, Artenprojektionen durchzuführen, um die Ergebnisse für Homo sapiens unabhängig von der Art, für die die Identifikatoren bereitgestellt werden, zu sammeln, um von der vollständigeren Reaktom-Annotation für den Menschen zu profitieren. Dazu müssen die im Reactome annotierten Spezies-Orthologen berücksichtigt werden. Orthologe sind Entitäten in verschiedenen Arten, die sich durch Artbildung aus einem gemeinsamen Vorfahren entwickelt haben.

Die letzte Anforderung in diesem Schritt besteht darin, die Zuordnung der Identifikatoren zwischen den eingereichten Identifikatoren und denen zu verfolgen, die in Reactome verwendet werden, um die einzelnen Entitäten zu kuratieren: UniProt-Akzessionen für Proteine, Ensembl-Identifikatoren für Gene, CHEBI-Identifikatoren für kleine Moleküle und miRBase für microRNAs. Obwohl ein wichtiger Teil dieses Mappings damit begann, im vorherigen Schritt die bekannten Querverweise als Bezeichner in den Radixbaum aufzunehmen, muss das Mapping selbst in diesem Schritt implementiert werden.

Zusammenfassend die Anforderungen für diesen Schritt der Analyse, muss die gewählte Datenstruktur das Problem der Entitätszusammensetzung, die Projektion der Artenorthologien und die Zuordnung der Entitäten modellieren. Ein gerichteter Graph ist ein Graph oder eine Menge von Knoten, die durch Kanten verbunden sind, wobei den Kanten eine Richtung zugeordnet ist. Wenn G für einen gegebenen Graphen G mit mehreren Knoten (a, b, c und d) einen Pfeil von a nach b und einen anderen Pfeil von b nach c hat, dann hat der zusammengesetzte Graph G2 einen Pfeil von a nach c. Wenn G einen Pfeil von a nach b, einen weiteren Pfeil von b nach c und noch einen weiteren von c nach d hat, dann hat der zusammengesetzte Graph G3 einen Pfeil von a nach d.

Aufbau eines Graphen pro Spezies (Abb. 2a) und alle miteinander verbinden, die alle Ortholog-Knoten (Fig. 2b) erzeugt ein größeres Diagramm, in dem die Projektionsanforderung dann erfüllt ist. Aufgrund der Eindeutigkeit des Knotens im endgültigen Diagramm enthält ein Knoten in den Fällen, in denen er Teil einer oder mehrerer strukturierter Entitäten ist, so viele Kanten, die auf andere Diagrammknoten zeigen, wie Strukturen, in denen er enthalten ist, sodass strukturierte Entitäten leicht modelliert werden können. Wenn schließlich jeder Knoten des Graphen seine zugehörige Entitätshauptidentifikation enthält (Abb. 2c) wird diese Zuordnung, wenn sie von einem Radix-Baumknoten aus erreicht wird, der eine andere Kennung als die Hauptkennung darstellt, gespeichert, um nach Abschluss der Analyse als Teil des Ergebnisses als erforderliche Zuordnung angeboten zu werden.

Graphendarstellung, wobei P Proteine sind; C sind Komplexe, S sind Mengen und Primknoten sind die gleichen, aber für andere Spezies. eine Art Graph. b Beziehung zwischen zwei Arten. c Basisknoteninhalt

Die Grafik in Abb. 2a zeigt drei Proteine (P1, P2 und P3), zwei Komplexe (C1 und C2) und zwei Sätze (S1 und S2). Durch Folgen der Kante von Knoten zu Knoten könnte S2 entweder P2 oder P3 sein, formal dargestellt als . C1 ist ein Komplex, der aufgrund seiner Kante von S2 dann potentiell zwei Komplexe ist: {P1,P2} oder {P1,P3}, dargestellt als . Nach dieser Dekonstruktion ist dann S1 und schließlich C2 .

Wenn beispielsweise ein mit P3 übereinstimmender Bezeichner verarbeitet wird und sein entsprechender Knoten im Diagramm vom Radixbaum aus erreicht wird, dauert es nur eine winzige Verarbeitungszeit, um den Graphen zu durchlaufen und die Knoten S2, C1, S1 und C2 zu erreichen. Ebenso, wenn das Zielprotein P1 ist, sind die erreichbaren Knoten, die den Graphenkanten folgen, C1, S1 und C2. In beiden Beispielen ist jedes Zielprotein Teil der Komplexe und Mengen, die durch die durchquerten Knoten dargestellt werden.

Die Verwendung eines Graphen verbessert die Kosten des Analysealgorithmus und, wichtig beim Aufbau einer In-Memory-Analyse, wird die Speichernutzung niedrig gehalten, da es keine Datenduplizierung gibt, da sich der Knoten für eine bestimmte Hauptkennung nur einmal im Speicher befindet. Darüber hinaus ist die endgültige Anzahl der Knoteniterationen des Algorithmus durch die zugehörigen Entitäten für einen bestimmten Bezeichner begrenzt, wodurch Abfragen gegen eine große Datenmenge und das Zusammenführen von Zwischenergebnissen vermieden werden, wie dies beim datenbankbasierten Ansatz der Fall ist.

Wie für den oben beschriebenen Radixbaum erfordert der Graph auch eine Strategie, damit der Algorithmus zum nächsten Analyseschritt übergehen kann. In diesem Fall enthält jeder Diagrammknoten, der eine Entität darstellt, die direkt einem oder mehreren Pfaden zugeordnet ist, so viele Links zu der folgenden Datenstruktur wie verschiedene Orte, an denen er vorhanden ist. Obwohl im aktuellen Analyseschritt jede der Zielkennung zugeordnete Entität gefunden wird, muss für das Endergebnis und die Statistikberechnung noch eine weitere Datenstruktur verwendet werden, wie im folgenden Unterabschnitt erläutert.

Ergebnisaggregation in die Pathways-Organisation

Jeder PE, der im vorherigen Schritt direkt oder indirekt getroffen wurde, ist einem oder mehreren Pathways zugeordnet. Um die Signifikanz jedes Pathways für eine bestimmte Benutzerstichprobe zu berechnen, ist es wichtig, die Anzahl der gefundenen Entitäten pro Pathway zu bestimmen. Aufgrund der Eltern-Kind-Organisation der Reaktomwege in einer ontologieähnlichen Hierarchie ist eine Entität, wenn sie in einem bestimmten Weg vorhanden ist, auch in ihren Superwegen rekursiv vorhanden, bis ein Pfad der obersten Ebene erreicht ist (z. wenn ein Protein im „Kohlenhydratstoffwechsel“ vorhanden ist, ist es auch im „Stoffwechsel“ vorhanden).

Unter Berücksichtigung der zuvor diskutierten Anforderungen ist eine gute Datenstruktur zum Modellieren dieses Schritts ein doppelt verknüpfter Baum, wobei jeder Knoten einen Pfad darstellt und Links zu seinen Eltern und Kindern enthält (Abb. 3). Wenn ein Knoten im Baum getroffen wird, kann die Aktion rekursiv bis zur Wurzel weitergegeben werden. Um den Speicherbedarf zu reduzieren, werden in jedem Knoten nur Bezeichner, Namen und Platzhalter für die Ergebnisberechnung gespeichert.

Doppelt verknüpfter Baum zur Darstellung der Ereignishierarchie in Reactome. Der Wurzelknoten definiert die Spezies und seine Kinder repräsentieren die verschiedenen Wege und Unterwege in Reactome. Jeder Knoten enthält die Pfadkennung, den Namen, die Gesamtzahl der Entitäten und die Anzahl der Entitäten, die in der Stichprobe des Benutzers gefunden wurden

Abgesehen davon, dass diese Datenstruktur eine bequeme Datenstruktur zur Beschleunigung der Sammlung von Ergebnissen und ein guter Halter für die Statistikergebnisse ist, kann sie nach Abschluss der Analyse auch in eine Datei serialisiert werden, um das Ergebnis beizubehalten. Darüber hinaus bietet das Zuordnen der Datei zu einem Token eine einfache Möglichkeit, feinkörnigere Methoden zu erstellen, mit denen das Ergebnis auf der Serverseite gefiltert werden kann, um leichte Clients zu beschleunigen. In diesem Szenario können die Clients das Token behalten, sobald die anfängliche Analyse abgeschlossen ist, und abhängig von den Anforderungen des Benutzers mehrere Anforderungen an den Server ausführen, die auf das zugehörige Token verweisen.

Analyse Ergebnis Statistik Berechnung

Die grundlegende Hypothese in einer Überrepräsentation Analyse ist, dass relevante Signalwege nachgewiesen werden können, wenn der Anteil der differentiell exprimierten Gene, innerhalb eines gegebenen Weges, übersteigt den Anteil der Gene, die zufällig erwartet werden könnte . Folglich beinhaltet der vierte und letzte Schritt in der Analysemethode die Statistikberechnung. Dieser Schritt erfordert keine zusätzliche Datenstruktur, da der doppelt verknüpfte Baum perfekt zum Zweck passt.

Der p-Wert zeigt die statistische Signifikanz jedes Trefferwegs für eine gegebene Probe und den Hintergrund, für den die Analyse durchgeführt wurde. In Reactome Die Methode zur Berechnung der statistischen Signifikanz ist der Binomialtest. Zusammen mit dem p-Wert hilft die False Discovery Rate (FDR) bei der Schätzung der False Positives und wird mit dem Benjamini-Hochberg-Ansatz berechnet . Wie bereits erwähnt, haben wir uns darauf konzentriert, die Leistung der Reaktomweganalyse zu optimieren und dabei den zuvor veröffentlichten Grundalgorithmus beizubehalten .