Dagstuhl Seminar 18451
Genomics, Pattern Avoidance, and Statistical Mechanics
( Nov 04 – Nov 09, 2018 )
(Click in the middle of the image to enlarge)
Permalink
Please use the following short url to reference this page:
https://www.dagstuhl.de/18451
Organizers
- Michael Albert (University of Otago, NZ)
- David Bevan (University of Strathclyde - Glasgow, GB)
- Miklós Bóna (University of Florida - Gainesville, US)
- István Miklós (Alfréd Rényi Institute of Mathematics - Budapest, HU)
Contact
- Michael Gerke (for scientific matters)
- Jutka Gasiorowski (for administrative matters)
Impacts
- Investigating the complexity of the double distance problems - Braga, Marilia D. V.; Brockmann, Leonie R.; Klerx, Katharina; Stoye, Jens - London : BMC, 2024. - 20 pp - (Algorithms for Molecular Biology ; 19. 2024, 1).
- A Linear Time Algorithm for an Extended Version of the Breakpoint Double Distance : article in 22nd International Workshop on Algorithms in Bioinformatics - Braga, Marilia D. V.; Brockmann, Leonie R.; Klerx, Katharina; Stoye, Jens - Wadern : LZI, 2022. - pp. 1-16 - (Leibniz International Proceedings in Informatics ; 242).
- On the Class of Double Distance Problems : article in Comparative Genomics - Braga, Marilia D. V.; Brockmann, Leonie R.; Klerx, Katharina; Stoye, Jens - Heidelberg : Springer, 2023 - (Lecture notes in bioinformatics ; 13883 : article).
Schedule
This event will bring together computational and mathematical biologists who are active in the field of genomics, computer scientists and mathematicians studying pattern avoidance, and mathematicians and physicists whose area of research is statistical mechanics.
There are many tantalising connections between these three fields. Examples include the following.
In the simplest form the problem of gene rearrangements corresponds to sorting by reversals. The permutations that are hardest to sort in this way are known as increasing oscillations, and are fundamental to the study of permutation classes.
The partially asymmetric simple exclusion process (PASEP) is a generalization of a one-dimensional gas model, exhibiting boundary-driven phase transitions and spontaneous symmetry-breaking. Properties of the PASEP are directly connected to counting occurrences of the vincular pattern 2-13 in permutations and to the combinatorics of permutation tableaux.
Evolution in viral populations can be modelled by theories of quasi-species. These theories have captured the attention of the statistical mechanics community since it was shown that they could be represented by a type of two-dimensional Ising model, the macroscopic distribution of the population corresponding to surface magnetization.
However, despite the existence of these links, there is little interaction between the different communities. The goals of this seminar are to
- build bridges between the three areas by bringing together experts from each field,
- identify themes and models that are common across the three areas,
- detail avenues of possible future research and define project ideas for cooperation between the communities.
In addition to presentations of recent research results, the Dagstuhl Seminar will include expository talks explaining the specific interests and questions of each community to the other two. The programme will also contain lectures surveying the interfaces between each pair of communities. In addition, there will be sessions on questions that are common to two or more of the fields. Opportunities will be provided for the discussion of open problems and other topics of shared interest.
Creative Commons BY 3.0 DE
Michael Albert, David Bevan, Miklós Bóna, and István Miklós
This report documents the program and the outcomes of Dagstuhl Seminar 18451 "Genomics, Pattern Avoidance, and Statistical Mechanics".
The workshop took place from November 4, 2018 to November 9, 2018. It had 40 participants, who were researchers in theoretical computer science, combinatorics, statistical mechanics and molecular biology. It was a geographically diverse group, with participants coming from the US, Canada, Brazil, Germany, Iceland, the United Kingdom, Sweden, France, Switzerland, Hungary, Australia, and New Zealand. The workshop featured 21 talks, three of which were hourlong talks, and an open problem session.
Several collaborative projects have been started. For example, Jay Pantone Michael Albert, Robert Brignall, Seth Pettie, and Vince Vatter started exploring the topic of 1324-avoiding permutations with a bounded number of descents, disproving a 2005 conjecture of Elder, Rechnitzer, and Zabrocki related to Davenport-Schinzel sequences. Had the conjecture been affirmed, it would have implied that the generating function for 1324-avoiding permutations is non-D-finite.
At the open problem session, Yann Ponty raised the following question: what is the number of independent sets in restricted families of trees, like caterpillars or complete binary plane trees? The main motivation for this question relates to a deep connection between such independent sets and RNA designs. This question led to a new collaborative effort by Mathilde Bouvel, Robert Brignall, Yann Ponty and Andrew Elvey Price.
Sergi Elizalde and Miklós Bóna have started working on Dyck paths that have a unique maximal peak. That collaboration since extended to the area of probabilistic methods, involving a researcher working in that field, Douglas Rizzolo.
Numerous participants expressed their pleasure with the workshop and its sequence of talks. The prevailing view was that while the participants came from three different fields, they were all open to the other two fields, and therefore, they all learned about results that they would not have learned otherwise. Therefore, we have all the reasons to believe that the workshop was a success, and we would like to repeat it some time in the future.
Miklós Bóna
- Michael Albert (University of Otago, NZ) [dblp]
- David Bevan (University of Strathclyde - Glasgow, GB) [dblp]
- Heather Blake (Davidson College, US) [dblp]
- Miklós Bóna (University of Florida - Gainesville, US) [dblp]
- Mathilde Bouvel (Universität Zürich, CH) [dblp]
- Marilia Braga (Universität Bielefeld, DE) [dblp]
- Robert Brignall (The Open University - Milton Keynes, GB) [dblp]
- Cedric Chauve (Simon Fraser University - Burnaby, CA) [dblp]
- Anders Claesson (University of Iceland - Reykjavik, IS) [dblp]
- Michael W. Deem (Rice University - Houston, US) [dblp]
- Sergi Elizalde (Dartmouth College - Hanover, US) [dblp]
- Andrew Elvey Price (The University of Melbourne, AU) [dblp]
- Péter L. Erdös (Alfréd Rényi Institute of Mathematics - Budapest, HU) [dblp]
- Guillaume Fertin (University of Nantes, FR) [dblp]
- Yoong Kuan Goh (University of Technology - Sydney, AU) [dblp]
- Torin Greenwood (Rose-Hulman Inst. of Technology - Terre Haute, US) [dblp]
- Sylvie Hamel (Université de Montréal - Québec, CA) [dblp]
- Christine Heitsch (Georgia Institute of Technology - Atlanta, US) [dblp]
- E. J. Janse van Rensburg (York University - Toronto, CA) [dblp]
- László Kozma (FU Berlin, DE) [dblp]
- Anthony Labarre (University Paris-Est - Marne-la-Vallée, FR) [dblp]
- Olya Mandelshtam (Brown University - Providence, US) [dblp]
- István Miklós (Alfréd Rényi Institute of Mathematics - Budapest, HU) [dblp]
- Alois Panholzer (TU Wien, AT) [dblp]
- Jay Pantone (Marquette University, US) [dblp]
- Seth Pettie (University of Michigan - Ann Arbor, US) [dblp]
- Yann Ponty (Ecole Polytechnique - Palaiseau, FR) [dblp]
- Svetlana Poznanovik (Clemson University, US)
- Thomas Prellberg (Queen Mary University of London, GB) [dblp]
- Pijus Simonaitis (University of Montpellier 2, FR) [dblp]
- Fiona Skerman (Uppsala University, SE) [dblp]
- Jakub Sliacan (University of Umeå, SE) [dblp]
- Jason Smith (University of Aberdeen, GB) [dblp]
- Rebecca Smith (The College at Brockport, US) [dblp]
- Einar Steingrimsson (University of Strathclyde - Glasgow, GB) [dblp]
- Jens Stoye (Universität Bielefeld, DE) [dblp]
- Jessica Striker (North Dakota State University - Fargo, US) [dblp]
- Krister Swenson (University of Montpellier & CNRS, FR) [dblp]
- Vincent Vatter (University of Florida - Gainesville, US) [dblp]
- Stéphane Vialette (University Paris-Est - Marne-la-Vallée, FR) [dblp]
Related Seminars
Classification
- bioinformatics
- data structures / algorithms / complexity
- modelling / simulation
Keywords
- permutation patterns
- genomics
- algorithms
- modeling
- evolutionary distance
