Biomedical Engineering Reference
In-Depth Information
and simulation, notably the Monte Carlo methods.
Monte Carlo Method
An approach developed through the collaboration of a computer scientist, physicist, and
mathematician, the Monte Carlo method, forms the basis for much modeling and simulation activity
in bioinformatics. The Monte Carlo method, named after the famous Monaco casino, involves running
multiple repetitions of a model, gathering statistical data, and deriving behaviors of the real-world
system based on these models. Each run of a model represents chance behaviors that cannot be
modeled exactly, but only characterized statistically. Monte Carlo methods are particularly useful in
modeling systems that have a large number of degrees of freedom and quantities of interest. The
first uses of the method were in nuclear physics and various military applications. Today, Monte Carlo
methods are used in bioinformatics for applications ranging from optimizing the drug discovery
process to protein structure prediction.
Metropolis Algorithm
The most important variant of the basic Monte Carlo method used in bioinformatics work is the
Metropolis Algorithm. The Metropolis Algorithm is useful in the minimization problems that are
common in performing likelihood fits and optimization problems. For example, consider the function
graphed in
Figure 9-8
. Within the boundaries defined by
x
1 and
x
2,
A
and
B
are local minima and
C
is
the global minimum. The general problem is to find
x
so that it minimizes
f(x)
with as few function
calls as possible. The caveat is that the formula for solving
f(x)
is non-trivial and may be
computationally intractable using ordinary means. One of the pitfalls of solving for
f(x)
through
ordinary means is that the solution may be stuck at a local minima, such as
A
or
B
in the figure. That
is, the algorithm determines that
f(x)
increases to either side of a local minima, and therefore settles
down in the local minima, ignoring the global minimum.
Figure 9-8. A function with local minima (
A
and
B
), global minimum (
C
),
and global maximum (
D
) within the boundaries defined by
x
1 and
x
2.
