Please use this identifier to cite or link to this item:
Title: M2Align: parallel multiple sequence alignment with a multi-objective metaheuristic.
Authors: Zambrano-Vega, Cristian
Nebro, Antonio J
García-Nieto, José
Aldana-Montes, José F
metadata.dc.subject.mesh: Algorithms
Sequence Alignment
Issue Date: 2017
Abstract: Multiple sequence alignment (MSA) is an NP-complete optimization problem found in computational biology, where the time complexity of finding an optimal alignment raises exponentially along with the number of sequences and their lengths. Additionally, to assess the quality of a MSA, a number of objectives can be taken into account, such as maximizing the sum-of-pairs, maximizing the totally conserved columns, minimizing the number of gaps, or maximizing structural information based scores such as STRIKE. An approach to deal with MSA problems is to use multi-objective metaheuristics, which are non-exact stochastic optimization methods that can produce high quality solutions to complex problems having two or more objectives to be optimized at the same time. Our motivation is to provide a multi-objective metaheuristic for MSA that can run in parallel taking advantage of multi-core-based computers. The software tool we propose, called M2Align (Multi-objective Multiple Sequence Alignment), is a parallel and more efficient version of the three-objective optimizer for sequence alignments MO-SAStrE, able of reducing the algorithm computing time by exploiting the computing capabilities of common multi-core CPU clusters. Our performance evaluation over datasets of the benchmark BAliBASE (v3.0) shows that significant time reductions can be achieved by using up to 20 cores. Even in sequential executions, M2Align is faster than MO-SAStrE, thanks to the encoding method used for the alignments. M2Align is an open source project hosted in GitHub, where the source code and sample datasets can be freely obtained: Supplementary data are available at Bioinformatics online.
metadata.dc.identifier.doi: 10.1093/bioinformatics/btx338
Appears in Collections:Producción 2020

Files in This Item:
There are no files associated with this item.

This item is protected by original copyright

Except where otherwise noted, Items on the Andalusian Health Repository site are licensed under a Creative Commons Attribution-NonCommercial-NoDerivatives License.