Orientador: Prof. Dr. Luiz Carlos da Silva Rozante / Dissertação (mestrado) - Universidade Federal do ABC, Programa de Pós-Graduação em Ciência da Computação, 2015. / A inferência de redes de regulação gênica é um dos problemas cruciais no campo de
Biologia de Sistemas. É ainda um problema em aberto, principalmente devido à alta dimensionalidade
(milhares de genes) com um número limitado de amostras (dezenas), tornando
difícil estimar dependências entre genes. Além do problema de estimação, outro obstáculo é
a inerente complexidade computacional dos métodos de inferência de GRNs. Este trabalho
teve como foco contornar problemas de desempenho de uma técnica baseada em perturbação de sinais para inferir dependências entre genes. Um dos passos principais consiste em resolver o problema da Transversal Mínima (do Inglês Hitting Set, ou HSP), o qual é NPDifícil.
Existem diversas propostas para se obter soluções aproximadas ou exatas para esse
problema. Uma dessas propostas consiste em um algoritmo baseado em GPU (Graphical
Processing Unit) para se obter as soluções exatas do HSP. Entretanto, tal método não é
escalável para GRNs de tamanho real. Foi proposto nesse trabalho, portanto, uma extensão
desse algoritmo para resolver o HSP, que é capaz de lidar com conjuntos de entrada contendomilhares de variáveis, pela introdução de inovações nas estruturas de dados e um mecanismo de ordenação que permite um descarte eficiente de candidatos que não são solução do HSP. Foi provida uma implementação em CPU multi-core e em clusters de GPU. Os resultados experimentais mostraram que o uso do mecanismo de ordenação fornece speedups de até 3,5 na implementação em CPU. Além disso, utilizando uma única GPU, foi obtido um speedup adicional de até 4,7, em comparação com uma implementação multithreaded em CPU. Porfim, o uso de oito GPUs de um cluster de GPU forneceu um speedup adicional de até 6,6. Combinando todas as técnicas, foram obtidos speedups acima de 60 para a parte paralela do algoritmo. / Gene regulatory networks inference is one of the crucial problems of the Systems Biology
field. It is still an open problem, mainly because of its high dimensionality (thousands
of genes) with a limited number of samples (dozens), making it difficult to estimate dependenciesamong genes. Besides the estimation problem, another important hindrance is
the inherent computational complexity of GRN inference methods. In this work, we focus
on circumventing performance issues of a technique based on signal perturbations to infer
gene dependencies. One of its main steps consists in solving the Hitting Set problem (HSP),
which is NP-Hard. There are many proposals to obtain approximate or exact solutions to
this problem. One of these proposals consists of a Graphical Processing Unit (GPU) based
algorithm to obtain exact solutions to the HSP. However, such method is not scalable for real
size GRNs. We propose an extension of the HSP algorithm to deal with input sets containing
thousands of variables by introducing innovations in the data structures and a sorting
scheme to allow efficient discarding of Hitting Set non-solution candidates. We provide an
implementation for multi-core CPUs and GPU clusters. Our experimental results show that
the usage of the sorting scheme brings speedups of up to 3.5 in the CPU implementation.
Moreover, using a single GPU, we could obtain an additional speedup of up to 4.7, in comparison with the multithreaded CPU implementation. Finally, usage of eight GPUs from a
GPU cluster brought an additional speedup of up to 6.6. Combining all techniques, speedups
above 60 were obtained for the parallel part of the algorithm.
| Identifer | oai:union.ndltd.org:IBICT/oai:BDTD:77320 |
| Date | January 2015 |
| Creators | Santos, Danilo Carastan dos |
| Contributors | Rozante, Luiz Carlos da Silva, Camargo, Raphael Yokoingawa de, Adi, Said Sadique, Song, Siang Wun, Martins Junior, David Corrêa |
| Source Sets | IBICT Brazilian ETDs |
| Language | Portuguese |
| Detected Language | Portuguese |
| Type | info:eu-repo/semantics/publishedVersion, info:eu-repo/semantics/masterThesis |
| Format | application/pdf, 52 f. : il. |
| Source | reponame:Repositório Institucional da UFABC, instname:Universidade Federal do ABC, instacron:UFABC |
| Rights | info:eu-repo/semantics/openAccess |
| Relation | http://biblioteca.ufabc.edu.br/index.php?codigo_sophia=77320&midiaext=70724, http://biblioteca.ufabc.edu.br/index.php?codigo_sophia=77320&midiaext=70723, Cover: http://biblioteca.ufabc.edu.brphp/capa.php?obra=77320 |
Page generated in 0.002 seconds