Identificar una estructura de datos conveniente para resolver un problema dado es uno de los principales factores para lograr un producto final de alto rendimiento. Como explica Skiena, elegir la estructura de datos incorrecta para el trabajo puede ser desastroso en términos de rendimiento, pero identificar la mejor estructura de datos generalmente no es tan crítico, porque puede haber varias opciones que funcionan de manera similar.

Basado en la regla de dividir y conquistar, el primer paso es dividir el problema de análisis en diferentes subproblemas lo suficientemente simples como para ser resueltos en tiempo polinómico mediante la identificación de una estructura de datos conveniente. Aquí, el algoritmo de análisis se puede dividir en cuatro partes: (1) comprobar si los identificadores proteicos/químicos del usuario están presentes en el Reactoma, (2) para los actuales, encontrar si son partes de complejos y/o conjuntos, así como la proyección de especies, (3) agregar los identificadores encontrados en las vías (y super-vías) donde están presentes y, finalmente, (4) realizar pruebas estadísticas para calcular la probabilidad de que la asociación entre los identificadores de muestra y la vía encontrada se deba a un azar aleatorio.

Más adelante en esta sección, cada parte se discute en detalle para determinar sus particularidades; exponer la estructura de datos elegida y los mecanismos adoptados para su mejora; y mostrar cómo conectar cada paso con el siguiente para llegar al algoritmo de análisis mejorado final. Otro punto de énfasis para la optimización será el uso de memoria de cada paso, de modo que las estructuras de datos llenas se puedan mantener en memoria para mejorar el rendimiento de los algoritmos de recorrido de datos implementados encima de ellos.

Búsqueda de identificadores de ejemplo de usuario en Reactome

Las entidades físicas anotadas (PE) en Reactome pueden ser entidades individuales o complejas. Las entidades individuales incluyen proteínas, moléculas pequeñas, ARN, ADN, carbohidratos o lípidos, mientras que los complejos consisten en una combinación de cualquiera de las entidades individuales, o polímeros sintetizados a partir de las entidades individuales. Sin embargo, aparte de estas dos categorías principales, los curadores de Reactome pueden agrupar entidades relacionadas en conjuntos. Los PSA son los bloques de construcción que más adelante se utilizarán como entradas, salidas, catalizadores o reguladores en reacciones.Los identificadores o números de acceso

se utilizan para referirse inequívocamente a una sola entidad, pero los PEs tienen diferentes ranuras para contener el identificador principal, el identificador secundario, las referencias cruzadas, los sinónimos y otros identificadores. La ranura de identificación principal siempre es anotada manualmente por los expertos que curan los datos en Reactome (curadores), y las otras ranuras se pueden llenar manualmente durante la curación o rellenarse automáticamente durante el proceso de publicación. Esta estrategia permite almacenar identificadores para una amplia gama de recursos: UniProt, ChEBI, Ensembl, miRBase, GenBank / EMBL / DDBJ, RefPep, RefSeq, EntrezGene, OMIM, InterPro, Affymetrix, Agilent, Compuesto KEGG, Illumina, etc.

Por lo tanto, en la primera parte del análisis, el principal requisito es mejorar el proceso de averiguar si cada identificador en la muestra del usuario corresponde a uno o varios PEs en Reactome. Un identificador corresponde a un PE si coincide con alguno de los identificadores almacenados en las diferentes ranuras mencionadas anteriormente. De hecho, la mejor manera de resolver este problema es siguiendo el enfoque inverso; crear una tabla de búsqueda con todos los PEs correspondientes por cada identificador con referencia cruzada en Reactome. Como consecuencia, otro requisito importante es minimizar el uso de memoria para que los datos se puedan mantener en memoria para mejorar el tiempo de consulta.

La selección de una buena estructura de datos está determinada por los requisitos tanto para implementar una tabla de búsqueda rápida como para mantener bajo el uso de memoria. Un Trie es una estructura de datos de árbol ordenada que se utiliza para almacenar un conjunto dinámico o una matriz asociativa donde las claves suelen ser cadenas . Un árbol radix es una estructura de datos Trie optimizada para el espacio en la que cada nodo con un solo hijo se fusiona con su padre .

Por un lado, un árbol radix tiene un uso de memoria relativamente bajo para la tabla de búsqueda porque los prefijos comunes se comparten evitando la duplicación de datos (Fig. 1). Por otro lado, el costo de comparar una clave de búsqueda para la igualdad con una clave de la estructura de datos puede ser un costo dominante que no se puede descuidar. El algoritmo de búsqueda de cadenas de árbol radix se ajusta al propósito original del algoritmo de análisis porque la iteración sobre nodos de árbol mantiene el tiempo de búsqueda del identificador restringido a la longitud y existencia de cada identificador en el conjunto de objetivos del Reactoma. Como consecuencia de esto, en caso de que el identificador buscado no esté contenido en la estructura de datos, no hay necesidad de leerlo todo, como sucede en los métodos de hash, donde el valor hash de la cadena debe calcularse en cada caso leyéndolo por completo.

Representación de árbol de radios para los identificadores P60484, P60467, P60468, P29172, P11087, P11086, P10639, P10636, P10635, P10622, P10620, P12939, P12938, P12931, P05480, P05386, PTEN

En resumen, una vez que se alcanza un nodo de árbol siguiendo el algoritmo de búsqueda de árbol radix para un identificador dado, la presencia o ausencia de referencias a PEs indica si el identificador asociado está presente o no en la base de datos. En realidad, las mencionadas «referencias a PE» son de hecho punteros a nodos en la estructura de datos elegida para la siguiente parte del análisis.

Reactome utiliza identificadores primarios únicos para los PEs a los que hace referencia, en particular UniProt para proteínas y ChEBI para entidades químicas. Por lo tanto, si los usuarios envían conjuntos de datos utilizando estos sistemas de referencia, la asignación a PEs es sencilla. Sin embargo, a raíz de las frecuentes solicitudes de los usuarios, también aceptamos datos de entrada con identificadores no únicos, en particular nombres de genes. Estos se mapean potencialmente a varios SPe. Por lo tanto, cada nodo de destino en el árbol podría contener más de un puntero a la siguiente estructura de datos.

Atravesar la composición de complejos / conjuntos y la proyección de especies

Alcanzar la entidad única asociada para un identificador dado es el comienzo del segundo paso en el análisis. Cuando estas entidades forman parte de un complejo, también son un objetivo en este paso del análisis. Además de las entidades individuales y los complejos, hay otro tipo de EP llamado conjuntos que, junto con los complejos, también deben considerarse. Un conjunto es una representación abstracta de un grupo de dos o más entidades que no interactúan entre sí, pero son funcionalmente equivalentes en la situación en que se usa el conjunto, por ejemplo, múltiples miembros de una familia de enzimas que podrían catalizar una reacción. Además, los complejos y conjuntos también pueden contener otros complejos y conjuntos para representar estructuras mucho más elaboradas que hacen que la complejidad del problema crezca.

Otro requisito específico es la posibilidad de realizar proyecciones de especies para recoger los resultados de Homo sapiens independientemente de la especie para la que se proporcionan los identificadores, para beneficiarse de la anotación de Reactomas más completa para Humanos. Para ello, se deben tener en cuenta los ortólogos de especies anotados en Reactoma. Los ortólogos son entidades en diferentes especies que evolucionaron de un ancestro común por especiación.

El último requisito en este paso es realizar un seguimiento de la asignación de identificadores entre los identificadores enviados y los utilizados en Reactome para curar las entidades individuales: accesiones UniProt para proteínas, identificador Ensembl para genes, identificadores CHEBI para moléculas pequeñas y miRBase para microRNAs. Aunque una parte importante de esta asignación comenzó incluyendo las referencias cruzadas conocidas como identificadores en el árbol radix en el paso anterior, la asignación en sí tiene que implementarse en este paso.

Resumiendo los requisitos expuestos para esta etapa del análisis, la estructura de datos elegida tiene que modelar el problema de composición de entidades, la proyección de ortólogos de especies y el mapeo de entidades. Un grafo dirigido es un grafo, o conjunto de nodos conectados por aristas, donde las aristas tienen una dirección asociada a ellas. Para un gráfico G dado con varios nodos (a, b, c y d), si G tiene una flecha de a a b y otra flecha de b a c, entonces el gráfico compuesto G 2 tiene una flecha de a a c. Si G tiene una flecha de a a b, otra flecha de b a c y otra de c a d, entonces el gráfico compuesto G 3 tiene una flecha de a a d.

Construyendo un gráfico por especie (Fig. 2a) e interconectando todos ellos enlazando todos los nodos ortológicos (Fig. 2b) crea un gráfico más grande donde se satisface el requisito de proyección. Debido a la singularidad del nodo en el gráfico final, para aquellos casos en los que un nodo es parte de una o más entidades estructuradas, contiene tantos bordes que apuntan a otros nodos del gráfico como estructuras en las que está contenido, por lo que las entidades estructuradas se modelan fácilmente. Finalmente, si cada nodo del gráfico contiene su identificador principal de entidad asociada (Fig. 2c), cuando se llega desde un nodo de árbol radix que representa un identificador distinto del principal, esta asociación se almacena para ofrecerse como parte del resultado como la asignación requerida una vez finalizado el análisis.

Representación gráfica donde P son proteínas; C son complejos, S son conjuntos y los nodos primos son los mismos pero para otras especies. un gráfico de una especie. b Relación entre dos especies. contenido del nodo base c

El gráfico de la Fig. 2a muestra tres proteínas (P1, P2 y P3), dos complejos (C1 y C2) y dos conjuntos (S1 y S2). Siguiendo el borde de nodo a nodo, S2 podría ser P2 o P3, representado formalmente como . C1 es un complejo que, debido a su borde de S2,es entonces potencialmente dos complejos: {P1,P2} o {P1, P3}, representado como . Después de esta deconstrucción, S1 es entonces y finalmente C2 es .

Por ejemplo, cuando se procesa un identificador que coincide con P3 y se llega a su nodo correspondiente en el gráfico desde el árbol radix, se necesita un tiempo de procesamiento minúsculo para atravesar el gráfico y llegar a los nodos S2, C1, S1 y C2. Del mismo modo, si la proteína objetivo es P1, los nodos alcanzables que siguen los bordes del gráfico son C1, S1 y C2. En ambos ejemplos, cada proteína diana es parte de los complejos y conjuntos representados por los nodos atravesados.

El empleo de un gráfico mejora el costo del algoritmo de análisis y, importante en la construcción de un análisis en memoria, el uso de memoria se mantiene bajo porque no hay duplicación de datos, ya que el nodo para un identificador principal dado solo está en memoria una vez. Además, el número final de iteraciones de nodos del algoritmo está limitado por las entidades relacionadas para un identificador dado, evitando consultas contra una gran cantidad de datos y la fusión de resultados intermedios, como se hace en el enfoque basado en la base de datos.

En cuanto al árbol radix descrito anteriormente, el gráfico también requiere una estrategia para permitir que el algoritmo pase al siguiente paso de análisis. En este caso, cada nodo de gráfico que representa una entidad directamente asociada a una o varias rutas contendrá tantos enlaces a la siguiente estructura de datos como diferentes ubicaciones donde está presente. Aunque en el paso de análisis actual se encuentra cada entidad asociada con el identificador de destino, para el resultado final y el cálculo estadístico, todavía hay una estructura de datos más a utilizar, como se explica en la siguiente subsección.

Agregación de resultados en la organización de las vías

Cada EP que fue afectada directa o indirectamente en el paso anterior está asociada a una o más vías. Para calcular la importancia de cada vía, para una muestra de usuario dada, es esencial determinar el número de entidades encontradas por vía. Debido a la organización padre-hijo de las vías del Reactoma en una jerarquía similar a una ontología, cuando una entidad está presente en una determinada vía, también está presente en sus super-vías de manera recursiva hasta que se alcanza una vía de nivel superior (i. e. si una proteína está presente en el» Metabolismo de los carbohidratos», también está presente en el»Metabolismo»).

Teniendo en cuenta los requisitos discutidos anteriormente, una buena estructura de datos para modelar este paso es un árbol de doble enlace, donde cada nodo representa una ruta y contiene enlaces a su padre e hijos (Fig. 3). Cuando se golpea un nodo en el árbol, la acción se puede propagar recursivamente hasta la raíz. Para reducir la huella de memoria, solo se guardan identificadores, nombres y marcadores de posición para el cálculo de resultados en cada nodo.

haga Doble vinculado árbol para representar el evento de jerarquía en Reactome. El nodo raíz que define a la especie y sus hijos representan las diferentes vías y sub-vías en Reactome. Cada nodo contiene el identificador de ruta, el nombre, el total de entidades curadas y el número de entidades encontradas en la muestra del usuario

Además de ser una estructura de datos conveniente para acelerar la recopilación de resultados y un buen soporte para los resultados estadísticos, una vez finalizado el análisis, esta estructura de datos también se puede serializar en un archivo para conservar el resultado. Además, asociar el archivo a un token proporciona una forma fácil de crear métodos de grano más fino que permiten filtrar el resultado en el lado del servidor para ayudar a acelerar los clientes livianos. En este escenario, los clientes pueden conservar el token una vez finalizado el análisis inicial y, dependiendo de las necesidades del usuario, realizar varias solicitudes al servidor que hacen referencia al token asociado.

Cálculo estadístico de resultados del análisis

La hipótesis básica en un análisis de sobre-representación es que se pueden detectar vías relevantes si la proporción de genes expresados diferencialmente, dentro de una vía dada, excede la proporción de genes que se podrían esperar aleatoriamente . En consecuencia, el cuarto y último paso del método de análisis implica el cálculo estadístico. Este paso no requiere ninguna estructura de datos adicional porque el árbol de doble enlace se ajusta perfectamente al propósito.

El valor p muestra la significación estadística de cada vía de respuesta positiva para una muestra dada y el fondo para el que se ha realizado el análisis. En Reactome, el método utilizado para calcular la significación estadística es la Prueba Binomial. Junto con el Valor p, la Tasa de Descubrimiento Falso (FDR) ayuda a estimar los falsos positivos y se calcula utilizando el enfoque Benjamini-Hochberg . Como se mencionó anteriormente, nos hemos centrado en optimizar el rendimiento del análisis de la vía del Reactoma, manteniendo el algoritmo básico publicado anteriormente .