A Hybrid Multiobjective Memetic Metaheuristic for Multiple Sequence Alignment

Álvaro Rubio-Largo, Miguel A. Vega-Rodríguez, David L. González-Álvarez

Research output: Contribution to journalArticlepeer-review

33 Citations (Scopus)


Over the last 25 years, the multiple sequence alignment (MSA) problem has attracted the attention of biologists because it is one of the major techniques used in several areas of computational biology, such as homology searches, genomic annotation, protein structure prediction, gene regulation networks, or functional genomics. This problem implicates the alignment of more than two biological sequences, and is considered as a nondeterministic polynomial time optimization problem. In this paper, we find a number of different approaches for dealing with this biological sequence alignment problem. Basically, we distinguish six main groups: 1) exact methods; 2) progressive methods; 3) consistency-based methods; 4) iterative methods; 5) evolutionary algorithms; and 6) structure-based methods. In this paper, we propose the use of evolutionary computation and multiobjective optimization for solving this bioinformatics problem. A multiobjective version of a memetic metaheuristic is presented: hybrid multiobjective metaheuristics for MSA. In order to prove the effectiveness of the new proposal, we use three structure-based benchmarks created by using empirical data as input. The results obtained by our method are compared with well-known methods published in this paper, concluding that the new approach presents remarkable accuracy when dealing with sets of sequences with a low sequence similarity, the most frequent ones in real world.

Original languageEnglish
Article number7274726
Pages (from-to)499-514
Number of pages16
JournalIEEE Transactions on Evolutionary Computation
Issue number4
Publication statusPublished - 1 Aug 2016


  • Memetic metaheuristic
  • multiobjective optimization
  • multiple sequence alignment (MSA)


Dive into the research topics of 'A Hybrid Multiobjective Memetic Metaheuristic for Multiple Sequence Alignment'. Together they form a unique fingerprint.

Cite this