In this chapter, the description about computer simulation of system biology is briefly explained. In next section of this chapter, simulation of yeast fermentation process is explained to give better understanding about modeling process. Next is about parameter estimation that explained in detail and parameter estimation algorithm used also mention in this section. In addition, genetic algorithm and simplex also been explained. This followed by explanation of swarm intelligent that comprise of Artificial Bee Colony algorithm, Bee algorithm and Particle Swarm Optimization algorithm. Then summary of the three swarm intelligent algorithm previous studies are mentioned too. Next section will be the comparison table between ABC, BA, GA and simplex. Lastly the problem and challenge faced is explained in the last section of this chapter.
This chapter of literature review is very important in explanation about information of the research topic. So that it will give more understanding about overall techniques and methodology that used in this research. By having difference technique that proposed by difference researcher, enable us to do comparison between technique that lead to understanding in advantage and disadvantage of difference algorithm. In parameter estimation, there are a lot of evolutionary algorithms that can be used. By reviewing the research papers of difference algorithm, suitable algorithm that can be used by this research can be determined.
2.3 Computer simulation of system biology
Recently, the accuracy and performance of biological system has been increasing due to the advance in supercomputer hardware. In addition, microcomputers have enter the new generation that enable more complex biological mathematical model can be constructed. By using simulation and modeling concept, the relationship between real biological system and its model can be improved.
A computer simulation of the biological system is the translation of mathematical model of the system into a program that calculate the parameter and give the results. According to Judith R.L (1987), mathematical model is the set of equation that describe the systems. Generally in a mathematical model, the differential equation that involved can be simulated using numerical analysis method in a computer. In biological system, computer simulation can be grouped into static and dynamic. For example, the static simulation is the model that give a three dimensional structure of protein and does not change in time. Whereas the dynamic simulation, it will change over time or does not involve time as a variable and will be further subdivided into continuous or discrete.
In simulation of mathematical model, it has a few type of model that distinguished by the type of equation that involve in the model. One of the types are the deterministic model that directly describe the system by algebraic expression, a set of equation and differential equations. In addition, deterministic channel model is a model that describe more realistic and detailed of the structure and property. Consequently give more complicated and channel models. Furthermore, another type of model is the stochastic model that involve of equation that describe the change probabilities of certain variable or event. It also decided whether the event has occurred or not by using random numbers.
System Biology Markup Language(SBML), CellML and Systems Biology Workbench are some of the open software platform used for modeling and simulation. So it is very helpful in increasing the value of new generation of database that related to biological pathways.
2.4 Parameter Estimation
Currently real world problem is tested and used in the field like computational biology, bioinformatics and medicine by using mathematical model. Usually mathematical model has large number of parameter and the value of these parameters is unknown. In addition, the estimation of parameter is very hard by experimentally and change in parameter can affect the whole outcome. This means that the model is sensitive to change in parameter.
In most field in science and engineering, the used of parameter estimation is crucial as initial steps and validation of mathematical model. In biochemical engineering problems, generally there are necessary to predict/estimate the parameter of model that in nonlinear algebraic or differential equation. Parameter estimation of mathematical model is based on simplification of some of calculated quality and as a function for parameter to estimate (Wang and Sheu, 2000).
Parameter estimation algorithms
2.5 Genetic algorithm
Genetic algorithm(GA) was firstly introduced by John Holland in 1970s. The increasing in price and improvement in computational system has made it useful in some type of optimization. GA is random search based algorithm that useful in nonlinear problem and work very well in continuous and discrete problem. It also has less risk to getting stuck at local optima and tend to be computationally expensive.
The stochastic nature of GA has solved the problem in initialization problem, this lead to consistent in the initial value of parameter because of initial value of parameter can't be measured experimentally.GA is algorithm that search randomly that useful in nonlinear problems and does not require to fix the initial value of parameter estimation.(Ozogur et al.).
In basic GA, it has five components. These are random number generator, a fitness evaluation unit and genetic operators for reproduction, crossover and mutation operations. Basic GA shown below:
1. Initialize population
7. Until requirement are meet
Genetic Algorithm Flowchart
Simplex is a famous algorithm and it is used to solving linear programming problems. Simplex name is given based on the concept of simplex and it is used frequently in optimization process. Simplex algorithm/method consist of several steps and repeatedly moving from vertex v move to an adjacent vertex w so that each step the value of the objective function increasing to obtain higher objective function. Such way to choose w given by v is called as pivot rule. Simplex algorithm is depends on the pivot rule that suggested and were tested over the time.
Generally, simplex can be describe as extremely good performance algorithm. Based on Gil Kalai (1992) stated that in a few steps, the common pivot rule can be reach at maximal vertex which is polynomial in d and n. The number of step in simplex is close to the same as the total number of vertices of the feasible polyhedron. The flowchart of simplex algorithm is shown below.
Flowchart of simplex algorithm
2.7 Swarm Intelligence
Swarm intelligence(SI) is the discipline involving artificial system and natural that have many individuals that coordinate using self-organization or decentralized control (Dorigo and Birattari, 2007). SI metaphor is based on collective behaviors of local individual interaction between itself and their surrounding environment. For example bee colony, ant colony, flocking birds and others. Frenderick et al. describe that swarm intelligence are distributed system that has bottom up design and give the useful and interesting output behavior at the global level consequent from relatively simple action of a number composing units that interaction each other and its surrounding environment at the local level.
Below are the properties of Swarm Intelligence System (Dorigo and Birattari, 2007):
' It composed of large number of individual
' The individual are relatively homogenous
' The interaction between individual are based on simple behavioral rule that exploit the local information that individual exchange through environment
' The overall behaviors must from interaction between individual and also the environment(group of behavior that self organize)
2.7.1 Artificial Bee Colony algorithm
The artificial bee colony algorithm is first proposed by karaboga in 2005, the algorithm is optimizing algorithm that based on the foraging behavior of honey bee swarm. In ABC algorithm, it consist of three components that comprise of food source, employed bee and unemployed bee(onlookers and scouts). The food source is represent the solution of the problem and the bees is the agent for finding the solution. The employed bee is the bee that going to the food source visited previously whereas onlooker is the bee that waiting on the dance area to make decision in choosing a food source and scout is the bee that will searching for randomly.
In ABC also, the amount of nectar in the food source represent the quality(fitness) of the associated solution. In the population, the number of employed/onlooker bee is equal to the number of the solution (Dervis Karaboga et al.,2009).
The main steps of ABC algorithm is shown below:
1. Initialize population
3. Place the employed bees on their food sources in the memory
4. Place the onlooker bees on the food source in the memory
5. Send the scouts to the search area for new food sources
6. Memorize the best food source found so far
7. Until requirements are meet
Each of algorithm cycle consist of three steps:
' sending the employed bee onto their food sources and evaluate fitness of the nectar.
' sharing nectar information of food source, then selection by onlookers and evaluation of the nectar fitness of food source.
' Scout is sent randomly to find new possible food source.
At first step of the cycle, the employed bee share the quality of nectar information with the onlooker in the dance area and onlooker choose the food source. Then employed bee goes back to previous food source due to the food source existing in the memory. At the second steps, the higher the amount of nectar the higher the possibility the food source is chosen by onlooker. Then at third step, the food source that had been abandoned will be replaced by the new food source. The scout bee randomly find the new food source when the quality of food source is bad continually and this enhance the ability in avoiding from local optimum (Huanzhe Li et al, 2010). Each of the cycle, consist of at most one scout that searching a new food source and the number of employed bee and onlooker bees is equal in number. These three step in cycle is repeated until termination criterion are meet.
Flowchart of ABC algorithm
Table of Advantages and disadvantages of ABC.
Easy to implement. Lack of use of secondary information about the problem(gradients).
Broad applicability, even in complex functions,or with continuous, discrete or mixed variables. -
High flexibility, which allows adjustments and the introduction of specific knowledge of the problem by observing nature Requires new fitness tests on the new algorithm parameters to improve performance
It does not require that objective function be differentiable, continuous or mathematically representable.
The possibility of losing relevant information on the behavior of the function to be optimized.
Robust against initialization, regardless of feasibility and distribution of the initial solutions population.
High number of objective function evaluations.
The structure of the algorithm is favourable for parallel processing, thus saving time.
Slow down when used in sequential processing.
Population of solutions (implicit parallelism). Possibility of creating regions of Pareto.
The population of solutions increases the computational cost due to slowdown, many iterations and memory capacity required.
Ability to explore local solutions. Slow to obtain accurate solutions.
Global optimizer, with effective search process even under high complexity, and with low risk of premature convergence.
Deterministic methods have higher accuracy in finding solutions when it does not get stuck in a local minimum.
(Source:Eduardo Gerhardt et al,2012)
2.7.2 Bee Algorithm(BA)
Bee algorithm is an optimization algorithm that inspired by the foraging behaviors of honey bee in finding the optimal way of harvesting honey around hive. This algorithm is proposed by D.T. Pham et al. in 2005. This algorithm is actually mimics the foraging behavior of swarm bee colony. The biggest difference between Artificial Bee Colony algorithm is that BA sent more bee to exploit good quality food source site to obtain high potential solution result and increasing in convergence speed of the algorithm. In addition, the algorithm performs neighborhood search that combined with random search to be used in optimization problem (D.T Pham et al. 2005).
(Source: Pham et al. 2005)
Flowchart of Bee algorithm
2.7.3 Particle Swarm Optimization(PSO)
Particle Swarm Optimization(PSO) is the evolutionary computation technique that introduced in various optimization problem (Eberhart and Kennedy, 1995). This algorithm is initially inspired by behavior of organism such as bird clocking and fish school. The algorithm is well design to increase performance for local and global exploration. The algorithm is begin with generate of random population of solution and then updating generation for optima searches.
In PSO, multiple individual is called particles that the position of each particle is represent of vector of decision in original problem. The movement of each particle in search space is flexible because of velocity of each particle always be updated according to its own flying experience and neighbor particle by memorize the best position encountered (He, Q., Wang, L. 2007). As a result, PSO combine the local search by the particle own experience and global search by sharing neighbor experience to explore and exploit in order to find the global optimum
Basic algorithm for original PSO
2.7.4 Summary of Swarm intelligent algorithm
Below shows the summary of related previous study in parameter estimation using ABC, BA and PSO. The table also listed the title, author, year, tool/software, dataset and result of the related studies.
Algorithm Title Author/year Tool/software & dataset Result
ABC Artificial Bee Colony algorithm for solving optimal power flow problem
Luong Le Dinh et al.(2013)
' IEEE 30-bus, 57-bus, and 118-bus systems ' Successful solving the OPF problem
' Found global solution for optimization problems
Artificial bee colony algorithm for small signal model parameter extraction of MESFET Samrat L. Sabat et al.(2010) Tool:
' MATLAB 2007a
' parameter data of a fabricated MESFET
' MESFET small signal model ' Successful extract small signal model parameters of MESFET with less relative error
BA Protein Conformational Search Using Bees Algorithm
Bahamish et al. (2008) Tool:
' visual C++
' TINKER software tools
' ECEPP/2 force field ' able to find the lowest free energy conformation of 12.91 kcal/mol usign ECEPP/2 force field
Approach to Solve
Functions Based on
' MATLAB 2007
' Blasius Differential Equation
' The parameters were determined and satisfy the boundary conditions
PSO Applying Particle Swarm Optimization to parameter estimation of the nonlinear Muskingum Model
Chu et al. (2009) Tool:
' PSO program in Muskingum model.
' Inflow and outflow Hydrographs ' Improve the accuracy of the flood routing model
2.8 Comparison between ABC, BA, GA and Simplex
ABC, BA, GA and Simplex are search algorithm that used in the parameter estimation. ABC and BA are grouped into meta-heuristic search. Whereas BA is grouped in evolutionary computation and Simplex is algorithm that categorized in linear programming. All of these algorithm has advantage and disadvantage, this as the indicator for determining the performance of the algorithm. A comparison between these algorithm based on global optimum, speed and accuracy features with the description is shown in the table below.
Table of comparison between ABC, BA, GA and Simplex
Features\Estimation algorithm ABC BA GA Simplex
Global optimum Global optimizer with effective in high complexity search and low risk in premature convergence (Eduardo Gerhardt et al,2012)
Ability to explore local solutions(Eduardo Gerhardt et al,2012)
Global optimizer and ignore local optimum (Wang et al. 2011) no guarantee in finding the global optimum May occur prematured termination (Danial Spielman et al. 2000)
Speed The structure of the algorithm fast in parallel processing and slow in sequential processing (Eduardo Gerhardt et al,2012) Fast in finding optimum point and use small test function. Compared to other algorithm, BA is outperformed in speed (Elsevier, 2007) Slow and likely to fall into premature convergence (Wenshan, 1996) Not rely on the gradient so it may converge slowly or does not converge at all (Danial et al. 2000)
Accuracy Have higher accuracy in finding solutions if does not stuck in local minimum (Eduardo Gerhardt et al,2012) can converge and does not trapped at local optima (Pham et al. 2006) Accuracy can't be guaranteed (Liu et al. 2000) Low in accuracy because of tendancy to local optimum (Daniel, 2000)
2.9 Problems and Challenges
Parameter estimation widely used in estimating of optimal parameter in biological kinetic model. Nevertheless, estimation of the optimal parameter always have problem with error and most of the parameter estimate often has doubt in minimize the gap between model and data. According to Gutenkunst et al. studied that parameter estimation in 17 published model that in system biology field, come in conclusion that parameter estimation in biology often hard due to having large number of measurement error and model behavior is often insensitive due to change in parameter values.
Nowdays, there are a lot of available parameter estimation algorithm that can be used in simulated the kinetic model. Nevertheless in choosing the right algorithm for suitable subject, there are few guidance to choose most optimal algorithm. So, ABC algorithm is used to enhance the accuracy and performance of the kinetic model by finding the optimal parameter value.