title: A new greedy randomised adaptive search procedure for Multiple Sequence Alignment.
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.
authors.affiliation: Computer Science Department, Mentouri University Constantine, Ain El Bey, Constantine 25017, Algeria. layeb@umc.edu.dz
authors.forename: Abdesslem
authors.initials: A
authors.lastname: Layeb
authors.forename: Marwa
authors.initials: M
authors.lastname: Selmane
authors.forename: Maroua Bencheikh
authors.initials: MB
authors.lastname: Elhoucine
mesh_terms: D000465:Algorithms; D000595:Amino Acid Sequence; D001483:Base Sequence; D016415:Sequence Alignment / Q000379:methods*; D020539:Sequence Analysis, Protein / Q000379:methods*