Um Algoritmo Exato em clusters de GPUs para o Hitting Set Aplicado à Inferência de Redes de Regulação Gênica
Resumo
Propomos um algoritmo para resolver o problema do Hitting Set (HSP), adequado para aplicações de inferência de GRNs, introduzindo 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. Foram providas implementações em CPU multi-core e em clusters (homogêneos e heterogêneos) de GPU. Resultados experimentais mostraram que as otimizações ofereceram ganhos de desempenho individuais significativos e alta escalabilidade com o aumento do número de GPUs. A conjunção 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 periódico (Qualis CC A2).
Referências
Barrera, J., Cesar-Jr, R. M., Martins-Jr, D. C., Vencio, R. Z. N., Merino, E. F., Yamamoto, M. M., Leonardi, F. G., Pereira, C. A. B., and del Portillo, H. A. (2007). Constructing probabilistic genetic networks of Plasmodium falciparum from dynamical expression signals of the intraerythrocytic development cycle. In Methods of Microarray Data Analysis V, chapter 2, pages 11–26. Springer.
Borelli, F. F., Camargo, R. Y., Martins, D. C., Stransky, B., and Rozante, L. C. (2012). Accelerating gene regulatory networks inference through gpu/cuda programming. In Computational Advances in Bio and Medical Sciences (ICCABS), 2012 IEEE 2nd International Conference on, pages 1–6. IEEE.
Cendic, B. L. (2014). A genetic algorithm for the minimum hitting set. Scientific Publications of the State University of Novi Pazar, 6(2):107.
Garey, M. R. and Johnson, D. S. (1999). Computers and Intractability - A guide to the Theory of NP-completeness. W. H. Freeman and Company.
Ideker, T. E., Thorsson, V., and Karp, R. M. (2000). Discovery of regulatory interactions through perturbation: inference and experimental design. Pacific symposium on biocomputing, 5:302–313.
Kauffman, S. A. (1969). Homeostasis and differentiation in random genetic control networks. Nature, 224(215):177–178.
Kauffman, S. A. (1993). The Origins of Order. Oxford University Press, New York.
Kolman, P. and Walen, T. (2007). Reversal distance for strings with duplicates: Linear time approximation using hitting set. The Electronic Journal of Combinatorics, 14(1):11.
Madhamshettiwar, P. B., Maetschke, S. R., Davis, M. J., Reverter, A., and Ragan, M. A. (2012). Gene regulatory network inference: evaluation and application to ovarian cancer allows the prioritization of drug targets. Genome medicine, 4(5):1–16.
Pearson, W. R., Robins, G., Wrege, D. E., and Zhang, T. (1996). On the primer selection problem in polymerase chain reaction experiments. Discrete Applied Mathematics, 71(1):231–246.
Ristevski, B. (2013). A survey of models for inference of gene regulatory networks. Nonlinear Analysis: Modelling and Control, 18(4):444–465.
Ruchkys, D. P. and Song, S. W. (2003). A parallel solution to infer genetic network architectures in gene expression analysis. International Journal of High Performance Computing Applications, 17(2):163–172.
Shi, H., Schmidt, B., Liu, W., and Muller-Wittig, W. (2011). Parallel mutual information estimation for inferring gene regulatory networks on gpus. BMC Research Notes, 4:189.
Shi, L. and Cai, X. (2010). An exact fast algorithm for minimum hitting set. Int. Joint Conference on Computational Science and Optimization, 1:64–67.
Steinbach, B. and Posthoff, C. (2012). Sources and obstacles for parallelization-a comprehensive exploration of the unate covering problem using both CPU and GPU. GPU Computing with Applications in Digital Logic, page 63.
Borelli, F. F., Camargo, R. Y., Martins, D. C., Stransky, B., and Rozante, L. C. (2012). Accelerating gene regulatory networks inference through gpu/cuda programming. In Computational Advances in Bio and Medical Sciences (ICCABS), 2012 IEEE 2nd International Conference on, pages 1–6. IEEE.
Cendic, B. L. (2014). A genetic algorithm for the minimum hitting set. Scientific Publications of the State University of Novi Pazar, 6(2):107.
Garey, M. R. and Johnson, D. S. (1999). Computers and Intractability - A guide to the Theory of NP-completeness. W. H. Freeman and Company.
Ideker, T. E., Thorsson, V., and Karp, R. M. (2000). Discovery of regulatory interactions through perturbation: inference and experimental design. Pacific symposium on biocomputing, 5:302–313.
Kauffman, S. A. (1969). Homeostasis and differentiation in random genetic control networks. Nature, 224(215):177–178.
Kauffman, S. A. (1993). The Origins of Order. Oxford University Press, New York.
Kolman, P. and Walen, T. (2007). Reversal distance for strings with duplicates: Linear time approximation using hitting set. The Electronic Journal of Combinatorics, 14(1):11.
Madhamshettiwar, P. B., Maetschke, S. R., Davis, M. J., Reverter, A., and Ragan, M. A. (2012). Gene regulatory network inference: evaluation and application to ovarian cancer allows the prioritization of drug targets. Genome medicine, 4(5):1–16.
Pearson, W. R., Robins, G., Wrege, D. E., and Zhang, T. (1996). On the primer selection problem in polymerase chain reaction experiments. Discrete Applied Mathematics, 71(1):231–246.
Ristevski, B. (2013). A survey of models for inference of gene regulatory networks. Nonlinear Analysis: Modelling and Control, 18(4):444–465.
Ruchkys, D. P. and Song, S. W. (2003). A parallel solution to infer genetic network architectures in gene expression analysis. International Journal of High Performance Computing Applications, 17(2):163–172.
Shi, H., Schmidt, B., Liu, W., and Muller-Wittig, W. (2011). Parallel mutual information estimation for inferring gene regulatory networks on gpus. BMC Research Notes, 4:189.
Shi, L. and Cai, X. (2010). An exact fast algorithm for minimum hitting set. Int. Joint Conference on Computational Science and Optimization, 1:64–67.
Steinbach, B. and Posthoff, C. (2012). Sources and obstacles for parallelization-a comprehensive exploration of the unate covering problem using both CPU and GPU. GPU Computing with Applications in Digital Logic, page 63.
Publicado
04/07/2016
Como Citar
DOS SANTOS, Danilo Carastan; ROZANTE, Luiz Carlos da Silva.
Um Algoritmo Exato em clusters de GPUs para o Hitting Set Aplicado à Inferência de Redes de Regulação Gênica. In: CONCURSO DE TESES E DISSERTAÇÕES (CTD), 29. , 2016, Porto Alegre.
Anais [...].
Porto Alegre: Sociedade Brasileira de Computação,
2016
.
p. 387-392.
ISSN 2763-8820.
DOI: https://doi.org/10.5753/ctd.2016.9136.
