Playing the Mastermind Game

¡°Quick, let¡¯s take these seats here, right behind those two girls! I fell in love with the brunette!¡± Nico grabbed my arm and pushed me towards the coach that took us to a snow tour in the Alps. Nico fell in love several times a day, so I was not particularly excited as I followed his instructions.

The two women sitting in front of us were absorbed in a game of Mastermind. One woman selected a hidden sequence of 4 coloured pegs, each peg being one of 6 possible colours. The other tried to guess this sequence by proposing a 4-peg colour sequence. She was told how many pegs were exactly in the right place, and how many pegs had the right colour, as depicted in Figure 1. Her goal was to find the hidden sequence in as few iterations of questions and answers as possible.

¡°Do you know of any good strategies for playing Mastermind?¡± Nico asked me, one eye on the women, pretending to be interested in the theory of the game. By chance, I remembered a solution derived in 1977 by the famous computer scientist Donald Knuth. ¡°Yes¡±, I replied, ¡°it goes like this: consider a candidate sequence for your next move. Any answer will hopefully reduce the number of remaining possible solutions; however, there is a worst-case scenario, which leaves the maximum number of alternatives. Among all candidate sequences, you should choose one for which this number is minimal. While seemingly simple, Knuth proved that this algorithm solves the game in at most 5 rounds!¡±.

Nico noticed that my answer failed to catch our fellow passengers¡¯ attention. ¡°Sounds funny, but what the hell does such stuff help in real life?¡± ¡°Actually, as a computational biologist, I play a kind of Mastermind game every day! My ¡®pegs¡¯ are molecules that transmit signals within a cell. For example, when a sensor molecule on the cell surface realizes that a virus attacks, it transmits this information to a messenger molecule, which in turn activates a cascade of molecules, until the signal reaches the nucleus, the control centre of the cell, where it invokes countermeasures against infection. If we knew exactly which signalling sequences were involved, we could better help the cell to resist the virus attack. My task is to guess the right cascade of molecules, just as in the game. Unfortunately, the type of questions I am able to ask, and the answers I get are much less informative. Our standard question is a so-called knockout experiment, a procedure in which one molecule is completely removed from the cell. As an answer, we observe changes in the behaviour of the cell¡±.

Nico was momentarily distracted from the centre of his attention and countered, ¡°But if you only had the option to test one peg per guess in the Mastermind game, it would take forever; moreover, the number of molecules potentially involved in a signalling cascade, and therefore the number of hidden combinations, is a zillion times larger than in the game! Isn¡¯t your goal completely hopeless?¡±.

¡°Yes, it would have been if biologists had not made a series of breakthrough discoveries. First, a Nobel-Prize winning method suggested by Craig Mellow and Andrew Fire in 1998 allows us to ask more complex questions, i.e., to simultaneously remove a number of molecules. Secondly, technologies have been developed that measure thousands of molecule concentrations per cell, providing not only one answer, but thousands of quantitative responses to our question. We have developed a mathematical model that can analyse these answers to discern between signalling cascades that do or do not fit the measurements, and that analysis guides the design of future experimental guesses. Like in the game, it is hopeless to try things out by brute force, but it becomes a feasible task if you employ a good strategy. My job is to solve the Mastermind game in biology¡±.

Obviously, our discussion did not solve the problem Nico had on his mind. When leaving the coach, Nico launched the frontal attack: ¡°Ladies, will you join our snowboard tour today? We could meet at the summit station.¡± ¡°Hey, nice idea!¡± they smiled back at us, ¡°See you there at, say, 2 pm!¡± Apparently relieved, Nico turned to me and murmured: ¡°You almost messed it up with your Mastermind talk! Remember, it may be helpful for biology in theory, but not in practice!¡±.