14.02.16 - 19.02.16, Seminar 16071

Pattern Avoidance and Genome Sorting

Diese Seminarbeschreibung wurde vor dem Seminar auf unseren Webseiten veröffentlicht und bei der Einladung zum Seminar verwendet.


This Dagstuhl Seminar aims to bring together computer scientists and mathematicians who are active in the field of pattern avoidance and mathematical biologists who are active in the field of genome rearrangement and who study various notions of evolutionary distance between species.

Patterns are a natural concept in the study of various properties of permutations (and many other mathematical structures), and have as such appeared implicitly, albeit sporadically, in the literature for over a hundred years. It is, however, only in the last couple of decades that they have been studied systematically, and they have only been emerging as an independent research field in the last ten years. Enumerating down-sets of permutations under this order has provided intriguing problems to researchers in both enumerative and extremal combinatorics, two communities that rarely interact.

On the mathematical biology side, it occurs in many cases that two different species have very similar genes, but these genes occur in a different order on the chromosomes of the two species; one famous example of this involves cabbages and turnips, which share 99 percent of their genes. The theory of genome rearrangements studies the way in which two different genomes might evolve from a common ancestor via certain fundamental mutations, such as reversals. The combinatorics of genome rearrangement sometimes reveals unexpectedly deep connections with other parts of mathematics.

There are many tantalizing connections between genome rearrangements and permutation patterns. For example, the permutations that are hardest to sort by reversals are also fundamental to the study of permutation patterns, where they are known as increasing oscillations. For another example, a Markov chain Monte Carlo method for sorting permutations with reversals, transpositions and reverted transpositions based on the fast searching of certain small patterns in the permutation has recently been developed. The absence of such patterns indicates cases that are hard to sort. It would be important to know what fraction of the permutations avoid easy-to-sort patterns.

As the examples above show, concepts and methods from the theory of patterns crop up in genome rearrangement problems, and problems arising in the latter area often have natural partners in the former. This seminar will bring together researchers from these two fields in order to spur more active collaborations between the two disciplines.