La biologie exerce une fascination sur les mathématiciens et les informaticiens. Au delà du cliché maintes fois répété des ordinateurs devenus indispensables pour analyser l'énorme masse de données qui est produite par les techniques à haut débit, c'est, avant tout, le haut degré de combinatoire inhérent à la plupart des processus biologiques qui captive l'imagination. La combinatoire de la vie est étonnante, et sa complexité va bien au delà de ce que l'imagination humaine pourrait ou aimerait considérer.

D'un côté, une puissance de calcul constamment croissante est en effet nécessaire et peut être atteinte grâce à des logiciels et des ordinateurs toujours plus efficaces. D'un autre côté, le besoin de représentations simplifiées, c'est-à-dire intelligibles, des systèmes biologiques demeure crucial. La voie adoptée par BAMBOO vise à gérer l'énorme quantité de données déjà disponible en s'appuyant sur des modèles simplifiés mais de plus en plus détaillés, pour parvenir à une compréhension fine des systèmes biologiques à différentes échelles, du génotype au phénotype, et inversement.

L'étude de l'évolution constitue un but en soi mais également un moyen de définir des modèles biologiques précis mais génériques visant entre autres à élucider la fonction biologique. L'évolution est entendue ici dans un sens très général, à savoir, classiquement comme les changements que la mutation et la sélection opèrent sur les textes moléculaires, et comme les changements dans la façon dont ces textes sont lus et interprétés par la machinerie cellulaire. De plus, seront prises en compte les variations génétiques mais également épigénétiques (héritables mais non codées dans la séquence d'ADN) ainsi qu'environnementales qui ont pu survenir dans l'histoire de la vie.

Les aspects formels de cette entreprise comprennent deux étapes : l'une de modélisation et l'autre de (re)visite et exploration de problèmes, classiques ou nouveaux, combinatoires, probabilistes et algorithmiques, sur les séquences et sur les graphes, soulevés par les objectifs biologiques de l'équipe. Ces aspects formels sont en dialogue permanent avec la partie expérimentale conduite au sein de l'équipe, ou en collaboration avec des biologistes externes.

Les objectifs de BAMBOO conduisent à une grande variété de problèmes mathématiques et computationnels, certains classiques mais pouvant apparaître sous un éclairage différent, d'autres complètement nouveaux. Ces problèmes concernent :

• l'algorithmique sur des textes : détection efficace de différents types de répétitions exactes ou diversement structurées; assemblage de fragments; construction et analyse d'indexes; comparaison et alignement sous diverses formes.
• l'algorithmique sur des arbres : comparaison et alignement sous différents types de modèles et de contraintes; détection de motifs d'arbres (isomorphisme de sous-arbre ou variantes); exploration d'indexes pour les arbres.
• l'algorithmique sur les (hyper)graphes : comme pour les arbres, comparaison et alignment sous différents types de modèles et de contraintes; détection de motifs de graphes (isomorphisme de sous-graphe, simples sous-graphes, sous-graphes communs connexes, etc.) et analyse d'indexes pour les graphes; différents types de calculs de flots dans les réseaux.

Tout cela implique également, bien entendu, des questions de complexité algorithmique.

Enfin, parce que tous ces aspects formels sont, avant tout, motivés par des problèmes biologiques, tout ceci requiert de plus :

• une première étape de construction de modèle qui nécessite une connaissance approfondie de la littérature biologique et un dialogue intense avec les biologistes ;
• le développement de méthodes statistiques et l'exploration de modèles aléatoires nouveaux et appropriés aux objets mis en lumière par les algorithmes ;
• un retour permanent à la biologie, à travers les discussions et/ou les expériences.

• Instituto de Matemática e Estatística, Universidade de São Paulo, São Paulo, Brésil
• Departamento de Computação e Estatística, Universidade Federal de Mato Grosso do Sul, Campo Grande, Brésil
• Laboratório Nacional de Computação Científica, Ministério da Ciência e da Teconologia, Petrópolis, Rio de Janeiro, Brésil
• Dipartimento di Informatica e Sistemistica, Università di Roma "La Sapienza", Rome, Italie
• Dipartimento di Informatica, Università di Pisa, Pise, Italie
• Vrije Universiteit Amsterdam, Amsterdam, Hollande
• Centrum Wiskunde & Informatica, Amsterdam, Hollande
• Knowledge Discovery and Bioinformatics Group, INESC-ID, Instituto Superior Técnico, Lisbonne, Portugal
• Algorithm Design Group, Department of Computer Science, King's College, Londres, UK