Combinatorics of Genome Rearrangements
Given a permutation written in the one-line notation, such as 3147526, it is natural to ask how many block transpositions (interchanges of two adjacent substrings) are needed to turn this permutation into the increasing one. This has turned out to be a surprisingly difficult problem, and a long-standing conjecture has recently been disproved in this area.
If, on the other hand, we are allowed to interchange any two blocks, then the best sorting algorithm is known. The average number of necessary block interchanges has recently been computed, using some very unexpected tools from remote-looking areas of mathematics.
In this talk, we will review the results and open problems of these two families of questions, and suggest another interesting open problem connected to them. We will say a few words about the biological motivation of these questions, and discuss some of their variations as well.
No previous knowledge of sorting algorithms is necessary, and the talk will be accessible to students.