Ir al contenido

Documat

DNA fragment assembling using a novel GPU firefly algorithm

  • Pablo Javier Vidal [1] ; Ana Carolina Olivera [1]
    1. [1] Universidad Nacional de la Patagonia Austral

      Universidad Nacional de la Patagonia Austral

      Argentina

  • Localización: DYNA: revista de la Facultad de Minas. Universidad Nacional de Colombia. Sede Medellín, ISSN 0012-7353, Vol. 85, Nº. 204, 2018, págs. 108-116
  • Idioma: inglés
  • DOI: 10.15446/dyna.v85n204.60078
  • Títulos paralelos:
    • Ensamblado de fragmentos de ADN utilizando un novedoso algoritmo de luciérnaga en GPU
  • Enlaces
  • Resumen
    • español

      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). Eneste 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 eficienciacomputacional y la calidad de los resultados obtenidos.

    • English

      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; thecomputational time associated is high. The Firefly Algorithm (FA) is a bioinspired model based on the behaviour of fireflies.Considering that FAis 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.

  • Referencias bibliográficas
    • Baykasoglu, A. and Ozsoydan, F.B., An improved firefly algorithm for solving dynamic multidimensional knapsack problems. Expert Syst. Appl.,...
    • Bojic, I., Podobnik, V., Ljubi, I., Jezic, G. and Kusek, M., A self-optimizing mobile network: Auto-tuning the network with firefly-synchronized...
    • Chandrasekaran, K. and Sishaj, P.S., Network and reliability constrained unit commitment problem using binary real coded firefly algorithm....
    • 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,...
    • de Paula, L. et al., Parallelization of a modified firefly algorithm using GPU for variable selection in a multivariate calibration problem....
    • Engle, M.L. and Burks, C., Artificially generated data sets for testing DNA sequence assembly algorithms, Genomics, Volume 16(1), pp. 286-288,...
    • Farhoodnea, M., Mohamed, A., Shareef, H. and Zayandehroodi, H., Optimum placement of active power conditioners by a dynamic discrete firefly...
    • 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...
    • 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-...
    • García-Nieto, J.M., Olivera, A.C. and Alba, E., Optimal cycle program of traffic lights with particle swarm optimization. IEEE Transactions...
    • 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...
    • Jati, G.K., Manurung, R. and Suyanto., Discrete firefly algorithm for traveling salesman problem: A new movement scheme. In Xin-She Y., Zhihua,...
    • 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,...
    • Knuth, D.E., The art of computer programming, Volume 3: (2Nd Ed.) Sorting and Searching. Addison Wesley Longman Publishing Co., Inc., Redwood...
    • Kothapalli, K., Shah, R. and Narayanan, P.J., GPU-accelerated genetic algorithms. Workshop on Parallel Architectures for Bio-ispired Algorithms...
    • Kubalik, J., Buryan, P. and Wagner, L., Solving the DNA fragment assembly problem efficiently using iterative optimization with evolved hypermutations....
    • 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...
    • Mallén-Fullerton, G.M. and Fernández-Anaya, G., DNA fragment assembly using optimization. IEEE Congress on Evolutionary Computation, Cancun,...
    • Meybodi, M.R., Farahani, S.M. and Nasiri, B., A multiswarm based firefly algorithm in dynamic environments. In Third international conference...
    • Minetti, G. and Alba, E., Metaheuristic assemblers of DNA strands: Noiseless and noisy cases. Proceedings of the IEEE Congress on Evolutionary...
    • Minetti, G., Leguizamón, G. and Alba, E., SAX: A new and efficient assembler for solving DNA fragment assembly problem. 2012 Argentine Symposium...
    • Mussi, L., Daolio, F. and Cagnoni, S., Evaluation of parallel particle swarm optimization algorithms within the CUDA architecture. Inf. Sci.,...
    • 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,...
    • 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...
    • 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,...
    • 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....
    • Sayadi, M.K., Hafezalkotob, A. and Naini, S.G.J., Firefly-inspired algorithm for discrete optimization problems: An application to manufacturing...
    • Sutton, G.G., White, O., Adams, M.D. and Kerlavage, A.R., Tigrassembler: A new tool for assembling large shotgun sequencing projects. Genome...
    • Vidal, P., Luna, F. and Alba, E., Systolic neighborhood search on graphics processing units. Soft Computing, 18(1), pp. 125-142, 2014. DOI:...
    • Vidal, P. and Olivera, A.C., A parallel discrete firefly algorithm on GPU for permutation combinatorial optimization problems. High Performance...
    • 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...
    • Yang, X-S., Firefly algorithm, stochastic test functions and design optimisation. Int. J. Bio-Inspired Comput., 2(2), pp. 78-84, 2010. DOI:...
    • 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....
Fundación Dialnet

Mi Documat

Opciones de artículo

Opciones de compartir

Opciones de entorno