Publicado

2018-01-01

Ensamblado de fragmentos de ADN utilizando un novedoso algoritmo de luciérnaga en GPU

DNA fragment assembling using a novel GPU firefly algorithm

DOI:

https://doi.org/10.15446/dyna.v85n204.60078

Palabras clave:

ensamblado de fragmentos de ADN, algoritmo de luciérnaga, unidades de procesamiento gráfico, optimización, paralelismo (es)
fragment assembly problem, firefly algorithm, graphics processing units, optimization, parallelism (en)

Descargas

Autores/as

El problema de ensamblado de fragmentos de cadenas de ácido desoxirribonucleico (Deoxyribonucleic Acid Fragment Assembly Problem, DNA-FAP) consiste en la reconstrucción de cadenas de ADN desde un conjunto de fragmentos tomados aleatoriamente. El DNA-FAP ha sido resuelto por diferentes autores utilizando distintos enfoques. Aunque se obtienen buenos resultados, el tiempo computacional asociado es alto. El algoritmo de luciérnaga (Firefly Algorithm, FA) es un modelo bioinspirado basado en el comportamiento de las luciérnagas. Al ser un algoritmo bioinspirado poblacional es posible generar un modelo paralelo del mismo sobre Unidades de Procesamiento Gráfico (Graphics Processing Units, GPU). En este trabajo un algoritmo de luciérnaga es diseñado especialmente para ser ejecutado sobre una arquitectura GPU de manera tal de acelerar el proceso computacional buscando resolver el DNA-FAP. A través de diferentes experimentos se demuestra la eficiencia computacional y la calidad de los resultados obtenidos.
The Deoxyribonucleic Acid Fragment Assembly Problem (DNA-FAP) consists in reconstruct a DNA chain from a set of fragments taken randomly. Several authors solved the DNA-FAP using different approaches. In general, although it was obtaining good results; the computational time associated is high. The Firefly Algorithm (FA) is a bioinspired model based on the behaviour of fireflies. Considering that FA is a population bioinspired algorithm is possible design a parallel model of itself on Graphics Processing. In this work, a FA especially development for its execution on GPU is presented in order to accelerate the computational process to solve the DNA-FAP. Through several experiments the efficiency of the algorithm and the quality of the results were demonstrated.

Descargas

Los datos de descargas todavía no están disponibles.

Citas

Baykasoglu, A. and Ozsoydan, F.B., An improved firefly algorithm for solving dynamic multidimensional knapsack problems. Expert Syst. Appl., 41(8), pp. 3712-3725, 2014. DOI: 10.1016/j.eswa.2013.11.040

Bojic, I., Podobnik, V., Ljubi, I., Jezic, G. and Kusek, M., A self-optimizing mobile network: Auto-tuning the network with firefly-synchronized agents. Information Sciences, 182(1), pp. 77-92, 2012. DOI: 10.1016/j.ins.2010.11.017

Chandrasekaran, K. and Sishaj, P.S., Network and reliability constrained unit commitment problem using binary real coded firefly algorithm. International Journal of Electrical Power & Energy Systems, 43(1), pp. 921-932, 2012. DOI: 10.1016/j.ijepes.2012.06.004

Chen, T. and Skiena, S.S., A case study in genome-level fragment assembly. BIOINF: Bioinformatics, 16, 2000.

Coull, S.E. and Szymanski, B.K., Sequence alignment for masquerade detection. Computational Statistics & Data Analysis, 52(8), pp. 4116-4131, 2008. DOI: doi.org/10.1016/j.csda.2008.01.022

de Paula, L. et al., Parallelization of a modified firefly algorithm using GPU for variable selection in a multivariate calibration problem. International Journal of Natural Computing Research (IJNCR), 4(1), pp. 31-42, 2014. DOI: /10.4018/ijncr.2014010103

Engle, M.L. and Burks, C., Artificially generated data sets for testing DNA sequence assembly algorithms, Genomics, Volume 16(1), pp. 286-288, 1993. DOI: 0.1006/geno.1993.1180

Farhoodnea, M., Mohamed, A., Shareef, H. and Zayandehroodi, H., Optimum placement of active power conditioners by a dynamic discrete firefly algorithm to mitigate the negative power quality effects of renewable energy-based generators. International Journal of Electrical Power & Energy Systems, 61(0), pp. 305-317, 2014. DOI: 10.1016/j.ijepes.2014.03.062

Firoz, J.S., Rahman, M.S. and Saha, T.K., Bee algorithms for solving dna fragment assembly problem with noisy and noiseless data. In Proceedings of the 14th Annual Conference on Genetic and Evolutionary Computation, GECCO’12, pp. 201-208, 2012. DOI: 10.1145/2330163.2330192

Fister, I., Fister, I. Jr., Yang, X.-S. and Brest, J., A comprehensive review of firefly algorithms. CoRR, abs/1312.6609, 2013.

Gandomi, A.H., Yang, X.-S., Talatahari, S. and Alavi, A.H., Firefly algorithm with chaos. Comm Nonlinear Sci Numer Simulat, 18(1), pp. 89- 98, 2013. DOI: 10.1016/j.cnsns.2012.06.009

García-Nieto, J.M., Olivera, A.C. and Alba, E., Optimal cycle program of traffic lights with particle swarm optimization. IEEE Transactions on Evolutionary Computation, 17(6), pp. 823-839, 2013. DOI: 10.1109/TEVC.2013.2260755

Green, P., Phrap, version 1.090518, [online], 2009, Available at: http://phrap.org.

Huang, X. and Madan, A., Cap3: A DNA sequence assembly program. Genome research, 9(9), pp. 868-877, 1999. DOI: 10.1101/gr.9.9.868

Husselmann, A.V. and Hawick, K.A., Parallel parametric optimisation with firefly algorithms on graphical processing units. World Congress in Computer Science, Computer Engineering, and Applied Computing, 2012.

Jati, G.K., Manurung, R. and Suyanto., Discrete firefly algorithm for traveling salesman problem: A new movement scheme. In Xin-She Y., Zhihua, C., Renbin, X., Amir, H.G. and Mehmet, K., eds., Swarm Intelligence and Bio-Inspired Computation, Elsevier, Oxford, pp. 295-312, 2013.

Jones, N.C. and Pevzner, P.A., Preface. An Introduction to bioinformatics algorithms. Massachusetts Institute of Technology, 2004.

Kirk, D.B. and Hwu, W.W., Programming massively parallel processors: A hands-on approach. Morgan Kaufmann Publishers Inc., San Francisco, CA, USA, 1st edition, 2010.

Knuth, D.E., The art of computer programming, Volume 3: (2Nd Ed.) Sorting and Searching. Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, USA, 1998.

Kothapalli, K., Shah, R. and Narayanan, P.J., GPU-accelerated genetic algorithms. Workshop on Parallel Architectures for Bio-ispired Algorithms in conjunction with Parallel Architectures and Compilation Techniques (PACT Workshop), pp. 27-34, 2010.

Kubalik, J., Buryan, P. and Wagner, L., Solving the DNA fragment assembly problem efficiently using iterative optimization with evolved hypermutations. Proceedings of the 12th annual conference on Genetic and evolutionary computation, 2010, pp. 213-214. DOI: 10.1145/1830483.1830522

Maher, B. et al., A firefly-inspired method for protein structure prediction in lattice models. Biomhc, 4(1), pp. 56-75, 2014. DOI: 10.3390/biom4010056

Mallén-Fullerton, G.M., Hughes, J.A., Houghten, S. and Fernández-Anaya, G., Benchmark datasets for the DNA fragment assembly problem. International Journal of Bio-Inspired Computation, 5(6), pp. 384-394, 2013. DOI: 10.1504/IJBIC.2013.058912

Mallén-Fullerton, G.M. and Fernández-Anaya, G., DNA fragment assembly using optimization. IEEE Congress on Evolutionary Computation, Cancun, 2013, pp. 1570-1577. DOI: 10.1109/CEC.2013.6557749

Meybodi, M.R., Farahani, S.M. and Nasiri, B., A multiswarm based firefly algorithm in dynamic environments. In Third international conference on signal processing systems (ICSPS 2011), pp. 68-72, Yantai, China, 2011.

Minetti, G. and Alba, E., Metaheuristic assemblers of DNA strands: Noiseless and noisy cases. Proceedings of the IEEE Congress on Evolutionary Computation (CEC2010), 2010, pp. 1-8. DOI: 10.1109/CEC.2010.5586524

Minetti, G., Leguizamón, G. and Alba, E., SAX: A new and efficient assembler for solving DNA fragment assembly problem. 2012 Argentine Symposium on Artificial Intelligence, 2012.

Mussi, L., Daolio, F. and Cagnoni, S., Evaluation of parallel particle swarm optimization algorithms within the CUDA architecture. Inf. Sci., 181(20), pp. 4642-4657, 2011. DOI: 10.1016/j.ins.2010.08.045

Myers, E.W., Sutton, G.G., Delcher, A.L., Dew, I.M., Fasulo, D.P., Flanigan, M.J., Kravitz, S.A., Mobarry, C.M., Reinert, K.H.J, Remington, K.A., et al., A whole-genome assembly of drosophila. Science, 287(5461), pp. 2196-2204, 2000. DOI: 10.1126/science.287.5461.2196

NVIDIA Corporation. NVIDIA CUDA C Programming Guide, 2011.

Osaba, E., Yang, X.-S., Díaz, F., Onieva, E., Masegosa, A.D. and Perallos, A., A discrete firefly algorithm to solve a rich vehicle routing problem modelling a newspaper distribution system with recycling policy. Soft Computing, pp. 1-14, 2016.

Pevzner, P., Computational molecular biology: An Algorithmic approach. MIT Press, 2000.

Parsons, R.J., Forrest, S. and Burks, C., Genetic algorithms, operators, and DNA fragment assembly. Machine Learning, 21(1-2), pp. 11-33, 1995. DOI: 10.1007/BF00993377, 10.1023/A:1022613513712

Peters, H., Schulz-Hildebrandt, O. and Luttenberger, N., Fast in-place sorting with CUDA based on bitonic sort. LNCS, 6067, pp. 403-410, 2009.

Pop, M., Shotgun sequence assembly. Advances in Computers, 60, pp. 193-248, 2004. DOI: 10.1016/S0065-2458(03)60006-9

Saito, M. and Matsumoto, M., Variants of Mersenne twister suitable for graphic processors. ACM Trans. Math. Softw., 39(2), pp. 1-12, 2013. DOI: 10.1145/2427023.2427029

Sayadi, M.K., Hafezalkotob, A. and Naini, S.G.J., Firefly-inspired algorithm for discrete optimization problems: An application to manufacturing cell formation. Journal of Manufacturing Systems, 32(1), pp. 78-84, 2013. DOI: 0.1016/j.jmsy.2012.06.004

Sutton, G.G., White, O., Adams, M.D. and Kerlavage, A.R., Tigrassembler: A new tool for assembling large shotgun sequencing projects. Genome Science and Technology, 1(1), pp. 9-19, 1995. DOI: 10.1089/gst.1995.1.9

Vidal, P., Luna, F. and Alba, E., Systolic neighborhood search on graphics processing units. Soft Computing, 18(1), pp. 125-142, 2014. DOI: 10.1007/s00500-013-1041-7

Vidal, P. and Olivera, A.C., A parallel discrete firefly algorithm on GPU for permutation combinatorial optimization problems. High Performance Computing, Communications in Computer and Information Science, 485, pp. 191-205. Springer, 2014.

Yang, X.-S., Nature-inspired metaheuristic algorithms. Luniver Press, 2008.

Yang, X-S., Firefly algorithms for multimodal optimization. In: Watanabe, O. and Zeugmann, T., eds., Stochastic algorithms: Foundations and applications, Lecture Notes in Computer Science, 5792, pp. 169-178, 2009. DOI: 10.1007/978-3-642-04944-6_14

Yang, X-S., Firefly algorithm, stochastic test functions and design optimisation. Int. J. Bio-Inspired Comput., 2(2), pp. 78-84, 2010. DOI: 10.1504/IJBIC.2010.032124

Yang, X-S. and He, X., Firefly algorithm: Recent advances and applications. Int. J. Swarm Intelligence, 1, pp. 36-50, 2013. DOI: 10.1504/IJSI.2013.055801

Yang, X-S., Hosseini, S.S.S. and Gandomi, A.H., Firefly algorithm for solving non-convex economic dispatch problems with valve loading effect. Appl. Soft Comput., 12(3), pp. 1180-1186, 2012. DOI: 10.1016/j.asoc.2011.09.017

Licencia

Derechos de autor 2018 DYNA

Creative Commons License

Esta obra está bajo una licencia internacional Creative Commons Atribución-NoComercial-SinDerivadas 4.0.

El autor o autores de un artículo aceptado para publicación en cualquiera de las revistas editadas por la facultad de Minas cederán la totalidad de los derechos patrimoniales a la Universidad Nacional de Colombia de manera gratuita, dentro de los cuáles se incluyen: el derecho a editar, publicar, reproducir y distribuir tanto en medios impresos como digitales, además de incluir en artículo en índices internacionales y/o bases de datos, de igual manera, se faculta a la editorial para utilizar las imágenes, tablas y/o cualquier material gráfico presentado en el artículo para el diseño de carátulas o posters de la misma revista.