a Identificação de uma conveniente estrutura de dados para resolver um determinado problema é um dos principais fatores para atingir um alto desempenho do produto final. Como Skiena explica, escolher a estrutura de dados errada para o trabalho pode ser desastroso em termos de desempenho, mas identificar a melhor estrutura de dados geralmente não é tão crítico, porque pode haver várias escolhas que executam de forma semelhante.

baseado na regra de dividir para conquistar, o primeiro passo é dividir o problema de análise em diferentes sub-problemas simples o suficiente para ser resolvido em tempo polinomial, identificando uma estrutura de dados conveniente. Aqui, o algoritmo de análise pode ser dividido em quatro partes: (1) verificar se o usuário proteína/identificadores químicos estão presentes em Reactome, (2) para o presente, encontrando-se a peças de complexos e/ou conjuntos, bem como a espécie de projeção, (3) a agregação dos encontrados identificadores nos caminhos (e super-vias), onde estão presentes e, finalmente, (4) executar os testes estatísticos para calcular a probabilidade de que a associação entre a exemplo de identificadores e o caminho encontrado é devido ao acaso.

Mais adiante nesta seção cada parte é discutida em detalhes para determinar suas peculiaridades; expor a estrutura de dados escolhida e os mecanismos adotados para sua melhoria; e mostrar como conectar cada passo ao seguinte para chegar ao algoritmo de análise melhorado final. Outro ponto de ênfase para a otimização será o uso da memória de cada passo, de modo que as estruturas de dados preenchidos podem ser mantidos na memória para melhorar o desempenho dos algoritmos de passagem de dados implementados em cima deles.

user sample identifiers search in Reactome

Annotated physical entities (PE) in Reactome can be either single entities or complexes. As entidades únicas incluem proteínas, pequenas moléculas, RNA, DNA, carboidratos ou lípidos, enquanto complexos consistem de uma combinação de qualquer uma das entidades únicas, ou polímeros sintetizados a partir das entidades únicas. No entanto, além destas duas categorias principais, curadores em Reactome podem agrupar entidades relacionadas em conjuntos. PEs são os blocos de construção que mais tarde serão usados como entradas, saídas, catalisadores ou reguladores em reações.

identificadores ou números de adesão são usados para se referir inequivocamente a uma única entidade, mas os PEs têm slots diferentes para manter o identificador principal, o identificador secundário, as referências cruzadas, os sinónimos e outros identificadores. O slot principal identificador é sempre anotado manualmente pelos especialistas que curam dados em Reactome (curadores), e os outros slots podem ser preenchidos manualmente durante a Curação ou automaticamente povoados durante o processo de liberação. Esta estratégia permite armazenar identificadores para uma ampla gama de recursos: UniProt, ChEBI, Ensembl, miRBase, GenBank/EMBL/DDBJ, RefPep, RefSeq, EntrezGene, OMIM, InterPro, Affymetrix, Agilent, composto KEGG, Illumina, etc.

portanto, na primeira parte da análise, o principal requisito é melhorar o processo de descobrir se cada identificador na amostra do usuário corresponde a um ou muitos PEs em Reagome. Um identificador corresponde a uma PE se corresponder a algum dos identificadores armazenados nas diferentes faixas horárias mencionadas anteriormente. Na verdade, a melhor maneira de resolver este problema é seguindo a abordagem inversa; criar uma tabela de pesquisa com todos os PEs correspondentes por cada identificador cruzado referenciado no Reactome. Como consequência, outro requisito importante é minimizar o uso da memória para que os dados possam ser mantidos na memória para melhorar o tempo da consulta.

a seleção de uma boa estrutura de dados é então determinada por requisitos tanto para implementar uma tabela de pesquisa rápida e para manter o uso da memória baixo. Trie é uma estrutura de dados de árvore ordenada que é usada para armazenar um conjunto dinâmico ou array associativo onde as chaves são geralmente strings . Uma árvore radix é uma estrutura de dados Trie otimizada em espaço, onde cada nó com apenas uma criança é fundido com seu pai .

por um lado, uma árvore radix tem um uso relativamente baixo de memória para a tabela de pesquisa porque os prefixos comuns são compartilhados evitando a duplicação de dados (Fig. 1). Por outro lado, o custo de comparar uma chave de pesquisa para a igualdade com uma chave da estrutura de dados pode ser um custo dominante que não pode ser negligenciado. O algoritmo de pesquisa de string de árvore radix se encaixa com o propósito original do algoritmo de análise, porque a iteração sobre nós de árvore mantém o identificador de busca de tempo restrito ao comprimento de cada identificador e existência no Reactome alvo definido. Como consequência, no caso de o procurado identificador não está contido na estrutura de dados, não há necessidade de ler tudo isso, como acontece nos métodos de hash, onde o valor de hash da cadeia, tem de ser calculado, em cada caso, ao lê-lo inteiramente.

a Base da árvore de representação para os identificadores P60484, P60467, P60468, P29172, P11087, P11086, P10639, P10636, P10635, P10622, P10620, P12939, P12938, P12931, P05480, P05386, PTEN

Em resumo, uma vez que um nó da árvore é atingida após a base da árvore algoritmo de pesquisa para um determinado identificador, a presença ou ausência de referências aos PEs indica se o identificador associado está presente ou não no banco de dados. Na verdade, as mencionadas “referências a PE” são de fato ponteiros para nós na estrutura de dados escolhida para a próxima parte da análise.

Reactome uses unique primary identifiers for the PEs it references, in particular UniProt for proteins and ChEBI for chemical entities. Assim, se os usuários enviarem conjuntos de dados usando esses sistemas de referência, o mapeamento para PEs é direto. No entanto, na sequência de Pedidos Frequentes de utilizadores, também aceitamos dados de entrada com identificadores não únicos, em particular nomes de genes. Estes são, então, potencialmente mapeados para múltiplos PEs. Assim, cada nó alvo na árvore pode conter mais de um ponteiro para a próxima estrutura de dados.

complexos transversais / conjuntos composição e projecção da espécie

alcançar a entidade única associada para um dado identificador é o início do segundo passo na análise. Quando essas entidades individuais fazem parte de um complexo, elas também são um alvo nesta etapa da análise. Além das Entidades e complexos únicos, há outro tipo de PE chamado conjuntos que, juntamente com complexos, também devem ser considerados. Um conjunto é uma representação abstrata de um grupo de duas ou mais entidades que não estão interagindo uns com os outros, mas são funcionalmente equivalentes a situação em que o conjunto é usado, por exemplo, vários membros de uma família de enzimas que poderia potencialmente catalisar uma reação. Além disso, complexos e conjuntos também podem conter outros complexos e conjuntos, a fim de representar estruturas muito mais elaboradas causando a complexidade do problema a crescer.outro requisito específico é a possibilidade de realizar projeções de espécies para coletar os resultados para o Homo sapiens independentemente da espécie para a qual os identificadores são fornecidos, para beneficiar da anotação reativa mais completa para o ser humano. Para tal, devem ser tidas em conta as espécies ortológicas anotadas em Reactome. Ortólogos são entidades de diferentes espécies que evoluíram de um ancestral comum por especiação.

O último requisito neste passo é manter o registro dos identificadores de mapeamento entre os apresentados identificadores e aqueles usados em Reactome para organizar a entidades única: UniProt adesões para proteínas, Ensembl identificador de genes, CHEBI identificadores de moléculas pequenas e miRBase para microRNAs. Embora uma parte importante deste mapeamento tenha começado por incluir as referências cruzadas conhecidas como identificadores na árvore radix na etapa anterior, o mapeamento em si tem de ser implementado nesta etapa.resumindo os requisitos expostos para esta etapa da análise, a estrutura de dados escolhida tem que modelar o problema de composição das Entidades, a projeção de espécies ortológicas e o mapeamento de entidades. Um grafo dirigido é um grafo, ou conjunto de nós conectados por arestas, onde as arestas têm uma direção associada a elas. Para um dado grafo G com vários nós (A, b, c E d), Se G tem uma seta de a A b e outra seta de b A c, então o grafo composto g 2 tem uma seta de a A C. Se G tem uma seta de a A b, outra seta de b A c e ainda outra de c A d, Então o grafo composto g 3 tem uma seta de a A D.

construindo um grafo por espécie (Fig. 2a) e interconectando todos eles ligando todos os nós ortolog (Fig. 2b) cria um gráfico maior onde o requisito de projeção é então satisfeito. Devido à unicidade do nó no grafo final, para aqueles casos em que um nó é parte de uma ou mais entidades estruturadas, ele contém tantas arestas apontando para outros nós de grafos como estruturas em que ele está contido, então as entidades estruturadas são facilmente modeladas. Finalmente, se cada nó do grafo contiver o seu identificador principal da entidade associada(Fig. 2c), quando é alcançado a partir de um nó de árvore radix que representa um identificador diferente do principal, esta associação é armazenada a fim de ser oferecido como parte do resultado como o mapeamento necessário uma vez que a análise é concluída.

Gráfico de representação onde P são as proteínas; C são complexos, S são conjuntos e prime nós mesmos, mas para outras espécies. um gráfico de uma espécie. B relação entre duas espécies. c base node content

the graph in Fig. 2a mostra três proteínas (P1, P2 e P3), dois complexos (C1 e C2), e dois conjuntos (S1 e S2). Seguindo a aresta de nó para nó, S2 pode ser P2 ou P3, formalmente representado como . C1 é um complexo que, devido à sua aresta de S2, é então potencialmente dois complexos: {P1,P2} ou {P1,P3}, representados como . Após esta desconstrução, S1 é então e finalmente C2 é .

Por exemplo, quando um identificador compatível com P3 é processado e seu nó correspondente no grafo é alcançado a partir da árvore radix, ele leva tempo de processamento minúsculo para atravessar o grafo e chegar aos nós S2, C1, S1 e C2. Da mesma forma, se a proteína alvo é P1, os nós alcançáveis seguindo as bordas do grafo são C1, S1 e C2. Em ambos os exemplos cada proteína alvo é parte dos complexos e conjuntos representados pelos nós atravessados.

empregando um grafo melhora o custo do algoritmo de análise e, importante na construção de uma análise na memória, o uso da memória é mantido baixo porque não há duplicação de dados como o nó para um dado identificador principal está apenas na memória uma vez. Além disso, o número final de iterações de nós do algoritmo é limitado pelas entidades relacionadas para um dado identificador, evitando consultas contra uma grande quantidade de dados e resultados intermediários de fusão, como feito na abordagem baseada em banco de dados.

Como para a árvore de radix descrito acima, o grafo também requer uma estratégia para permitir que o algoritmo passe para a próxima etapa de análise. Neste caso, cada nó de grafo que representa uma entidade diretamente associada a uma ou várias vias conterá tantas ligações à seguinte estrutura de dados como diferentes locais onde ela está presente. Embora na fase de análise actual se encontre cada entidade associada ao identificador de destino, para o resultado final e o cálculo de estatísticas, ainda há mais uma estrutura de dados a utilizar, como explicado na subsecção seguinte.a agregação dos resultados na organização das vias

cada PE que foi directa ou indirectamente atingido no passo anterior está associada a uma ou mais vias. Para calcular o Significado de cada via, para uma dada amostra de usuário, é essencial determinar o número de entidades encontradas por via. Devido à organização pai-filho das vias reativas em uma hierarquia ontológica, quando uma entidade está presente em uma determinada via, ela também está presente em suas super-vias de uma maneira recursiva até que uma via de nível superior seja alcançada (i.e. se uma proteína está presente no “metabolismo dos carboidratos”, também está presente no “metabolismo”).

tendo em conta os requisitos anteriormente discutidos, uma boa estrutura de dados para modelar este passo é uma árvore de dupla ligação, onde cada nó representa um caminho e contém links para o seu pai e filhos(Fig. 3). Quando um nó na árvore é atingido, a ação pode ser propagada recursivamente até a raiz. Para reduzir a pegada de memória, apenas identificadores, nomes e substituições para o cálculo dos resultados são mantidos em cada nó.