A method for solution of the multi-objective inverse problems under uncertainty

We describe a method to solve multi-objective inverse problems under uncertainty. The method was tested on non-linear models of dynamic series and population dynamics, as well as on the spatiotemporal model of gene expression in terms of non-linear differential equations. We consider how to identify model parameters when experimental data contain additive noise and measurements are performed in discrete time points. We formulate the multi-objective problem of optimization under uncertainty. In addition to a criterion of least squares difference we applied a criterion which is based on the integral of trajectories of the system spatiotemporal dynamics, as well as a heuristic criterion CHAOS based on the decision tree method. The optimization problem is formulated using a fuzzy statement and is constrained by penalty functions based on the normalized membership functions of a fuzzy set of model solutions. This allows us to reconstruct the expression pattern of hairy gene in Drosophila even-skipped mutants that is in good agreement with experimental data. The reproducibility of obtained results is confirmed by solution of inverse problems using different global optimization methods with heuristic strategies.     

Inference of S-system models of genetic networks by solving one-dimensional function optimization problems

Voit and Almeida have proposed the decoupling approach as a method for inferring the S-system models of genetic networks. The decoupling approach defines the inference of a genetic network as a problem requiring the solutions of sets of algebraic equations. The computation can be accomplished in a very short time, as the approach estimates S-system parameters without solving any of the differential equations. Yet the defined algebraic equations are non-linear, which sometimes prevents us from finding reasonable S-system parameters. In this study, we propose a new technique to overcome this drawback of the decoupling approach. This technique transforms the problem of solving each set of algebraic equations into a one-dimensional function optimization problem. The computation can still be accomplished in a relatively short time, as the problem is transformed by solving a linear programming problem. We confirm the effectiveness of the proposed approach through numerical experiments.     

Thermodynamic heuristics with case-based reasoning: combined insights for RNA pseudoknot secondary structure

The secondary structure of RNA pseudoknots has been extensively inferred and scrutinized by computational approaches. Experimental methods for determining RNA structure are time consuming and tedious; therefore, predictive computational approaches are required. Predicting the most accurate and energy-stable pseudoknot RNA secondary structure has been proven to be an NP-hard problem. In this paper, a new RNA folding approach, termed MSeeker, is presented; it includes KnotSeeker (a heuristic method) and Mfold (a thermodynamic algorithm). The global optimization of this thermodynamic heuristic approach was further enhanced by using a case-based reasoning technique as a local optimization method. MSeeker is a proposed algorithm for predicting RNA pseudoknot structure from individual sequences, especially long ones. This research demonstrates that MSeeker improves the sensitivity and specificity of existing RNA pseudoknot structure predictions. The performance and structural results from this proposed method were evaluated against seven other state-of-the-art pseudoknot prediction methods. The MSeeker method had better sensitivity than the DotKnot, FlexStem, HotKnots, pknotsRG, ILM, NUPACK and pknotsRE methods, with 79% of the predicted pseudoknot base-pairs being correct.     

Particle swarm optimizer for weighting factor selection in intensity-modulated radiation therapy optimization algorithms

In inverse treatment planning of intensity-modulated radiation therapy (IMRT), the objective function is typically the sum of the weighted sub-scores, where the weights indicate the importance of the sub-scores. To obtain a high-quality treatment plan, the planner manually adjusts the objective weights using a trial-and-error procedure until an acceptable plan is reached. In this work, a new particle swarm optimization (PSO) method which can adjust the weighting factors automatically was investigated to overcome the requirement of manual adjustment, thereby reducing the workload of the human planner and contributing to the development of a fully automated planning process. The proposed optimization method consists of three steps. (i) First, a swarm of weighting factors (i.e., particles) is initialized randomly in the search space, where each particle corresponds to a global objective function. (ii) Then, a plan optimization solver is employed to obtain the optimal solution for each particle, and the values of the evaluation functions used to determine the particle’s location and the population global location for the PSO are calculated based on these results. (iii) Next, the weighting factors are updated based on the particle’s location and the population global location. Step (ii) is performed alternately with step (iii) until the termination condition is reached. In this method, the evaluation function is a combination of several key points on the dose volume histograms. Furthermore, a perturbation strategy – the crossover and mutation operator hybrid approach – is employed to enhance the population diversity, and two arguments are applied to the evaluation function to improve the flexibility of the algorithm. In this study, the proposed method was used to develop IMRT treatment plans involving five unequally spaced 6 MV photon beams for 10 prostate cancer cases. The proposed optimization algorithm yielded high-quality plans for all of the cases, without human planner intervention. A comparison of the results with the optimized solution obtained using a similar optimization model but with human planner intervention revealed that the proposed algorithm produced optimized plans superior to that developed using the manual plan. The proposed algorithm can generate admissible solutions within reasonable computational times and can be used to develop fully automated IMRT treatment planning methods, thus reducing human planners’ workloads during iterative processes.     

A 'cheap' optimal control approach to estimate muscle forces in musculoskeletal systems

This paper shows a new method to estimate the muscle forces in musculoskeletal systems based on the inverse dynamics of a multi-body system associated optimal control. The redundant actuator problem is solved by minimizing a time-integral cost function, augmented with a torque-tracking error function, and muscle dynamics is considered through differential constraints. The method is compared to a previously implemented human posture control problem, solved using a Forward Dynamics Optimal Control approach and to classical static optimization, with two different objective functions. The new method provides very similar muscle force patterns when compared to the forward dynamics solution, but the computational cost is much smaller and the numerical robustness is increased. The results achieved suggest that this method is more accurate for the muscle force predictions when compared to static optimization, and can be used as a numerically 'cheap' alternative to the forward dynamics and optimal control in some applications.     

Multi-Objective Community Detection Based on Memetic Algorithm

Community detection has drawn a lot of attention as it can provide invaluable help in understanding the function and visualizing the structure of networks. Since single objective optimization methods have intrinsic drawbacks to identifying multiple significant community structures, some methods formulate the community detection as multi-objective problems and adopt population-based evolutionary algorithms to obtain multiple community structures. Evolutionary algorithms have strong global search ability, but have difficulty in locating local optima efficiently. In this study, in order to identify multiple significant community structures more effectively, a multi-objective memetic algorithm for community detection is proposed by combining multi-objective evolutionary algorithm with a local search procedure. The local search procedure is designed by addressing three issues. Firstly, nondominated solutions generated by evolutionary operations and solutions in dominant population are set as initial individuals for local search procedure. Then, a new direction vector named as pseudonormal vector is proposed to integrate two objective functions together to form a fitness function. Finally, a network specific local search strategy based on label propagation rule is expanded to search the local optimal solutions efficiently. The extensive experiments on both artificial and real-world networks evaluate the proposed method from three aspects. Firstly, experiments on influence of local search procedure demonstrate that the local search procedure can speed up the convergence to better partitions and make the algorithm more stable. Secondly, comparisons with a set of classic community detection methods illustrate the proposed method can find single partitions effectively. Finally, the method is applied to identify hierarchical structures of networks which are beneficial for analyzing networks in multi-resolution levels.     

The combinatorial distance geometry method for the calculation of molecular conformation. I. A new approach to an old problem

A new approach to the long-standing local minimum problem of molecular energy minimization is proposed. The approach relies upon a field of computer mathematics known as combinatorial optimization, together with methods of conformational analysis derived from distance geometry. The advantages over the usual numerical techniques of optimization are, first, that the algorithms derived are globally convergent, and second, that the mathematical problems involved are well-posed and suitable for study within the modern theory of computational complexity. In this paper we introduce the approach, and describe a computer program based on it.     

Analytical and numerical analysis of inverse optimization problems: conditions of uniqueness and computational methods

One of the key problems of motor control is the redundancy problem, in particular how the central nervous system (CNS) chooses an action out of infinitely many possible. A promising way to address this question is to assume that the choice is made based on optimization of a certain cost function. A number of cost functions have been proposed in the literature to explain performance in different motor tasks: from force sharing in grasping to path planning in walking. However, the problem of uniqueness of the cost function(s) was not addressed until recently. In this article, we analyze two methods of finding additive cost functions in inverse optimization problems with linear constraints, so-called linear-additive inverse optimization problems. These methods are based on the Uniqueness Theorem for inverse optimization problems that we proved recently (Terekhov et?al., J Math Biol 61(3):423?C453, 2010). Using synthetic data, we show that both methods allow for determining the cost function. We analyze the influence of noise on the both methods. Finally, we show how a violation of the conditions of the Uniqueness Theorem may lead to incorrect solutions of the inverse optimization problem.     

Dynamic optimization of bioprocesses: efficient and robust numerical strategies

The dynamic optimization (open loop optimal control) of non-linear bioprocesses is considered in this contribution. These processes can be described by sets of non-linear differential and algebraic equations (DAEs), usually subject to constraints in the state and control variables. A review of the available solution techniques for this class of problems is presented, highlighting the numerical difficulties arising from the non-linear, constrained and often discontinuous nature of these systems. In order to surmount these difficulties, we present several alternative stochastic and hybrid techniques based on the control vector parameterization (CVP) approach. The CVP approach is a direct method which transforms the original problem into a non-linear programming (NLP) problem, which must be solved by a suitable (efficient and robust) solver. In particular, a hybrid technique uses a first global optimization phase followed by a fast second phase based on a local deterministic method, so it can handle the nonconvexity of many of these NLPs. The efficiency and robustness of these techniques is illustrated by solving several challenging case studies regarding the optimal control of fed-batch bioreactors and other bioprocesses. In order to fairly evaluate their advantages, a careful and critical comparison with several other direct approaches is provided. The results indicate that the two-phase hybrid approach presents the best compromise between robustness and efficiency.     

Asymptotically consistent numerical approximation of hemolysis

In a previous communication, we have proposed a numerical framework for the prediction of in vitro hemolysis indices in the preselection and optimization of medical devices. This numerical methodology is based on a novel interpretation of Giersiepen-Wurzinger blood damage correlation as a volume integration of a damage function over the computational domain. We now propose an improvement of this approach based on a hyperbolic equation of blood damage that is asymptotically consistent. Consequently, while the proposed correction has yet to be proven experimentally, it has the potential to numerically predict more realistic red blood cell destruction in the case of in vitro experiments. We also investigate the appropriate computation of the shear stress scalar of the damage fraction model. Finally, we assess the validity of this consistent approach with an analytical example and with some 3D examples.     

On the local optimal solutions of metabolic regulatory networks using information guided genetic algorithm approach and clustering analysis

Biological information generated by high-throughput technology has made systems approach feasible for many biological problems. By this approach, optimization of metabolic pathway has been successfully applied in the amino acid production. However, in this technique, gene modifications of metabolic control architecture as well as enzyme expression levels are coupled and result in a mixed integer nonlinear programming problem. Furthermore, the stoichiometric complexity of metabolic pathway, along with strong nonlinear behaviour of the regulatory kinetic models, directs a highly rugged contour in the whole optimization problem. There may exist local optimal solutions wherein the same level of production through different flux distributions compared with global optimum. The purpose of this work is to develop a novel stochastic optimization approach-information guided genetic algorithm (IGA) to discover the local optima with different levels of modification of the regulatory loop and production rates. The novelties of this work include the information theory, local search, and clustering analysis to discover the local optima which have physical meaning among the qualified solutions.     

Deterministic global optimization algorithm based on outer approximation for the parameter estima- tion of nonlinear dynamic biological systems

ABSTRACT: BACKGROUND: The estimation of parameter values for mathematical models of biological systems is an optimization problem that is particularly challenging due to the nonlinearities involved. One major difficulty is the existence of multiple minima in which standard optimization methods may fall during the search. Deterministic global optimization methods overcome this limitation, ensuring convergence to the global optimum within a desired tolerance. Global optimization techniques are typically classified into stochastic and deterministic. The former typically lead to lower CPU times but offer no guarantee of convergence to the global minimum in a finite number of iterations. In contrast, deterministic methods provide solutions of a given quality (i.e., optimality gap), but tend to lead to large computational burdens. RESULTS: This work presents a deterministic outer approximation-based algorithm for the global optimization of dynamic problems arising in the parameter estimation of models of biological systems. Our approach, which offers a theoretical guarantee of convergence to the global minimum, reformulating the set of ordinary differential equations into an equivalent set of algebraic equations through the use of orthogonal collocation methods, giving rise to a nonconvex nonlinear programming (NLP) problem. This nonconvex NLP is decomposed into two hierarchical levels: a master mixed-integer linear programming problem (MILP) that provides a rigorous lower bound on the optimal solution, and a reduced-space slave NLP that yields an upper bound. The algorithm iterates between these two levels until a termination criterion is satisfied. CONCLUSION: The capabilities of our approach were tested in two benchmark problems, in which the performance of our algorithm was compared with that of the commercial global optimization package BARON. The proposed strategy produced near optimal solutions (i.e., within a desired tolerance) in a fraction of the CPU time required by BARON.     

A practical approach to significance assessment in alignment with gaps.

Current numerical methods for assessing the statistical significance of local alignments with gaps are time consuming. Analytical solutions thus far have been limited to specific cases. Here, we present a new line of attack to the problem of statistical significance assessment.We combine this new approach with known properties of the dynamics of the global alignment algorithm and high performance numerical techniques and present a novel method for assessing significance of gaps within practical time scales. The results and performance of these new methods test very well against tried methods with drastically less effort.     

Mathematical and kinetic modeling of biofilm reactor based on ant colony optimization

Inverse estimation of model parameters via mathematical modeling route, known as inverse modeling (IM), is an attractive alternative approach to the experimental methods. This approach makes use of efficient optimization techniques in the course of solution of an inverse problem with the aid of measured data. In this study, a novel optimization method based on ant colony optimization (ACO), denoted by ACO-IM, is presented for inverse estimation of kinetic and film thickness parameters of biofilm models that describe an experimental fixed bed anaerobic reactor. The proposed optimization method for parameter estimation emulates the fact that ants are capable of finding the shortest path from a food source to their nest by depositing a trial of pheromone during their walk. The efficacy of the ACO-IM for numerical estimation of bio-kinetic parameters is demonstrated through its application for the anaerobic treatment of industry wastewater in a fixed bed biofilm process. The results explain the rigorousness of mathematical models, the form of kinetic and film thickness models and the type of packing to be used with the biofilm process for accurate determination of kinetic and film thickness parameters so as to ensure reliable predictive performance of the biofilm reactor models.     

Local versus global optimal sports techniques in a group of athletes

Various optimization algorithms have been used to achieve optimal control of sports movements. Nevertheless, no local or global optimization algorithm could be the most effective for solving all optimal control problems. This study aims at comparing local and global optimal solutions in a multistart gradient-based optimization by considering actual repetitive performances of a group of athletes performing a transition move on the uneven bars. Twenty-four trials by eight national-level female gymnasts were recorded using a motion capture system, and then multistart sequential quadratic programming optimizations were performed to obtain global optimal, local optimal and suboptimal solutions. The multistart approach combined with a gradient-based algorithm did not often find the local solution to be the best and proposed several other solutions including global optimal and suboptimal techniques. The qualitative change between actual and optimal techniques provided three directions for training: to increase hip flexion–abduction, to transfer leg and arm angular momentum to the trunk and to straighten hand path to the bar.     

A linear programming approach for identifying a consensus sequence on DNA sequences

MOTIVATION: Maximum-likelihood methods for solving the consensus sequence identification (CSI) problem on DNA sequences may only find a local optimum rather than the global optimum. Additionally, such methods do not allow logical constraints to be imposed on their models. This study develops a linear programming technique to solve CSI problems by finding an optimum consensus sequence. This method is computationally more efficient and is guaranteed to reach the global optimum. The developed method can also be extended to treat more complicated CSI problems with ambiguous conserved patterns. RESULTS: A CSI problem is first formulated as a non-linear mixed 0-1 optimization program, which is then converted into a linear mixed 0-1 program. The proposed method provides the following advantages over maximum-likelihood methods: (1) It is guaranteed to find the global optimum. (2) It can embed various logical constraints into the corresponding model. (3) It is applicable to problems with many long sequences. (4) It can find the second and the third best solutions. An extension of the proposed linear mixed 0-1 program is also designed to solve CSI problems with an unknown spacer length between conserved regions. Two examples of searching for CRP-binding sites and for FNR-binding sites in the Escherichia coli genome are used to illustrate and test the proposed method. AVAILABILITY: A software package, Global Site Seer for the Microsoft Windows operating system is available by http://www.iim.nctu.edu.tw/~cjfu/gss.htm     

GENOCOP algorithm and hierarchical grid transformation for image warping of two dimensional gel eletrophoretic maps

Hierarchical grid transformation is a powerful approach to SDS 2DPAGE maps warping. The hierarchy of the warping transformation is able to model both global and local deformations of the gels and the algorithm can be stopped when a certain degree of accuracy in the image alignment is obtained. The numerical optimization of the position of the nodes of the grid that are responsible for the image warping is a multivariate task that can be solved efficiently using Genetic Algorithms. The use of Genetic Algorithms ensures that an optimal position of the nodes can be defined with a low computational cost with respect to other methods. The optimal positions of the nodes of the grid can be successfully used for defining a good warping of the gels.