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.

• Michael Albert (University of Otago, NZ) [dblp]
• David Bevan (The Open University - Milton Keynes, GB) [dblp]
• Miklós Bóna (University of Florida - Gainesville, US) [dblp]
• Mathilde Bouvel (Universität Zürich, CH) [dblp]
• Marilia Braga (Inmetro - Duque de Caxias, BR) [dblp]
• Brona Brejova (Comenius University in Bratislava, SK) [dblp]
• Robert Brignall (The Open University - Milton Keynes, GB) [dblp]
• Cedric Chauve (Simon Fraser University - Burnaby, CA) [dblp]
• Anders Claesson (University of Strathclyde, GB) [dblp]
• Péter L. Erdös (Alfréd Rényi Institute of Mathematics - Budapest, HU) [dblp]
• Niklas Eriksen (University of Örebro, SE) [dblp]
• Pedro Feijão (Universität Bielefeld, DE) [dblp]
• Guillaume Fertin (University of Nantes, FR) [dblp]
• Sylvie Hamel (University of Montréal, CA) [dblp]
• Vít Jelínek (Charles University - Prague, CZ) [dblp]
• Anthony Labarre (University Paris-Est - Marne-la-Vallée, FR) [dblp]
• Marie-Louise Lackner (TU Wien, AT) [dblp]
• Martin Lackner (University of Oxford, GB) [dblp]
• Megan Martinez (Ithaca College, US)
• István Miklós (Alfréd Rényi Institute of Mathematics - Budapest, HU) [dblp]
• Jay Pantone (Dartmouth College - Hanover, US) [dblp]
• Adeline Pierrot (University of Paris South XI, FR) [dblp]
• Yann Ponty (Ecole Polytechnique - Palaiseau, FR) [dblp]
• Svetlana Poznanovik (Clemson University, US)
• Manda Riehl (University of Wisconsin - Eau Claire, US) [dblp]
• Bruce Sagan (Michigan State University - East Lansing, US) [dblp]
• David Sankoff (University of Ottawa, CA) [dblp]
• Rebecca Smith (The College at Brockport, US) [dblp]
• Einar Steingrimsson (University of Strathclyde, GB) [dblp]
• Jens Stoye (Universität Bielefeld, DE) [dblp]
• Krister Swenson (University of Montpellier 2, FR) [dblp]
• Eric Tannier (University Claude Bernard - Lyon, FR) [dblp]
• Vincent Vatter (University of Florida - Gainesville, US) [dblp]
• Stéphane Vialette (University Paris-Est - Marne-la-Vallée, FR) [dblp]
• Tomas Vinar (Comenius University in Bratislava, SK) [dblp]