Solving the DNA fragment assembly problem with a parallel discrete firefly algorithm implemented on GPU

Computer Science and Information Systems

Vidal, Pablo Javier¹ 

关键词: DNA Fragment Assembly Problem;    Graphic Processing Units;    parallelism;    firefly algorithm;    Graphic Processing Units;   

DOI  :  10.2298/CSIS170510009V

学科分类：社会科学、人文和艺术（综合）

来源: Computer Science and Information Systems

【 摘 要 】

The Deoxyribonucleic Acid Fragment Assembly Problem (DNA-FAP) consists in reconstructing a DNA chain from a set of fragments taken randomly. This problem represents an important step in the genome project. Several authors are proposed different approaches to solve the DNA-FAP. In particular, nature-inspired algorithms have been used for its resolution. Even they were obtaining good results; its computational time associated is high. The bio-inspired algorithms are iterative search processes that can explore and exploit efficiently the solution space. Firefly Algorithm is one of the recent evolutionary computing models which is inspired by the flashing light behaviour of fireflies. Recently, the Graphics Processing Units (GPUs) technology are emerge as a novel environment for a parallel implementation and execution of bio-inspired algorithms. Therefore, the use of GPU-based parallel computing it is possible as a complementary tool to speed-up the search. In this work, we design and implement a Discrete Firefly Algorithm (DFA) on a GPU architecture in order to speed-up the search process for solving the DNA Fragment Assembly Problem. Through several experiments, the efficiency of the algorithm and the quality of the results are demonstrated with the potential to applied for longer sequences or sequences of unknown length as well.

【 授权许可】

CC BY-NC-ND