Um Algoritmo Exato em clusters de GPUs para o Hitting Set Aplicado a Inferencia de Redes de Regulacao Genica
We propose a Hitting Set problem (HSP) algorithm suited for GRN inference applications by introducing innovations in the data structures and a sorting scheme to allow efficient discarding of Hitting Set non solution candidates. We provided an implementation for multi core CPUs and for (homogeneous and heterogeneous) GPU clusters. Experimental results show that the optimizations offered significant individual performance gains and a high scalability with increasing number of GPUs. The conjunction of these gains resulted in speedups above 60 for the parallel part of the algorithm. We publish two papers: one in conference (Qualis CC A1) and the other in journal (Qualis CC A2) Resumo. Propomos um algoritmo para resolver o problema do Hitting Set (HSP) adequado para aplicacoes de inferencia de GRNs, introduzindo inovacoes nas estruturas de dados e um mecanismo de ordenacao que permite um descarte eficiente de candidatos que nao sao solucao. Foram providas implementacoes em CPU multi core e em clusters (homogeneos e heterogeneos) de GPU. Resultados experimentais mostraram que as otimizacoes ofereceram ganhos de desempenho individuais significativos e alta escalabilidade com o aumento do numero de GPUs. A conjuncao desses ganhos resultou em speedups acima de 60 para a parte paralela do algoritmo. Publicamos dois artigos: um em congresso (Qualis CC A1) e outro em periodico (Qualis CC A2) 1. Introducao e Motivacao Diversas areas de estudo possuem problemas teoricos ou praticos os quais podem ser modelados, em parte ou como um todo, como uma instancia do problema da Transversal Minima (do Ingles, Hitting Set Problem ou HSP) A area de Biologia de Sistemas nao e uma excecao, apresentando aplicacoes tais como distancia reversa genomica [Kolman and Walen 2007] experimentos com reacao em cadeia de polimerase [Pearson et al. 1996] e inferencia de redes de regulacao genica (do Ingles Gene Regulatory Networks ou GRNs) [Ideker et al. 2000, Ruchkys and Song 2003] Ideker et al. [Ideker et al. 2000] por exemplo, utiliza uma abordagem iterativa de perturbacao de sinais, na qual se aplicam perturbacoes sucessivas nos niveis de expressao dos genes e as *Financiado pelo CNPq 6.720 (4000 x 1.68) (about R$ 17.440 lesser or 72.18% So, with the application of the complete model, the cost total to correct the essays would be R$ 5.360 (4000 x 1.34) a reduction of R$ 18.800 or 77,81% compared to the traditional model or reduction of R$ 1.360 or 20.23% compared to the model without gamification. Now, imagine the gains if increase the number of schools, which means more students or increase the amount of essays performed by student.