Application of the CUDA programming model in the simulation of genetic sequences evolution
DOI:
https://doi.org/10.29019/enfoqueute.v8n2.159Keywords:
simulation, evolution model, Markov, parallel programming, CUDAAbstract
Simulation is a powerful approach in the study of the molecular evolution of genetic sequences and their divergence over time; there are different procedures for the simulation of molecular evolution, but all of them have high computational complexity, and in most cases the genetic sequences have large size, increasing the execution time of the implementations of those procedures. Based on this problem, this paper describes a proposal of parallelization model using CUDA technology and the results of this proposal are compared with its sequential equivalent.
Downloads
Download data is not yet available.
References
Andrieu, C., & Doucet, A. (2010). Particle Markov chain Monte Carlo methods - Andrieu - 2010 - Journal of the Royal Statistical Society: Series B (Statistical Methodology) - Wiley Online Library. Journal of the Royal. Retrieved from http://onlinelibrary.wiley.com/doi/10.1111/j.1467-9868.2009.00736.x/full%5Cnpapers2://publication/uuid/9E1D438C-88FE-4D49-8CFE-F4D4525C0C7D
Claver, J. M., Sanjuan, A., & Arnau, V. (2007). Análisis paralelo de secuencias de ADN mediante el uso de GPU y CUDA. Uv.es, 1–6. Retrieved from http://www.uv.es/VARNAU/115-GPU-ANACAP_2008.pdf
Cornebise, J., & Peters, G. W. (2009). Comments on “Particle Markov Chain Monte Carlo” by C. Andrieu, A. Doucet and R. Hollenstein. Arxiv, 1–9. Retrieved from http://arxiv.org/abs/0911.3866
Counsell, D. (2005). Bioinformatics and molecular evolution. Comparative and Functional Genomics, 6(5-6), 317–319. https://doi.org/10.1002/cfg.486
CUDA Zone | NVIDIA Developer. (2011). Retrieved January 4, 2017, from https://developer.nvidia.com/cuda-zone
Hwu, W. (2012). GPU computing gems. Applications of GPU computing series. https://doi.org/10.1017/CBO9781107415324.004
Link, W. A., & Eaton, M. J. (2012). On thinning of chains in MCMC. Methods in Ecology and Evolution, 3(1), 112–115. https://doi.org/10.1111/j.2041-210X.2011.00131.x
Liu, Y., Schmidt, B., & Maskell, D. L. (2012). CUSBHAW: A CUDA compatible short read aligner to large genomes based on the Burrows-Wheeler transform. Bioinformatics, 28(14), 1830–1837. https://doi.org/10.1093/bioinformatics/bts276
Liu, Y., Wirawan, A., & Schmidt, B. (2013). CUDASW++ 3.0: accelerating Smith-Waterman protein database search by coupling CPU and GPU SIMD instructions. BMC Bioinformatics, 14, 117. https://doi.org/10.1186/1471-2105-14-117
Manavski, S. A., & Valle, G. (2008). CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment. BMC Bioinformatics, 9 Suppl 2, S10. https://doi.org/10.1186/1471-2105-9-S2-S10
NVIDIA. (2015). CUDA Toolkit 7.5 Documentation. Retrieved January 4, 2017, from http://docs.nvidia.com/cuda/index.html
Nvidia, C. (2011). NVIDIA CUDA C Programming Guide. Changes, (350), 173. https://doi.org/PG-02829-001_v6.0
Sánchez, G. A. L., Carbajal, M. O., Cortés, N. C., & Fernández, R. B. (2012). Sobre la programación paralela de un algoritmo de optimización por cúmulo de partículas en un dispositivo GPU multi-hilos. Intekhnia, 6(2), 59–74.
Schatz, M., Trapnell, C., Delcher, A., & Varshney, A. (2007). High-throughput sequence alignment using Graphics Processing Units. BMC Bioinformatics, 8, 474. https://doi.org/10.1186/1471-2105-8-474
Weber, R. (2012). Markov Chains. Statslab.Cam.Ac.Uk, 28–49. https://doi.org/10.1017/CCOL0521534283.010
Yang, Z. (2006). Computational molecular evolution. Oxford Series in Ecology and Evolution, xvi, 357 p. https://doi.org/10.1093/acprof:oso/9780198567028.001.0001
Yang, Z., & Rodríguez, C. E. (2013). Searching for efficient Markov chain Monte Carlo proposal kernels. Proceedings of the National Academy of Sciences of the United States of America, 110(48), 19307–12. https://doi.org/10.1073/pnas.1311790110
Claver, J. M., Sanjuan, A., & Arnau, V. (2007). Análisis paralelo de secuencias de ADN mediante el uso de GPU y CUDA. Uv.es, 1–6. Retrieved from http://www.uv.es/VARNAU/115-GPU-ANACAP_2008.pdf
Cornebise, J., & Peters, G. W. (2009). Comments on “Particle Markov Chain Monte Carlo” by C. Andrieu, A. Doucet and R. Hollenstein. Arxiv, 1–9. Retrieved from http://arxiv.org/abs/0911.3866
Counsell, D. (2005). Bioinformatics and molecular evolution. Comparative and Functional Genomics, 6(5-6), 317–319. https://doi.org/10.1002/cfg.486
CUDA Zone | NVIDIA Developer. (2011). Retrieved January 4, 2017, from https://developer.nvidia.com/cuda-zone
Hwu, W. (2012). GPU computing gems. Applications of GPU computing series. https://doi.org/10.1017/CBO9781107415324.004
Link, W. A., & Eaton, M. J. (2012). On thinning of chains in MCMC. Methods in Ecology and Evolution, 3(1), 112–115. https://doi.org/10.1111/j.2041-210X.2011.00131.x
Liu, Y., Schmidt, B., & Maskell, D. L. (2012). CUSBHAW: A CUDA compatible short read aligner to large genomes based on the Burrows-Wheeler transform. Bioinformatics, 28(14), 1830–1837. https://doi.org/10.1093/bioinformatics/bts276
Liu, Y., Wirawan, A., & Schmidt, B. (2013). CUDASW++ 3.0: accelerating Smith-Waterman protein database search by coupling CPU and GPU SIMD instructions. BMC Bioinformatics, 14, 117. https://doi.org/10.1186/1471-2105-14-117
Manavski, S. A., & Valle, G. (2008). CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment. BMC Bioinformatics, 9 Suppl 2, S10. https://doi.org/10.1186/1471-2105-9-S2-S10
NVIDIA. (2015). CUDA Toolkit 7.5 Documentation. Retrieved January 4, 2017, from http://docs.nvidia.com/cuda/index.html
Nvidia, C. (2011). NVIDIA CUDA C Programming Guide. Changes, (350), 173. https://doi.org/PG-02829-001_v6.0
Sánchez, G. A. L., Carbajal, M. O., Cortés, N. C., & Fernández, R. B. (2012). Sobre la programación paralela de un algoritmo de optimización por cúmulo de partículas en un dispositivo GPU multi-hilos. Intekhnia, 6(2), 59–74.
Schatz, M., Trapnell, C., Delcher, A., & Varshney, A. (2007). High-throughput sequence alignment using Graphics Processing Units. BMC Bioinformatics, 8, 474. https://doi.org/10.1186/1471-2105-8-474
Weber, R. (2012). Markov Chains. Statslab.Cam.Ac.Uk, 28–49. https://doi.org/10.1017/CCOL0521534283.010
Yang, Z. (2006). Computational molecular evolution. Oxford Series in Ecology and Evolution, xvi, 357 p. https://doi.org/10.1093/acprof:oso/9780198567028.001.0001
Yang, Z., & Rodríguez, C. E. (2013). Searching for efficient Markov chain Monte Carlo proposal kernels. Proceedings of the National Academy of Sciences of the United States of America, 110(48), 19307–12. https://doi.org/10.1073/pnas.1311790110
Published
2017-03-31
How to Cite
Yasmany Chávez, F., & Gálvez Lio, D. (2017). Application of the CUDA programming model in the simulation of genetic sequences evolution. Enfoque UTE, 8(2), pp. 78 – 93. https://doi.org/10.29019/enfoqueute.v8n2.159
Issue
Section
Miscellaneous
License
The authors retain all copyrights ©.
- The authors retain their trademark and patent rights, as well as rights to any process or procedure described in the article.
- The authors retain the right to share, copy, distribute, perform, and publicly communicate the article published in Enfoque UTE (for example, post it in an institutional repository or publish it in a book), provided that acknowledgment of its initial publication in Enfoque UTE is given.
- The authors retain the right to publish their work at a later date, to use the article or any part of it (for example, a compilation of their work, lecture notes, a thesis, or for a book), provided that they indicate the source of publication (authors of the work, journal, volume, issue, and date).
