H2020 Twinning Project OLISSIPO

Coordinator: Coordinator: Susana Vinga, INESC-ID, Instituto Superior Técnico, Lisbon, Portugal; Coordinator in ERABLE Team at Inria: Marie-France Sagot.
Duration: 2021-2023

Brief description
OLISSIPO is a H2020 Twinning project coordinated by INESC-ID. The project focuses on Computational Biology, a strongly interdisciplinary area that combines Computer Science, Algorithms, Mathematics, Probability and Statistics, Machine Learning, Molecular Biology and Medicine. The project consortium is composed of INESC-ID (Coordinator), the National Institute for Research in Digital Science and Technology (Inria) through the Erable team, the Swiss Federal Institute of Technology (ETH Zurich) and the European Molecular Biology Laboratory (EMBL). The main goal of the project is to intensify, increase and consolidate the research in Computational Biology carried out at INESC-ID in partnership with the European partner institutions.

H2020 ITN Project ALPACA

Coordinator: Coordinator: Alexander Schönhuth, University of Bielefeld, Germany.
Duration: 2020-2023

Brief description
ALPACA (“Algorithms for PAngenome Computational Analysis”) is an EU Marie Skłodowska-Curie Innovative Training Networks (ITN) consortium grant that will train 14 PhD researchers, including one at CWI who will be co-supervised by Solon Pissis and Leen Stougie, together also with Marie-France Sagot, and one at the University of Pisa supervised by Nadia Pisanti.

Genomes are strings over the letters A, C, G, T, which represent nucleotides, the building blocks of DNA. In view of ultra-large amounts of genome sequence data emerging from ever more and technologically rapidly advancing genome sequencing devices—in the meantime, amounts of sequencing data accrued are reaching into the exabyte scale—the driving, urgent question is: how can we arrange and analyse these data masses in a formally rigorous, computationally efficient and biomedically rewarding manner? Graph based data structures have been pointed out to have disruptive benefits over traditional sequence-based structures when representing pan-genomes, sufficiently large, evolutionarily coherent collections of genomes. This project will put this shift of paradigms—from sequence to graph based representations of genomes—into full effect.

The project consortium consists of 23 academic and industrial partners, including CWI, the University of Bielefeld (Germany), the CNRS (France), the INRIA (France), the University of Pisa (Italy), the University of Milan-Bicocca (Italy), the Heinrich Heine University in Düsseldorf (Germany), the European Molecular Biology Laboratory (EMBl-EBI), the Comenius University in Bratislava (Slovakia), the University of Helsinki (Finland), the Pasteur Institute (France), and the University of Cambridge (UK).

NWO Grant on Optimisation for and with Machine Learning

Coordinator: Coordinator: D. den Hertog, Tilburg University; Participant in ERABLE Team at CWI: Leen Stougie.
Duration: 2020-2025

Brief description
Machine learning is often in the news because of remarkable applications such as image recognition and self-driving cars. When constructing machine learning models, such as deep learning and random forests, mathematical optimisation plays an important role. In the first project part we want to better understand the performance of existing optimisation techniques for machine learning and also develop faster and better optimisation techniques. In the second part we use machine learning techniques to solve optimisation problems faster and more accurately. The new techniques are applied to classification problems for medical treatments, finding genetic relationships, food distribution chains for the World Food Programme, and self-driving cars.

This programme is coordinated by Tilburg University, with participants at TUD, Tilburg University and CWI. In close collaboration with TUD, Leen Stougie from CWI and Erable together with Leo J.J. van Iersel from TUD will work on improving models and optimisation methods for life sciences inspired problems, such as classification of virulent yeast strains and problems in phylogeny. At CWI also, Nikhil Bansal and Monique Laurent from the Networks and Optimization group at CWI will study combinatorial and polynomial optimisation based methods for machine learning, develop theoretical analysis for heuristics used in machine learning, and use machine learning to design optimization algorithms that exploit structure in data. More information about this grant may be found here.

Inria Associated Team CAPOEIRA

Coordinators: Coordinators: Marie-France Sagot (Erable); André Fujita (Universidade de São Paulo (USP), São Paulo, Brazil).
Duration: 2020-2023

Brief description
The project covers theoretical computer science (essentially graph theory), mathematics (combinatorics, statistics, and probability), and the development of algorithms to address various biological questions, in particular, the intra and cross-species interactions, which have implications in all aspects of life sciences, including health, ecology, and environment.

Two main general topics will be addressed, namely evolution/co-evolution, and biological network (graph/hypergraph) analysis and comparison. The first topic concerns better understanding and characterising the moment of speciation leading to new species on one hand, and on the other, how one set of species may influence the evolution of another. The second topic concerns metabolism on one hand, and (post-)transcriptional regulation on the other, with the post-transcriptional level involving also inference “from scratch” of the main actors, namely the non-coding RNAs and their targets, and the regulatory network they form. In the first two cases (of metabolism and transcriptional regulation), we will assume that the networks are already inferred albeit with possibly numerous missing and incorrect data. Finally, in the case of regulation, we will also consider the problem of inferring variants, notably related to alternative splicing, from a set of RNA-seq data using a de Bruijn graph approach. Overseeing these two main topics are the issues of knowledge representation and model revision that will also be addressed. These are crucial in the life sciences, and notably in the context of post-transcriptional regulation by non-coding RNAs, for which the different actors, features, and overall mechanisms are constantly being questioned and revised.

Capes-Cofecub Project AHIMSA

Coordinators: Coordinators: Marie-France Sagot (Erable); Andréa Ávila (Instituto de Biologia Molecular do Paraná – Fiocruz-PR, Curitiba, Paraná, Brazil).
Duration: 2020-2022

Brief description
One of the objectives of this project, the one with highest risk of not succeeding, is to explore Ahimsa-like approaches to sickness and health. However, our main objective is to first understand how these organisms respond to drug treatments or reshape the host cells after infection. We further aim to focus on a community-vision approach to living organisms which will try to gather information from multiple partners of the biological systems we are studying. This presents further risks that are both methodological and experimental. Modelling communities up to the molecular level is indeed hard because of a lack of enough or of adequate data. Modelling and then experimentally manipulating such communities is tricky also because of the complexity of having to handle many different processes taking place at very different levels and time scales.

ANR project U4ATAC-Brain

Coordinators: Coordinators: (General) Patrick Edery & Sylvie Mazoyer (CRNL Lyon, INSERM-CNRS-UCBL), (in Lyon) Vincent Lacroix BAOBAB-ERABLE Teams LBBE-UCBL-INRIA, (in Montpellier) Remi Bordonné IGMM CNRS, (in Paris) Anne-Louise Leutenegger U946 INSERM.
Duration: 2018-2021

Brief description
The aim of this proposal is to unravel the role played by minor splicing in embryonic development, with a focus on brain development. We will achieve this task through the study of rare malformation syndromes with abnormal brain development caused by a defect of U4atac snRNA, a component of the minor spliceosome. We will take advantage of our collective first-rate expertises on human syndromes, genomics, transcriptomics, bioinformatics, biochemistry and zebrafish model to perform a multidisciplinary research study aiming at understanding the physiopathology of brain malformations caused by RNU4ATAC-associated minor splicing defects. The present project will also help to improve the genetic counselling of the families concerned by a RNU4ATAC mutation or related disorders.

Inria Associated Team COMPASSO

Coordinators: Marie-France Sagot (Erable); Susana Vinga (Instituto Superior Técnico (IST), Lisbon, Portugal).
Duration: 2018-2020

Brief description
Microbial communities are ubiquitous in nature and have major impact on every aspect of life in our planet. In spite of its importance, little is known about the principles that determine the functioning, robustness, evolution and control of such communities. The two teams that are partners of this project have some history of collaborating together. So far however, their main direct scientific concerns have been distinct in terms of final goals, while the areas of expertise are concentrated on computer science but with also some distinct characteristics. The main aim of this project is to work together towards establishing a strong link between the different application goals each team has had so far. This is an ambitious project, that will highly depend on further blending together the different expertises that each team has.

The French team has since some ten years now been highly interested in modelling and exploring species interactions. Such interactions indeed appear crucial to understand some if not all of the most fundamental evolutionary and functional questions related to living organisms. They remain however very little explored by computational biologists.

The Portuguese team on the other hand has been involved since a few years in a number of projects related mainly to cancer and rare diseases. The objective has been to develop the statistical and machine learning algorithms that would allow, using multi-omic data, to help propose personalised treatments to these diseases.

The ultimate aim of this project is to start building links between these two aspects, of species interactions and cancer/rare diseases, or more precisely, between infectious diseases and non infectious ones, whether they involve human or animals more in general. The main general questions that will be addressed are the following: (i) Are species interactions really a crucial factor on the development of at least some non infectious diseases as is suspected? (ii) If yes, could this disease be treated in a “non-aggressive” way by exploiting such species interactions? These are highly ambitious questions that will in the first three years be tackled through two angles. One concerns modelling and understanding the system biology of communities, and the second modelling and understanding the co-evolutionary aspects present in such communities. first will in fact cover both synthetic communities and natural ones.

ANR Technology SPOCK

Coordinator: Lilia (Brinza) Boucinha, MaatPharma; PhD supervisors from academia: Marie-France Sagot (Erable); Susana Vinga (Instituto Superior Técnico (IST), Lisbon, Portugal).
Duration: 2018-2021

Brief description
The PhD project SPOCK (Cifre scholarship) funded by the ANR Technology will consist in the development of a unified and standardised framework for quantitative metagenomics in a clinical/industrial context with as a main purpose identifying the key microorganismal players in the host-microbiome dialog and human health maintenance. The beneficiary of the PhD scholarship is Marianne Borderes.

ANR project GREEN

Coordinators: (General) Abdelaziz Heddi (Insa-Lyon), (in LBBE) Cristina Vieira; Participant in BAOBAB-ERABLE Teams LBBE-UCBL-INRIA: Marie-France Sagot.
Duration: 2018-2021

Brief description
Most insect pests thriving on nutritionally poor habitats have evolved obligate mutualistic relationships with heritable intracellular bacteria (endosymbionts) that supplement their diet with limiting nutrients and thereby improve their adaptive and invasive powers. The endosymbiont distribution is restricted to female germ cells and to the bacteriocytes, i.e. the specialised cells that seclude the bacteria and prevent their exposure to the host immune system. Remarkably, neither the host nor the endosymbiont can survive independently out of these integrated associations. Investigating the mechanisms by which insects maintain endosymbionts and control their number will participate to the identification of new specific targets of host-symbiont interaction and host homeostasis and fitness. By investigating the endosymbiotic association between the cereal weevil Sitophilus oryzae and the Gram-negative bacterium Sodalis pierantonius, we showed that bacteriocytes display a modulated expression of immune genes, notably marked by a down-regulation of most immune effectors, and that S. pierantonius undergoes a highly contrasted dynamics along the host life cycle. The endosymbionts load is controlled and adjusted to the host physiological and developmental needs through specific immune gene expression, cell apoptosis, and autophagy. The present project aims at unraveling the major host gene involved in the symbiosis homeostasis and endosymbiont dynamics, and at deciphering their mechanisms of regulation and function. We will decipher the molecular bases of the host-symbiont interactions at critical phases of the host development by using the dual-RNA-seq technology, which allows to simultaneously screen the transcriptomes of host and endosymbiont and to pinpoint their coordinated and contrasted gene expression. To go further into how the bacteriocyte immune response has evolved to express a limited set of immune effectors, and what are the regulatory elements behind this immunomodulation, we will identify cis-regulatory elements, non-coding RNAs, and candidate transcription factors acting as master regulators. Finally, we will analyze the function of selected candidate genes related to the bacteriocyte homeostasis or symbiosis dynamics during the host life cycle by combining complementary functional genomics tools, including in situ transcript and protein localisation, RNA interference transcript inhibition, and structure-activity analysis of candidate proteins.

By combining in silico and wet lab tools, we expect to provide a clear picture on the gene players and how they are regulated in both endosymbiosis homeostasis and along endosymbiont dynamics. We have the ambition to provide the foundation for identifying specific molecules disrupting the endosymbiotic relationship, as a novel control strategy for weevils and other major insect pests.

ANR project ASTER

Coordinators: (General) Hélène Touzet, Bonsai team, CRIStAL-INRIA, (in Lille) David Hot, Institut Pasteur de Lille, (in Lyon) Vincent Lacroix BAOBAB-ERABLE Teams LBBE-UCBL-INRIA, (in Paris) Jean-Marc Aury, CEA.
Duration: 2016-2020

Brief description
The ANR project ASTER proposes to develop algorithms and software for analysing third generation sequencing data. Third generation is an emerging technology for RNA and DNA sequencing that promises to give a better picture for studying transcriptomes, metagenomes and metatranscriptomes of all living organisms. It will be key for discovering new fundamental mechanisms in cell biology, with broad implications in environmental research, health and agriculture. However, analysing the data is computationally challenging due to a very high rate of sequencing errors. There is a pressing need for models and algorithms that can accommodate this new kind of data and that are also scalable.

ANR project GraphEn

Coordinators: (General) Dieter Kratsch, LITA, University of Lorraine, France, (in Clermont-Ferrand) Mamadou Moustapha Kanté, LIMOS, University of Clermont-Ferrand, France, (in Bordeaux) Paul Dorbec, LABRI, University of Bordeaux, France; Participant in BAOBAB-ERABLE Teams LBBE-UCBL-INRIA: Arnaud Mary.
Duration: 2016-2020

Brief description
The P vs. NP question is arguably the most important open question in Theoretical Computer Science these days. Under the widely believed assumption that the complexity classes P and NP are not equal, there are problems that cannot be solved efficiently with the help of computers. Thus it is important to identify such problems and to find other ways of dealing with them, different from the traditional means of polynomial-time algorithms. Unfortunately, many problems of great theoretical importance and also many problems that arise from real applications turn out to be intractable in the general case.

While optimisation is ubiquitous in Computer Science and a lot of research has been done on algorithms and complexity on optimisation problems, surprisingly little attention has been given to enumeration. A solution of the enumeration version of a problem typically provides an immediate solution for the optimisation version of the problem. This seems to suggest that enumeration is “much harder” than optimisation, which, among others, directed the search for tractability and efficient algorithms to optimisation problems. New insights from the recent research on the exact complexity of hard problems indicate that the relation between enumeration and optimisation is more subtle and worth a fundamental study from theoretical point of view.

Listing, generating or enumerating objects of specified type and properties has important applications in various domains of Computer Science as e.g. data mining, machine learning and artificial intelligence, as well as in other sciences, in particular in biology, and also many applications in real life. This is one of the motivations of our interest in enumeration. The scientific goals of the project are of theoretical nature and oriented towards better understanding of the complexity of enumeration and the study of algorithmic techniques to solve enumeration problems. This project will concentrate focus on problems for graphs and hypergraphs and study three different approaches to the algorithmics of enumeration.

Older projects

Information on older projects of the team may be found here. Notice that this page remains uncomplete.

Permanent link to this article: