Source-linked AI summary
MEIGO: an open-source software suite based on metaheuristics for global optimization in systems biology and bioinformatics
Jose A Egea, David Henriques, Thomas Cokelaer, Alejandro F Villaverde, Julio R Banga, Julio Saez-Rodriguez
TL;DR
Computational-biology optimization often requires global methods, yet metaheuristic tools are limited. MEIGO addresses this gap with an open-source suite implementing eSS and VNS across several problem classes; benchmarks and case studies report strong performance, while the paper notes that some problems also admit deterministic formulations.
Problem
Metaheuristic optimization tools are limited despite the need for global optimization in computational biology.
Method
MEIGO implements eSS for cNLP and MINLP problems and VNS for IP problems, with single-thread and cooperative parallel execution.
Results
MEIGO was evaluated on optimization benchmarks and systems-biology and bioinformatics case studies, with reported performance exceeding other state-of-the-art methods.
Takeaways & Limitations
MEIGO provides a free, open-source, modular optimization platform applicable across multiple systems-biology and bioinformatics domains.
Takeaways & Limitations
The paper notes that the signaling-network problem can also be solved by deterministic Integer Linear Programming or Answer Set Programming methods.
Abstract
from arXiv · showhide
Optimization is key to solve many problems in computational biology. Global optimization methods provide a robust methodology, and metaheuristics in particular have proven to be the most efficient methods for many applications. Despite their utility, there is limited availability of metaheuristic tools. We present MEIGO, an R and Matlab optimization toolbox (also available in Python via a wrapper of the R version), that implements metaheuristics capable of solving diverse problems arising in systems biology and bioinformatics: enhanced scatter search method (eSS) for continuous nonlinear programming (cNLP) and mixed-integer programming (MINLP) problems, and variable neighborhood search (VNS) for Integer Programming (IP) problems. Both methods can be run on a single-thread or in parallel using a cooperative strategy. The code is supplied under GPLv3 and is available at \url{http://www.iim.csic.es/~gingproc/meigo.html}. Documentation and examples are included. The R package has been submitted to Bioconductor. We evaluate MEIGO against optimization benchmarks, and illustrate its applicability to a series of case studies in bioinformatics and systems biology, outperforming other state-of-the-art methods. MEIGO provides a free, open-source platform for optimization, that can be applied to multiple domains of systems biology and bioinformatics. It includes efficient state of the art metaheuristics, and its open and modular structure allows the addition of further methods.
Background
MEIGO addresses the limited availability of metaheuristic tools for non-convex optimization problems in systems biology and bioinformatics. It provides eSS and VNS across continuous, mixed-integer, integer, and binary problem classes.
- Many computational-biology tasks can be formulated as integer-programming problems, including sequence alignment, genome rearrangement, protein structure prediction, and synthetic-network design.
- Non-convex optimization motivates global methods because exact approaches can be computationally prohibitive, whereas stochastic methods offer reasonable runtimes without global-optimality guarantees.
- MEIGO implements enhanced scatter search and variable neighborhood search in open-source R and Matlab versions, with Python access through an R wrapper.
- MEIGO supports cooperative parallel computation and black-box objective functions, enabling use when objectives or constraints require additional problem-solving steps.
Methods
MEIGO combines two complementary metaheuristics with cooperative parallel execution. eSS uses population-based systematic combination and memory, while VNS explores progressively different neighborhoods around incumbent solutions.
- Enhanced Scatter Search (eSS): eSS is a population-based evolutionary metaheuristic that uses a small Reference Set and systematic, rather than random, member combinations.
- Enhanced Scatter Search (eSS): Enhanced scatter search adds 1+1 replacement, a “go-beyond” strategy for promising directions, and memory-based initial-point selection.
- Variable Neighbourhood Search (VNS): VNS performs local searches around an incumbent solution and changes neighborhoods to explore different local optima, including progressively more distant neighborhoods.
- Cooperative parallel strategy: MEIGO runs parallel algorithm threads with potentially different settings or random initializations that exchange the best solution and optionally eSS diversity information.
- Cooperative parallel strategy: Threads exchange information at fixed intervals, with conservative settings emphasizing diversification and aggressive settings emphasizing intensification.
Implementation
MEIGO provides cross-platform implementations of eSS and VNS, cooperative multicore or cluster versions, and a modular architecture for black-box optimization. Its open structure also permits integration of additional optimization methods.
- MEIGO runs on Windows, Mac, and Linux and provides implementations in Matlab and R.
- eSS solves continuous and mixed-integer nonlinear programs, while VNS solves integer programs; cooperative CeSS and CVNS versions support multicore PCs and clusters.
- Cooperative execution lets independent parallel threads cover search options ranging from aggressive to robust settings.
- Users supply externally callable black-box objective functions that return objective values and constraint values for constrained problems.
- MEIGO’s open optimization platform can incorporate additional exact, heuristic, probabilistic, single-trajectory, or population-based methods.
Illustrative examples
MEIGO is illustrated across large-scale continuous, integer, metabolic engineering, and logic-model optimization problems. The examples show competitive benchmark behavior and strong VNS results against genetic algorithms in the reported case studies.
- Large-Scale Continuous Global Optimization Benchmark: MEIGO was evaluated on CEC@WCCI-2012 large-scale global-optimization benchmarks f10, f17, and f20 using the R version of cooperative enhanced scatter search.Its convergence curves were coherent with earlier Matlab results and competitive with the reference results.
- Integer optimization benchmark problems: VNS solved all tested AMPL integer optimization problems and sometimes achieved a better solution than the best previously reported one.These tests used the Matlab version of MEIGO; the AMPL interface restricted execution to Windows.
- Metabolic engineering example: In the E. coli metabolic-engineering example, VNS searched for gene knockouts maximizing succinate production under a biomass-maximization flux-balance objective.Five integer decision variables represented possible gene knockouts, each ranging from 0 to 52.
- Metabolic engineering example: For the metabolic-engineering encoding, VNS achieved the optimal solution more often than the genetic algorithm, although the authors describe the comparison as a cross-check rather than an extensive performance study.The reported p-value was 0.06753, or 0.02104 after removing an outlier VNS solution; results may vary with encoding and parameter tuning.
- Training of logic models of signalling networks to phospho-proteomic data: For logic-model training, VNS and GA were each run 100 times, and VNS returned better average solutions within the allowed time budget.The Welch two-sample t-test reported p = 3.45e-14, while the binary formulation can also be solved by deterministic integer-programming or answer-set methods.
Conclusions
MEIGO is presented as a free, open-source, flexible global-optimization package with a modular design that supports connecting existing methods and adding further methods.
- MEIGO provides free, open-source global optimization in R, Matlab, and Python.
- Its modular structure allows connection to existing optimization methods.
- The authors plan to add further methods, including Bayesian inference methods.
Availability and requirements
MEIGO is available for Windows, Linux, and Mac OS X under the GPLv3 licence, with Matlab and R requirements specified.
- MEIGO supports Windows, Linux, and Mac OS X.
- The software requires Matlab 7.5 or higher or R 2.15 or higher.
- MEIGO is distributed under the GPLv3 licence.