L'essor des bases de données contenant des descriptions d'objets biologiques arborescents (structures secondaires d'ARNs, architecture de plantes, etc.) crée un important besoin de nouveaux outils de traitement automatique et d'analyse.
Des avancées récentes dans différents champs des mathématiques appliquées et de l'informatique permettent de refonder les méthodes usuelles de la biologie en intégrant à la fois les dynamiques de développement et la structure. Notre but est ainsi d'analyser les structures et leurs développements à différentes échelles afin de répondre à deux types d'objectifs:
- Des objectifs de nature cognitive afin d'identifier les régularités et gradients à l'intérieur de structure biologique et d'en déduire des interprétations en termes de fonctionnement, c'est le cas par exemple pour les structures secondaires d'ARNs,
- Des objectifs plus finalisés consistant à intégrer de manière opérationnelle la structure dans une démarche biologique (par exemple pour la sélection de nouvelles variétés agronomiques dans le cas de l'analyse de l'architecture de plantes).
Dans ce contexte, le développement de méthodes d'investigation de l'architecture des plantes ou de structures génomiques revêt une importance majeure. Par exemple, en modélisation des plantes, la comparaison structurelle d'individus permet d'aborder sous un angle nouveau le problème de l'évaluation des modèles de simulation de la croissance des plantes (Ferraro, 2000).
La famille d'algorithmes que nous étudions principalement consiste à reconstruire un graphe cible en appliquant à un graphe initial différentes opérations structurelles élémentaires, appelées opérations d'édition. On peut montrer que la définition d'une telle distance se ramène à la recherche d'une solution optimale dans un espace dont la taille croît exponentiellement avec la taille des objets à comparer. Ainsi, pour définir des algorithmes efficaces à la fois en temps et en espace, la solution optimale est construite de façon incrémentale en utilisant des techniques de programmation dynamique. Durant les 20 dernières années, plusieurs équipes de mathématiciens et d'informaticiens se sont attaquées à différents aspects du problème posé par l'édition des arborescences biologiques (Zhang 1996, Wang 1999, Ferraro 2003, Ouangraoua 2007). Ces premières explorations ont ouvert un nombre important de voies de recherches algorithmiques et applicatives.
L'objectif des recherches en cours est d'intégrer, à partir de ces études initiales, les travaux dédiés à l'édition d'arborescence, afin de proposer un point de vue unifié des différentes techniques et de développer leurs applications. D'un point de vue applicatif, les biologistes, alors qu'ils utilisent fréquemment des logiciels comme Blast ou Fasta pour l'analyse de structures plus simples comme les séquences d'ADN, ne disposent à l'heure actuelle d'aucun outil logiciel d'analyse des arborescences. Dans ce cadre, notre travail a pour but de développer des outils conceptuels et algorithmiques pour la comparaison d'objets biologiques arborescents basés sur les méthodes d'édition.
En parallèle, nous avons mis en place une thématique émergeante transdisciplianire qui s'interresse à l'adaptation des méthodes présentées ci-dessus à l'analyse de la musique.