Multi-start Evolutionary Nonlinear OpTimizeR (MENOTR): A hybrid parameter optimization toolbox

Abstract

Parameter optimization or "data fitting" is a computational process that identifies a set of parameter values that best describe an experimental data set. Parameter optimization is commonly carried out using a computer program utilizing a non-linear least squares (NLLS) algorithm. These algorithms work by continuously refining a user supplied initial guess resulting in a systematic increase in the goodness of fit. A well-understood problem with this class of algorithms is that in the case of models with correlated parameters the optimized output parameters are initial guess dependent. This dependency can potentially introduce user bias into the resultant analysis. While many optimization programs exist, few address this dilemma. Here we present a data analysis tool, MENOTR, that is capable of overcoming the initial guess dependence in parameter optimization. Several case studies with published experimental data are presented to demonstrate the capabilities of this tool. The results presented here demonstrate how to effectively overcome the initial guess dependence of NLLS leading to greater confidence that the resultant optimized parameters are the best possible set of parameters to describe an experimental data set. While the optimization strategies implemented within MENOTR are not entirely novel, the application of these strategies to optimize parameters in kinetic and thermodynamic biochemical models is uncommon. MENOTR was designed to require minimal modification to accommodate a new model making it immediately accessible to researchers with a limited programming background. We anticipate that this toolbox can be used in a wide variety of data analysis applications. Prototype versions of this toolbox have been used in a number of published investigations already, as well as ongoing work with chemical-quenched flow, stopped-flow, and molecular tweezers data sets. STATEMENT OF SIGNIFICANCE: Non-linear least squares (NLLS) is a common form of parameter optimization in biochemistry kinetic and thermodynamic investigations These algorithms are used to fit experimental data sets and report corresponding parameter values. The algorithms are fast and able to provide good quality solutions for models involving few parameters. However, initial guess dependence is a well-known drawback of this optimization strategy that can introduce user bias. An alternative method of parameter optimization are genetic algorithms (GA). Genetic algorithms do not have an initial guess dependence but are slow at arriving at the best set of fit parameters. Here, we present MENOTR, a parameter optimization toolbox utilizing a hybrid GA/NLLS algorithm. The toolbox maximizes the strength of each strategy while minimizing the inherent drawbacks.

Keywords: Data fitting; Kinetics; Optimization; Thermodynamics.

Fig. 1.

Illustration outlining deterministic, random, and hybrid algorithms approach to finding minima in error contour. a) NLLS, a deterministic method will quickly converge on solution. If one minimum is present, the algorithm will converge on identical position irrespective of starting point. b) NLLS has well known initial guess bias in cases involving multiple minima in error contour. Different starting points will result in different optimized parameters. c) The genetic algorithm will randomly probe the error space at different parameter values. This algorithm overcomes local minima but has difficulty in finding the absolute minimum. d) MENOTR, a hybrid NLLS-genetic algorithm, takes advantage of the strengths of both approaches while minimizing the weaknesses. The genetic algorithm component of MENOTR escapes local minima and the NLLS quickly converges on a solution.

Fig. 2.

Functionalities of the MENOTR toolbox. MENOTR can optimize parameters describing floating or static models in addition to closed form expressions. Errors on resultant parameters may be ascertained using Monte Carlo or grid search analysis. The toolbox can be run with minimal user intervention, making it ideal for being launched on a node of a high-performance computer cluster.

Fig. 3.

Flow diagram overview illustrating how MENOTR optimizes parameters. In the first step, an initial guess is passed to three different optimization routines. The parameters are optimized individually and then pooled together. The pooled parameters are then compared to see if they are different. If they are different, then the best set of parameters is used as the new initial guess. If they are identical then the parameter values are reported.

Fig. 4.

Example of resultant contour generated from grid-search analysis for a given parameter. (Circles) Individual F-statistic values, (solid lines) interpolation between data points, and (Broken line) F-critical value.

Fig. 5.

MENTOR analysis of previously published single turnover RecBCD catalyzed DNA unwinding. Fitting was performed globally across eight DNA duplex lengths using Eq. (1). Parameters kU, kC, kNP, m, and h were assigned as global parameters while A and x were local parameters for each length. Here we show three representative data sets (colored traces) of duplex lengths (a) 24 bp, (b) 43 bp, and (c) 60 bp with the corresponding best-fit simulations (black traces) based on Eq. (1) and the optimized parameters (Table 1). A corresponding figure for the original fits and analysis of this data can be found in Lucius 2004, fig. 8 [1].

Fig. 6.

MENOTR analysis of previously published fluorescence time courses for ClpA catalyzed polypeptide translocation. Translocation time courses were collected on fluorescein-SsrA 30mer, 40mer and 50mer out to 200 s. Fitting was performed globally across all three peptide lengths using Eq. (2). Parameters k_T, k_d, k_C, k_NP, h, m, and b were optimized globally, while A and x were optimized locally for each length. The first 20 s of the time courses are plotted here as solid traces with the dashes representing a best-fit simulation using Eq. (2) and the optimized parameters (Table 1). A corresponding figure for the original fits and analysis of this data can be found in Lucius et al. 2010, Fig. 3 [2].

Fig. 7.

MENOTR analysis of simulated thermodynamic data for two classic cases of ligand binding to macromolecule using implicit fitting strategies. (a) n-independent and identical: Simulated data were generated using Eq. (8) and Gaussian white noise was added to simulate experimental error. A signal to noise ratio of 30 was used for the experimental noise. The data were fit implicitly using Eq. (4) and Eq. (6) in MENOTR. (b) n-independent non-identical: Data were simulated using a 2-site model with Eq. (6) and Eq. (9) in Micromath Scientist. Gaussian white noise was added to each data set to simulate experimental error using the function AWGN in MATLAB. A signal to noise ratio of 40 was used for the experimental noise. The data were fit implicitly in MENOTR using Eq. (6) and Eq. (9).

Scheme 1

Scheme 2