Project acronym Active-DNA
Project Computationally Active DNA Nanostructures
Researcher (PI) Damien WOODS
Host Institution (HI) NATIONAL UNIVERSITY OF IRELAND MAYNOOTH
Call Details Consolidator Grant (CoG), PE6, ERC-2017-COG
Summary During the 20th century computer technology evolved from bulky, slow, special purpose mechanical engines to the now ubiquitous silicon chips and software that are one of the pinnacles of human ingenuity. The goal of the field of molecular programming is to take the next leap and build a new generation of matter-based computers using DNA, RNA and proteins. This will be accomplished by computer scientists, physicists and chemists designing molecules to execute ``wet'' nanoscale programs in test tubes. The workflow includes proposing theoretical models, mathematically proving their computational properties, physical modelling and implementation in the wet-lab.
The past decade has seen remarkable progress at building static 2D and 3D DNA nanostructures. However, unlike biological macromolecules and complexes that are built via specified self-assembly pathways, that execute robotic-like movements, and that undergo evolution, the activity of human-engineered nanostructures is severely limited. We will need sophisticated algorithmic ideas to build structures that rival active living systems. Active-DNA, aims to address this challenge by achieving a number of objectives on computation, DNA-based self-assembly and molecular robotics. Active-DNA research work will range from defining models and proving theorems that characterise the computational and expressive capabilities of such active programmable materials to experimental work implementing active DNA nanostructures in the wet-lab.
Summary
During the 20th century computer technology evolved from bulky, slow, special purpose mechanical engines to the now ubiquitous silicon chips and software that are one of the pinnacles of human ingenuity. The goal of the field of molecular programming is to take the next leap and build a new generation of matter-based computers using DNA, RNA and proteins. This will be accomplished by computer scientists, physicists and chemists designing molecules to execute ``wet'' nanoscale programs in test tubes. The workflow includes proposing theoretical models, mathematically proving their computational properties, physical modelling and implementation in the wet-lab.
The past decade has seen remarkable progress at building static 2D and 3D DNA nanostructures. However, unlike biological macromolecules and complexes that are built via specified self-assembly pathways, that execute robotic-like movements, and that undergo evolution, the activity of human-engineered nanostructures is severely limited. We will need sophisticated algorithmic ideas to build structures that rival active living systems. Active-DNA, aims to address this challenge by achieving a number of objectives on computation, DNA-based self-assembly and molecular robotics. Active-DNA research work will range from defining models and proving theorems that characterise the computational and expressive capabilities of such active programmable materials to experimental work implementing active DNA nanostructures in the wet-lab.
Max ERC Funding
2 349 603 €
Duration
Start date: 2018-11-01, End date: 2023-10-31
Project acronym PARAMTIGHT
Project Parameterized complexity and the search for tight complexity results
Researcher (PI) Dániel Marx
Host Institution (HI) MAGYAR TUDOMANYOS AKADEMIA SZAMITASTECHNIKAI ES AUTOMATIZALASI KUTATOINTEZET
Call Details Starting Grant (StG), PE6, ERC-2011-StG_20101014
Summary The joint goal of theoretical research in algorithms and
computational complexity is to discover all the relevant algorithmic techniques
in a problem domain and prove the optimality of these techniques.
We propose that the search for such tight results should be done
by a combined exploration of the dimensions running time, quality
of solution, and generality. Furthermore, the theory of parameterized complexity
provides a framework for this exploration.
Parameterized complexity is a theory whose goal is to
produce efficient algorithms for hard combinatorial problems using
a multi-dimensional analysis of the running time. Instead of
expressing the running time as a function of the input size only
(as it is done in classical complexity theory), parameterized
complexity tries to find algorithms whose running time is
polynomial in the input size, but exponential in one or more
well-defined parameters of the input instance.
The first objective of the project is to go beyond the
state of the art in the complexity and algorithmic aspects of
parameterized complexity in order to turn it into a theory
producing tight optimality results. With such theory at hand, we
can start the exploration of other dimensions and obtain tight
optimality results in a larger context. Our is goal is being able
to prove in a wide range of settings that we understand all the
algorithmic ideas and their optimality.
Summary
The joint goal of theoretical research in algorithms and
computational complexity is to discover all the relevant algorithmic techniques
in a problem domain and prove the optimality of these techniques.
We propose that the search for such tight results should be done
by a combined exploration of the dimensions running time, quality
of solution, and generality. Furthermore, the theory of parameterized complexity
provides a framework for this exploration.
Parameterized complexity is a theory whose goal is to
produce efficient algorithms for hard combinatorial problems using
a multi-dimensional analysis of the running time. Instead of
expressing the running time as a function of the input size only
(as it is done in classical complexity theory), parameterized
complexity tries to find algorithms whose running time is
polynomial in the input size, but exponential in one or more
well-defined parameters of the input instance.
The first objective of the project is to go beyond the
state of the art in the complexity and algorithmic aspects of
parameterized complexity in order to turn it into a theory
producing tight optimality results. With such theory at hand, we
can start the exploration of other dimensions and obtain tight
optimality results in a larger context. Our is goal is being able
to prove in a wide range of settings that we understand all the
algorithmic ideas and their optimality.
Max ERC Funding
1 150 000 €
Duration
Start date: 2012-01-01, End date: 2017-06-30
Project acronym SYSTEMATICGRAPH
Project Systematic mapping of the complexity landscape of hard algorithmic graph problems
Researcher (PI) Dániel MARX
Host Institution (HI) MAGYAR TUDOMANYOS AKADEMIA SZAMITASTECHNIKAI ES AUTOMATIZALASI KUTATOINTEZET
Call Details Consolidator Grant (CoG), PE6, ERC-2016-COG
Summary Graph-theoretical models are natural tools for the description of road networks, circuits, communication networks, and abstract relations between objects, hence algorithmic graph problems appear in a wide range of computer science applications. As most of these problems are computationally hard in their full generality, research in graph algorithms, approximability, and parameterized complexity usually aims at identifying restricted variants and special cases, which are at the same time sufficiently general to be of practical relevance and sufficiently restricted to admit efficient algorithmic solutions. The goal of the project is to put the search for tractable algorithmic graph problems into a systematic and methodological framework: instead of focusing on specific sporadic problems, we intend to obtain a unified algorithmic understanding by mapping the entire complexity landscape of a particular problem domain.
Completely classifying the complexity of each and every algorithmic problem appearing in a given formal framework would necessarily reveal every possible algorithmic insight relevant to the formal setting, with the potential of discovering novel algorithmic techniques of practical interest. This approach has been enormously successful in the complexity classifications of Constraint Satisfaction Problems (CSPs), but comparatively very little work has been done in the context of graphs. The systematic investigation of hard algorithmic graph problems deserves the same level of attention as the dichotomy program of CSPs, and graph problems have similarly rich complexity landscapes and unification results waiting to be discovered. The project will demonstrate that such a complete classification is feasible for a wide range of graph problems coming from areas such as finding patterns, routing, and survivable network design, and novel algorithmic results and new levels of algorithmic understanding can be achieved even for classic and well-studied problems.
Summary
Graph-theoretical models are natural tools for the description of road networks, circuits, communication networks, and abstract relations between objects, hence algorithmic graph problems appear in a wide range of computer science applications. As most of these problems are computationally hard in their full generality, research in graph algorithms, approximability, and parameterized complexity usually aims at identifying restricted variants and special cases, which are at the same time sufficiently general to be of practical relevance and sufficiently restricted to admit efficient algorithmic solutions. The goal of the project is to put the search for tractable algorithmic graph problems into a systematic and methodological framework: instead of focusing on specific sporadic problems, we intend to obtain a unified algorithmic understanding by mapping the entire complexity landscape of a particular problem domain.
Completely classifying the complexity of each and every algorithmic problem appearing in a given formal framework would necessarily reveal every possible algorithmic insight relevant to the formal setting, with the potential of discovering novel algorithmic techniques of practical interest. This approach has been enormously successful in the complexity classifications of Constraint Satisfaction Problems (CSPs), but comparatively very little work has been done in the context of graphs. The systematic investigation of hard algorithmic graph problems deserves the same level of attention as the dichotomy program of CSPs, and graph problems have similarly rich complexity landscapes and unification results waiting to be discovered. The project will demonstrate that such a complete classification is feasible for a wide range of graph problems coming from areas such as finding patterns, routing, and survivable network design, and novel algorithmic results and new levels of algorithmic understanding can be achieved even for classic and well-studied problems.
Max ERC Funding
1 532 000 €
Duration
Start date: 2017-07-01, End date: 2022-06-30
Project acronym Tamed Cancer
Project Personalized Cancer Therapy by Model-based Optimal Robust Control Algorithm
Researcher (PI) Levente Adalbert Kovács
Host Institution (HI) OBUDAI EGYETEM
Call Details Starting Grant (StG), PE6, ERC-2015-STG
Summary Imagine if tumor growth would be reduced and then kept in a minimal and safe volume in an automated manner and in a personalized way, i.e. cancer drug would be injected using a continuous therapy improving the patient’s quality of life.
By control engineering approaches it is possible to create model-based strategies for health problems. Artificial pancreas is an adequate example for this, where by continuous glucose measurement device and insulin pump it is possible to improve diabetes treatment. Gaining expertise from this problem, the current proposal focuses on taming the cancer by developing an engineering-based medical therapy.
The interdisciplinary approach focuses on modern robust control algorithm development in order to stop the angiogenesis process (i.e. vascular system development) of the tumor; hence, to stop tumor growth, maintaining it in a minimal, “tamed” form. This breakthrough concept could revitalize cancer treatment. It is the right time to do it as some investigations regarding tumor growth modeling have been already done; now, it should be refined by model identification tools and validated on animal trials. The benefit of robust control was already demonstrated in artificial pancreas; hence, it could be adapted to cancer research. The result could end with a personalized healthcare approach for drug-delivery in cancer, improving quality of life, optimizing drug infusion and minimizing treatment costs. This interdisciplinary approach combines control engineering with mathematics, computer science and medical sciences.
As a result, the model-based robust control approach envisage refining the currently existing tumor growth modeling aspects, design an optimal control algorithm and extend it by robust control theory to guarantee its general applicability. Based on our research background, validation will be done first in a manually controlled way, but then in an automatic mode to propose it for further human investigations.
Summary
Imagine if tumor growth would be reduced and then kept in a minimal and safe volume in an automated manner and in a personalized way, i.e. cancer drug would be injected using a continuous therapy improving the patient’s quality of life.
By control engineering approaches it is possible to create model-based strategies for health problems. Artificial pancreas is an adequate example for this, where by continuous glucose measurement device and insulin pump it is possible to improve diabetes treatment. Gaining expertise from this problem, the current proposal focuses on taming the cancer by developing an engineering-based medical therapy.
The interdisciplinary approach focuses on modern robust control algorithm development in order to stop the angiogenesis process (i.e. vascular system development) of the tumor; hence, to stop tumor growth, maintaining it in a minimal, “tamed” form. This breakthrough concept could revitalize cancer treatment. It is the right time to do it as some investigations regarding tumor growth modeling have been already done; now, it should be refined by model identification tools and validated on animal trials. The benefit of robust control was already demonstrated in artificial pancreas; hence, it could be adapted to cancer research. The result could end with a personalized healthcare approach for drug-delivery in cancer, improving quality of life, optimizing drug infusion and minimizing treatment costs. This interdisciplinary approach combines control engineering with mathematics, computer science and medical sciences.
As a result, the model-based robust control approach envisage refining the currently existing tumor growth modeling aspects, design an optimal control algorithm and extend it by robust control theory to guarantee its general applicability. Based on our research background, validation will be done first in a manually controlled way, but then in an automatic mode to propose it for further human investigations.
Max ERC Funding
1 015 900 €
Duration
Start date: 2016-07-01, End date: 2021-06-30
