Laurent Bulteau, University Gustave Eiffel, France
Title talk: Tutorial on Parameterized Algorithms and Complexity with Longest Common Subsequence
Short abstract: Parametrized techniques have become an important algorithmic tool to address many difficult problems. They lead to fine-grained algorithms and complexity results and help pinpoint the true source of complexity of a problem. Even though parameterized theory thrived on graph-based questions, the same toolbox also applies to many other areas, and especially sequence-based problems. In this talk we will present parameterized algorithmic techniques applied to a famous stringology problem: Longest Common Subsequence. More precisely, we will show that the problem becomes Fixed-Parameter Tractable if we consider inputs with many similar strings, and that it is W[1]-hard if only one string is similar to the solution.
Jessica Enright, University of Glasgow, UK
Title talk: Algorithms for temporal graphs
Short abstract: Temporal graphs are graphs in which the edges are only active at specified times – this allows us to model (for example) contact processes that change over time. I will discuss basics of temporal graphs, give some practical examples that inspired me to start working with them, and outline several examples of computational problems on temporal graphs. I will then give examples of parameterised approaches on temporal graphs and discuss the usefulness of several different parameters.
Fedor Fomin, University of Bergen, Norway
Title talk: When Distances Lie: Euclidean Embeddings in the Presence of Outliers and Distance Violations
Short abstract: Distance geometry studies the properties of metric spaces that can be represented as pairwise Euclidean distances between points in Euclidean space. In this talk, we present algorithms for deciding whether a given distance space can be isometrically embedded into a d-dimensional Euclidean space after a limited number of modifications. We discuss kernelization and fixed-parameter tractable (FPT) algorithms for this problem.
This talk is based on joint work with Matthias Bentert, Petr Golovach, M. S. Ramanujan, and Saket Saurabh.
Kurt Mehlhorn, Max Planck Institute for Informatics, Germany
Title talk: Matchings in Graphs: Algorithm, Implementation, Experiments
Yann Ponty, École Polytechnique, France
Title talk: RNA design: Probably hard, certainly combinatorial!
Short abstract: RNA design is a discipline in Computational Biology aiming at the production of RNAs sequences targeting a predefined function. Design targets a wide diversity of objectives, for instance: encoding a given amino-acids sequence; optimizing levels of translation; evading degradation by nucleases; expose specific recognition sites towards interaction with partners; adopt alternative conformations depending of presence/absence of metabolites. On a computational level, RNA design can usually be tackled as a search/random generation of sequences featuring/avoiding motifs, compatible with one or several structures, or adopting a predefined structure as its unique energy-minimizing conformation (aka inverse folding). Most associated problems are difficult in the sense of complexity theory ((NP/#P)-hard), but are highly relevant in practice, and arguably deserving of a CS perspective.
In this talk, I will present an overview of the field, and the relevance of key computational problems in the context of health and synthetic biology. I will describe recent contributions towards practically solving several RNA design problems, using concepts from graph theory and parameterized complexity. In particular, I will show that the generation of sequences simultaneously compatible with several RNA structures has strong connection with the enumeration of stable sets in Bipartite graphs. One can then use graph decompositions to obtain a parameterized complexity solution for the uniform/Boltzmann weighted generation of designs. We further generalized this approach to general set of constraints, and implemented it within a generic solver/sampler, named infrared and applicable to a variety of applications in Bioinformatics and beyond. If time allows, I will highlight the inverse folding problem, and show that the structure of its objective function implies the existence of undesignable local motifs, the absence of which ends up massively depleting the set of designable structures. I will finally mention recent results for generating, in linear-time, solutions to the (NP-hard) inverse folding for reasonable subsets of targeted structures. Overall, RNA design is a subfield of Bioinformatics that is both mature and gaining in momentum. It features problems that both showcase the relevance of modern algorithmic techniques, and are certainly worthy of further attention from the graph/algorithms community.
This work is based on multiple collaboration including (but not limited to) Danny Barash, Théo Boury, Laurent Bulteau, Cédric Chauve, Alain Denise, Stefan Hammer, Alice Héliou, Jan Manuch, Bertrand Marchand, Ladislav Stacho, Wei Wang, Sebastian Will, Hua-Ting Yao…
Romeo Rizzi, University of Verona, Italy
Title talk: An overview of the framework of safety
Short abstract: This talk introduces the “safeness” framework via a couple of examples. This framework offers a new perspective and opportunities of enquiry and applications for both new and classical models in algorithmic discrete mathematics. One of the aspects of bioinformatics that fascinates many is that, given partial and fragmented information on some hidden reality, you want to reconstruct the likely truth underneath, at least for as much as you can (the problem might well be ill-posed if taken at face value). On one hand, this displaces the classical algorithmic approach in Computer Science and Discrete Optimization. However, on the other hand, it sets off a new range of intriguing questions that rekindle curiosity even around old classical models. The border on what is tractable can shift when your ambition around a model rotates and twists, but a structural viewpoint remains king. With this, we enjoy the best of two worlds: a new cave rich in puzzling but practically relevant problems and an empowering feeling of an underground methodological continuity. I hope this overview may serve as an invitation to open discussions and exchanges or attract interest in the “safeness” perspective both in old and new models and settings. Not only for the days of the meeting, nor in small circuit. My involvement in “safeness” cames from a collaboration with Alexandru Tomescu’s bioinformatics group in Helsinki and relates to general themes and trends in bioinformatics that this group has identified, cultivated, and fostered. The main such theme is indeed the “safeness” framework, wich to the group serves as a unified technological perspective. This project and commitment has received important EU fundings that have allowed the group to thrive while supporting the formation of a new generation of young and motivated researchers (including my best PhD students in Verona).
Two examples: safe paths within de Bruijn graphs, safe trails within the possible decompositions of a network flow into flow paths.
Related concepts: safety, persistency, kernels of optimal solutions in combinatorial optimization, backbones for Boolean satisfiability.
Blerina Sinaimeri, LUISS University Rome, Italy
Title talk: Mathematical and Algorithmic Perspectives on Host-Symbiont Coevolution
Short abstract: Reconstructing the joint evolutionary history of hosts and their symbionts is a central problem in evolutionary biology, with applications ranging from biodiversity studies to tracing emerging infectious diseases. Cophylogeny provides a formal framework for modeling these interactions, typically by reconciling parasite phylogenies with those of their hosts through a set of evolutionary events. In this talk, we will review the main methodological approaches to cophylogeny, with a focus on algorithmic strategies and their computational complexity. Particular attention will be given to the combinatorial structure of reconciliation spaces as well as to the many open problems and future directions that remain to be explored.
Rémi Watrigant, University Lyon1 and ENS, France
Title talk: Graph decompositions: recent techniques and applications
Short abstract: In this talk, we will first recall some classical graph decomposition techniques, before introducing the notion of contraction sequences. This concept lies at the heart of twin-width, but it also provides a unifying perspective that can recover several other graph parameters. We will then present applications to both exact and approximation algorithms.