A new greedy randomised adaptive search procedure for multiple sequence alignment. (1st January 2013)

• Record Type: Journal Article
• Authors: Layeb, Abdesslem; Selmane, Marwa; Elhoucine, Maroua Bencheikh
• Is Part Of: International journal of bioinformatics research and applications. Volume 9:Number 4(2013)
• Page Start: 323
• Page End: 335
• Publication Date: 2013-01-01
• Subjects: bioinformatics -- optimisation -- MSA -- multiple sequence alignment -- progressive alignment -- GRASP procedure; Bioinformatics -- Periodicals; 570.285
• Languages: English
• ISSNs: 1744-5485

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.