Title: A new greedy randomised adaptive search procedure for multiple sequence alignment

Authors: Abdesslem Layeb; Marwa Selmane; Maroua Bencheikh Elhoucine

Addresses: Computer Science Department, Mentouri University Constantine, Ain El Bey, Constantine 25017, Algeria ' Computer Science Department, Mentouri University Constantine, Ain El Bey, Constantine 25017, Algeria ' Computer Science Department, Mentouri University Constantine, Ain El Bey, Constantine 25017, Algeria

Abstract: The Multiple Sequence Alignment (MSA) is one of the most challenging tasks in bioinformatics. It consists of aligning several sequences to show the fundamental relationship and the common characteristics between a set of protein or nucleic sequences; this problem has been shown to be NP-complete if the number of sequences is >2. In this paper, a new incomplete algorithm based on a Greedy Randomised Adaptive Search Procedure (GRASP) is presented to deal with the MSA problem. The first GRASP's phase is a new greedy algorithm based on the application of a new random progressive method and a hybrid global/local algorithm. The second phase is an adaptive refinement method based on consensus alignment. The obtained results are very encouraging and show the feasibility and effectiveness of the proposed approach.

Keywords: bioinformatics; optimisation; MSA; multiple sequence alignment; progressive alignment; GRASP procedure; greedy randomised adaptive search.

DOI: 10.1504/IJBRA.2013.054695

International Journal of Bioinformatics Research and Applications, 2013 Vol.9 No.4, pp.323 - 335

Received: 11 May 2011
Accepted: 20 Sep 2011

Published online: 18 Sep 2014 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article