https://www.dagstuhl.de/16071
February 14 – 19 , 2016, Dagstuhl Seminar 16071
Pattern Avoidance and Genome Sorting
Organizers
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)
For support, please contact
Documents
Dagstuhl Report, Volume 6, Issue 2
Aims & Scope
List of Participants
Dagstuhl's Impact: Documents available
Dagstuhl Seminar Schedule [pdf]
Summary
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.


Dagstuhl Seminar Series
- 23121: "Pattern Avoidance, Statistical Mechanics and Computational Complexity" (2023)
- 18451: "Genomics, Pattern Avoidance, and Statistical Mechanics" (2018)
Classification
- Data Structures / Algorithms / Complexity
- Semantics / Formal Methods
- Soft Computing / Evolutionary Algorithms
Keywords
- Permutations
- Patterns
- Sorting
- Lists
- Evolutionary distance
- Metrics