Dagstuhl Seminar 16071
Pattern Avoidance and Genome Sorting
( Feb 14 – Feb 19, 2016 )
- Michael Albert (University of Otago, NZ)
- Miklós Bóna (University of Florida - Gainesville, US)
- István Miklós (Alfréd Rényi Institute of Mathematics - Budapest, HU)
- Einar Steingrimsson (University of Strathclyde, GB)
- Annette Beyer (for administrative matters)
- A Bijection between the set of nesting-similarity classes and L&P matchings - Martinez, Megan A.; Riehl, Manda - Cornell University : arXiv.org, 2017. - 9 pp..
- Computational Complexity of Counting and Sampling - Miklos, Istvan - Boca Raton : CRC Press, 2019. - 390 pp. - (Discrete Mathematics and Its Applications). ISBN: 978-1-13-803557-7 / 1-13-803557-2.
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.
The seminar took place from February 14, 2016, to February 19, 2016. It had 36 participants, who were researchers in theoretical computer science, combinatorics, and molecular biology. It was a geographically diverse group, with participants coming from the US, Canada, Brazil, Germany, Iceland, the United Kingdom, Sweden, France, Slovakia, Hungary and New Zealand. The seminar featured 18 talks, three of which were hourlong talks, and an open problem session.
Numerous collaborative research efforts have been started. Here is a sampling.
Megan Martinez and Manda Riehl worked on a bijection between LP matchings (one of the RNA matchings described in Vincent Vatter's talk) and Klazar's nesting equivalent matchings. They studied a paper by Klazar and Aziza Jefferson's dissertation and made progress on the bijection.
István Miklós, Péter Erdös and Miklós Bóna worked on proving a log-convexity conjecture related to ordered degree sequences of bipartite graphs.
Brona Brejova and Manda Riehl discussed two potential future projects related to gene and species tree reconciliation. The most probable starting point is a project involving gene and species trees where a gene is allowed to duplicate a string inside itself. This situation was not allowed in previous models, however it seems that as long as the specific breakpoints are not reused from this insertion, a modification of the previous algorithms could still be effective.
Jay Pantone, David Bevan and Miklós Bóna collaborated on asymptotic enumeration of a balanced urns and balls model that was seen to be a step towards finding a better upper bound for a pattern avoidance enumeration problem.
We have all the reasons to believe that this, and many other joint research efforts that started during this seminar will lead to new results that would not have been possible without the seminar. Therefore, we strongly believe that the seminar was a success that we would like to repeat at some point in the future.
- 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]
- data structures / algorithms / complexity
- semantics / formal methods
- soft computing / evolutionary algorithms
- evolutionary distance