BAMBOO Research team

An algorithmic view on genomes, cells, and environments

Team presentation

Biology has held a deep fascination to people with a mathematical mind. Beyond the much expressed cliché that computers are essential to analyse the huge masses of data being produced by sequencing and other high-throughput experiments, it is the high level combinatorics underlying most of life processes that has cast a spell on the imagination of mathematicians and computer scientists alike. The combinatorics of life is unexpectedly diverse and its complexity goes much beyond what any human imagination could or would wish to consider.

On one hand, increasing computing power is indeed required and may be attained by the production of more efficient software or hardware. On another hand, the need to get at simplified representations of biological systems remains. The route adopted by BAMBOO attempts to deal with the huge amount of data and with the broadness of picture this offers, while at the same time trying to arrive at simplified but increasingly more detailed models, and thereby at a better and finer understanding of biological systems at any scale, from genotype to phenotype, and back.

Evolution represents both the main investigative means to arrive at such simultaneously precise and broad models and a major purpose of the undertaking, together with getting at biological function. Evolution will be understood in a very general sense, that is, classically as the changes selection imprints on the molecular texts, and, something which is less usually considered, as the changes on the way such texts are read by the cellular machinery. Moreover, we shall attempt to take into account not just the genetic but also the epigenetic (heritable but not encoded in the DNA sequence) as well as environmental variations that have taken place in the history of life.

The formal aspects of this endeavour comprise two main steps: modelling, and a (re)visit and exploration of the classical or completely new combinatorial, probabilistic and algorithmic problems on strings and (hyper)graphs that are raised by the biological goals of the team. Such formal aspects will be in constant dialog with an experimental part conducted within the team, or in collaboration with geographically close and more distant biologists.

Research themes

The objectives of BAMBOO give rise to a wide variety of mathematical and computational problems, some classic that may reappear in new coats and others completely new. Those involve:

  • text algorithmics: efficient detection of different types of exact and approximate, simple or variously structured repeats; fragment assembly; index building and analysis; text comparison and alignment under many forms.
  • tree algorithmics: tree comparison and alignment with different types of models and constraints; tree motif detection (subtree isomorphism or variants thereof); tree index exploration.
  • (hyper)graph algorithmics: as for trees, comparison and alignment with different types of models and constraints; graph motif detection (subgraph isomorphism, simple subgraphs, common connected subgraphs, etc.) and graph index analysis; various sorts of network flow computations.

All involve also complexity issues. Because all such formal aspects are strongly motivated by biological questions, any require further:

  • an initial model building step that involve a deep knowledge of the biological literature and an intensive dialog with biologists;
  • the development of sophisticated statistical methods and exploration of new and more appropriate random models for assessing the significance of what is discovered by the algorithms;
  • a permanent return to biology, via discussions and/or experiments.

International and industrial relations

Keywords: Algorithmics Mathematics Combinatorics Molecular and Cellular Biology Environment

Research teams of the same theme :

Inria Headquarters and research centres

Direct links

Social