Python Programming for Biology: Bioinformatics and Beyond

Figure 25.1.  The travelling salesman problem as an example of a hard problem.

Using the map coordinates of cities in France as an example, the route that minimises the

total journey distance between all cities is an example of a hard problem that cannot be

solved by classic minimisation techniques. Here the number of possible routes, with no

fixed starting or end points, is 15! = 1,307,674,368,000, or half that number if we consider

reverse routes to be the same. Because it is often impractical to test all possible routes we

can use methods like Monte Carlo, or Monte Carlo in combination with simulated

annealing, to find a good solution in a reasonable time. The illustrated route is the

optimum solution found by the Python functions described later in this chapter.

Problems  of  this  kind  are  a  vast  topic  that  we  can  only  touch  upon  lightly.  However,

using Python examples we will illustrate a few core techniques, which are commonly used

to  solve  complex  problems  in  general.  Accordingly  we  will  describe  the  Monte  Carlo

method,  simulated  annealing,  particle  dynamics  and  Markov  chains.  These  will  then  be

applied  to  situations  that  a  biologist  will  be  passingly  familiar  with.  Unfortunately  there

will not be room to include descriptions of other methods, such as genetic algorithms or

bounded  tree  traversal.  It  is  worth  noting,  however,  that  the  methods  described  are

complementary  to  the  machine  learning  approaches  described  in

Chapter  24

,  which  are

good at recognising patterns and approximating functions in complex systems: useful for

getting good heuristics.