
DNA normally evolves by tiny mutations, but every now and then something more radical occurs, and the order of entire genes along a chromosome is rearranged. Understanding these rearrangements is an important task, shedding light on the process of evolution. It boils down to solving a problem from pure mathematics: an instance of the many connections between maths and biology that have become increasingly apparent in recent years. In this article we'll explore this problem, embarking on a journey from waiters sorting pancakes, via one of the richest men in the world, to the genetic similarities of mice and humans.
Pancake sorting
In 1975 Jacob E. Goodman (under the pseudonym Harry Dweighter) posed the following problem:
The chef in our place is sloppy, and when he prepares a stack of pancakes they come out all different sizes. Therefore, when I deliver them to a customer, on the way to the table I rearrange them (so that the smallest winds up on top, and so on, down to the largest at the bottom) by grabbing several from the top and flipping them over, repeating this (varying the number I flip) as many times as necessary. If there are n pancakes, what is the maximum number of flips (in terms of n) that I will ever have to use to rearrange them?

Pancakes hold the secret to gene flipping along chromosomes.
We can model this as a permutation sorting problem. A permutation
Harry Dweighter's question is therefore:
Given a whole number
It's never going to be harder than...
One easy sorting method proceeds as follows:
- Find the biggest entry in the current permutation that's in the wrong place: let's say it's number
in position . - Reverse the first
entries, so that is now in position . - Reverse the first
entries, so that the number is now correctly in position . - Go back to step
and repeat, until the whole permutation is sorted.

Want a neater stack?
As an example, suppose that we have four pancakes with
So the answer to Harry Dweighter's question is either equal to the number of reversals required to complete this method, or, if there is a better method, it is smaller. In other words, the number of reversals needed to complete this method is an upper bound on the difficulty of the problem. With this method, each number takes at most two flips to end up in the right place, except that
And it's never going to be easier than...
What about a lower bound? Answering Harry Dweighter's question is equivalent to finding the permutation that is hardest to sort and counting the number of flips required to sort it. We don't know what this hardest permutation is, but if we can find one that is reasonably hard, then this will give us a reasonably good lower bound on the difficulty of the problem: we know that sorting the hardest permutation is probably going to be harder than this, but hopefully not that much harder. As a measure of "hardness" we look for consecutive entries that differ by 1. If this is the case for a pair of consecutive entries

Bill Gates, an unlikely pancake flipper. Image: World Economic Forum.
The first significant improvement on the upper bound of
So we have some grim news for our poor harried waiter: in the worst case, it will take him between
Burnt Pancakes
Unfortunately, if the chef is even more careless and burns one side of the pancake, and our waiter needs to serve the pancakes with their unburnt side up, then his situation gets even bleaker. This can be modelled as a signed permutation, where we write over- and underlines on the entries to indicate their burnt sides. For example, if the pancakes are given to the waiter as
An extra plate
In response to the increasingly wayward chef, the waiter has a brilliant idea. He puts the plate of pancakes down, and uses a second plate. He first slides a batch of pancakes, still the same way up, onto the spare plate. Now he can flip the remaining pancakes as before -- flipping some initial part of this bottom stack -- before returning the original pancakes back to the top of the pile. So for example, given
3 | 1 | 5 | 2 | 7 | 4 | 9 | 6 | ... | n-6 | n-1 | n-4 | n | n-2 | if n is even, |
3 | 1 | 5 | 2 | 7 | 4 | 9 | 6 | ... | n-2 | n-5 | n | n-3 | n-1 | if n is odd. |
and consist of two subsequences (here coloured red and blue), both increasing.
If the chef burns one side of each pancake, the two plate system fares only slightly worse: every signed permutation can be sorted with at most
Mice in the kitchen
It turns out that evolutionary processes flip genes in the same way as our waiter flips pancakes: soon we'll see a sequence of flips that takes us from mice to men.
Rather than a stack of pancakes, a chromosome is an ordered list of genes, a sequence. (Genes themselves are a subsequence of the long DNA molecule, the Science Education Foundation has a good illustration on how these relate to each other.) Normally genes evolve by tiny mutations, but every now and then something more radical occurs and entire genes get flipped: we're talking the two plate flipping technique here, as this can occur anywhere in the chromosome. Understanding gene flipping gives important clues about how an organism evolved. For example, two versions of a virus that are in fact quite closely related can look extremely different, if we look at the details within each gene. However, their similarities become more obvious if we concentrate instead on the broader picture: the sequence of genes along the chromosome. Furthermore, genes have beginnings and ends, so we can denote one direction of a gene by an underline and the reverse direction by an overline, enabling us to model chromosomes as signed permutations.

Close relatives.
Sticking with the food theme for now, let's look at a pair of vegetables. Despite outward appearances, cabbages and turnips are more similar than you might think. In fact, many of their genes are 99\% identical in content, but they come in a different order in the two different vegetables. For example, if we look at one sequence of five genes shared between turnips and cabbages, and label them as
Training is everything. The peach was once a bitter almond; cauliflower is nothing but cabbage with a college education.
About this article
Colva Roney-Dougal is a lecturer in Pure Mathematics at the University of St Andrews. She initially went to university to study English and Moral Philosophy, but got distracted along the way and wound up with a maths degree. Since then she has worked at Queen Mary, University of London and the University of Sydney. She is interested in symmetry and computation.
Vince Vatter is currently a John Wesley Young Research Instructor at Dartmouth College in New Hampshire. Born in Michigan, Vince received his PhD in mathematics from Rutgers University, and then spent two years across the pond as a research fellow at the University of St Andrews.
Colva and Vince have yet to make pancakes together.
Comments
Burnt Pancakes
Actually the first author on the burnt pancake problem was David (not Daniel) S. Cohen. These days he's better known as David X. Cohen, executive producer of Futurama.