http://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

Dagstuhl Service Team

Documents

Dagstuhl Report, Volume 6, Issue 2 Dagstuhl Report
Aims & Scope
List of Participants
Shared Documents
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.

License
  Creative Commons BY 3.0 Unported license
  Miklós Bóna

Related Dagstuhl Seminar

Classification

  • Data Structures / Algorithms / Complexity
  • Semantics / Formal Methods
  • Soft Computing / Evolutionary Algorithms

Keywords

  • Permutations
  • Patterns
  • Sorting
  • Lists
  • Evolutionary distance
  • Metrics

Book exhibition

Books from the participants of the current Seminar 

Book exhibition in the library, ground floor, during the seminar week.

Documentation

In the series Dagstuhl Reports each Dagstuhl Seminar and Dagstuhl Perspectives Workshop is documented. The seminar organizers, in cooperation with the collector, prepare a report that includes contributions from the participants' talks together with a summary of the seminar.

 

Download overview leaflet (PDF).

Publications

Furthermore, a comprehensive peer-reviewed collection of research papers can be published in the series Dagstuhl Follow-Ups.

Dagstuhl's Impact

Please inform us when a publication was published as a result from your seminar. These publications are listed in the category Dagstuhl's Impact and are presented on a special shelf on the ground floor of the library.

NSF young researcher support