Um Algoritmo Exato em clusters de GPUs para o Hitting Set Aplicado à Inferência de Redes de Regulação Gênica

• Danilo Carastan dos Santos UFABC
• Luiz Carlos da Silva Rozante UFABC

DOI: https://doi.org/10.5753/ctd.2016.9136

Abstract

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).

References

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.