Algorithmes et calculs - Description

Contexte et motivations

Les données environnementales (e.g. les images satellitaires) et liées au vivant (e.g. les génomes de très nombreuses espèces) se développent de manière spectaculaire, sur un rythme bien souvent exponentiel, plus rapide que la loi de Moore caractérisant la puissance de calcul des ordinateurs. Dans le même temps, les connaissances et les modèles sur ces données sont sans cesse plus complexes et précis, et on attend toujours plus de leur exploitation, pour résoudre non seulement les grandes questions scientifiques (origine de la vie, dynamique des écosystèmes…), mais aussi répondre à des enjeux sociétaux essentiels (e.g. santé, médicaments, impacts du changement climatique, conséquences de la démographie…). Il y a là un défi majeur pour les méthodes informatiques et algorithmiques, puisqu’il faut essentiellement être à même de faire des calculs plus complexes sur plus de données et en moins de temps, avec des ordinateurs dont la puissance n’augmente pas aussi vite que la taille des données. On attend aussi que ces méthodes et les résultats produits soient valides et certifiés, avec des garanties prouvées d’optimalité et de précision, numérique notamment.
La communauté internationale est largement mobilisée autour de ces questions, mais pour l’instant les données semblent être produites plus rapidement que n’avance notre capacité à les analyser. Le projet 1000 génomes humains est à ce titre exemplaire (http://www.1000genomes.org/). Lancé il y a bientôt 3 ans, le projet a largement dépassé ses objectifs avec près de 2,500 génomes séquencés appartenant à une trentaine de populations à la surface du globe. Mais l’information extraite de ces données est encore faible (un seul article publié, en Octobre 2010), alors qu’à l’évidence elles contiennent une masse considérable d’informations sur l’homme, son histoire et sa biologie. Des exemples analogues peuvent être trouvés dans d’autres domaines, par exemple celui des images satellitaires environnementales. La raison en incombe au manque de méthodes informatiques et mathématiques pour traiter ces données, et sur le difficile passage à l’échelle.
Dans ce contexte, la contribution de NUMEV devrait permettre des avancées significatives, tant théoriques qu’appliquées. L’axe « Algorithmes et calculs » regroupe des équipes issues de l’informatique, des mathématiques, de la microélectronique et de la physique, avec un large spectre de compétences complémentaires, allant de la théorie algorithmique de la complexité, au traitement effectif des données de la biologie à grande échelle, en passant par les méthodes pratiques de résolution des problèmes NP-complet, les approches probabilistes de type Monte Carlo, la simulation des systèmes complexes, la conception de machines dédiées, le parallélisme massif et le calcul haute performance.

Figure 10 : Arbre phylogénétique représentant l’histoire évolutive des primates, reconstruit par l’algorithme PhyML à partir de séquences d’ADN en suivant le principe du maximum de vraisemblance.

Ces équipes sont internationalement reconnues dans leurs domaines respectifs. Elles sont à l’origine d’avancées majeures en algorithmique, suivant des approches très variées, par exemple en résolution de contraintes par filtrage [Bessiere 2005], en complexité paramétrique [Heggerness 2007], ou sur les algorithmes d’approximation [Berry 2009]. La publication [Guindon 2003] décrivant un algorithme rapide pour la reconstruction phylogénétique, est l’article d’écologie et environnement le plus cité au monde.
L’objectif de NUMEV est de mettre en synergie ces compétences pour un double passage à l’échelle, tant quantitatif et imposé par la masse de données, que qualitatif et induit par le raffinement des modèles. Les résultats théoriques, les concepts et les outils développés pour répondre à ce défi, auront un caractère générique dépassant le cadre « environnement et vivant » et impactant l’ensemble des disciplines informatiques et mathématiques concernées.

Projet scientifique

L’irruption de nouvelles données dont le volume croît exponentiellement, associée aux questions essentielles posées par l’environnement et le vivant, impose des recherches fondamentales sur la formalisation de ces questions, leur complexité algorithmique intrinsèque, la conception de méthodes efficaces pour les traiter au mieux, la certification et mise à l’épreuve de ces méthodes sur des grands jeux de données simulées puis réelles. Des travaux spécifiques seront engagés dans chacune de ces directions par les équipes impliquées dans cet axe :

Algorithmique combinatoire

De nombreuses questions se formalisent à l’aide des objets usuels de l’informatique que sont les graphes (e.g. les réseaux génétiques), les arbres (e.g. phylogénétiques ou botaniques) ou les séquences (e.g. l’ADN), et se ramènent alors à des problèmes génériques, certains étudiés depuis longtemps mais nécessitant de nouvelles recherches pour passer à l’échelle, d’autres nouveaux, qui constituent un défi pour l’algorithmique combinatoire. Dans ce cadre, nous étudierons les liens mathématiques entre ces structures discrètes et les modèles géométriques [Gonçalves 2009]. Nous poursuivrons nos travaux sur la complexité paramétrique et les algorithmes d’approximation, appliqués aux questions biologiques [Berry 2009]. Nous traiterons des problèmes complexes d’indexation et d’algorithmique du texte posés par les méthodes de séquençage massif [Rivals 2009a]. Nous travaillerons sur l’utilisation d’algorithmes de graphes pour la compression, la protection et la transmission d’images [Amat 2010], ou la compression et la reconstruction de structures végétales [Fernandez 2010].

Méthodes numériques

En collaboration avec l'axe Modélisation de NUMEV, l’objectif sera de favoriser les interactions entre chercheurs autour des méthodes numériques avancées pour les problèmes environnementaux et du vivant : optimisation numérique (par exemple pour des problèmes d'érosion du littoral [Berthon 2008]), méthodes de discrétisation d'équations aux dérivées partielles vérifiant des propriétés physiques ou mathématiques très restrictives (par exemple pour les écoulements en milieux poreux anisotropiques [Droniou 2009]), et méthodes lagrangiennes du type éléments discrets, couplées avec un milieu continu [Radjai 2010]. L’accent sera mis sur les méthodes probabilistes de Monte-Carlo, très utilisées pour la résolution de problèmes complexes ne possédant pas de solution numérique explicite, pour lesquelles nous développerons des techniques adaptatives permettant le réglage automatique des paramètres d’implantation en cours d’exécution [Cappé 2008].

Filtrage, transformation de problèmes, méthodes heuristiques

De nombreux problèmes essentiels pour l’analyse du vivant et de l’environnement sont intrinsèquement difficiles (typiquement NP-complets). On a alors recours à des techniques de filtrage et de transformation de problèmes, qui produisent des instances plus simples et de dimension moindre, et à des approches heuristiques, qui ne garantissent pas l’optimalité mais produisent en général des solutions de bonne qualité. Dans ce cadre, nous poursuivrons nos travaux récents sur les méthodes de kernelisation appliquées aux graphes [Thomassé 2009]. En intelligence artificielle, nous proposerons un outil de résolution de contraintes utilisant l’apprentissage en ligne pour choisir en cours de résolution les heuristiques et les niveaux de filtrage les mieux adaptés [Bessiere 2007]. Nous étendrons aussi nos travaux sur la non-décomposabilité de contraintes à d’autres langages que la logique propositionnelle [Bessiere 2009]. En bioinformatique, où les heuristiques sont la norme, notre objectif sera de progresser dans l’étude théorique de celles-ci pour en démontrer les bonnes propriétés [Pardi 2010], et d’en diminuer encore la complexité en temps [Guindon 2010].
Calcul haute performance. Au-delà de l’amélioration des algorithmes, il est indispensable de mettre en place des implantations efficaces et sûres des grands calculs scientifiques, comme souligné dans Nature récemment [Merali 2010]. Il est par exemple classique de réduire la précision numérique (e.g. en se limitant aux flottants 32 bits) pour accélérer les temps d’exécution. Les algorithmes et leur implantation doivent alors être repensés pour limiter toute perte additionnelle de précision qui serait provoquée par le calcul lui-même [Langlois 2009]. Une alternative consiste à calculer de manière exacte en utilisant le calcul algébrique et l'algèbre linéaire haute performance [Dumas 2008].   L'arrivée de nouvelles architectures pour le calcul massivement parallèle (e.g. multi-coeur, GPU, Intel™ tera-scale project) est également en passe de modifier profondément les algorithmes et les modèles, notamment en matière de résolution d'équations aux dérivées partielles où l’on améliore déjà nettement les performances des codes standards [Cabrit 2009]. L'exploitation optimale de ces architectures  étant difficile, il est primordial de développer des outils logiciels simplifiant leur programmation. Afin d'être à la pointe de la révolution du calcul parallèle dans les années à venir, l'Université de Montpellier s'est doté d'un méso-centre de calcul appelé HPC@LR, qui sera une plate-forme idéale pour la discussion entre développeurs d'architectures et d'implantations, et les chercheurs des autres laboratoires plus tournés vers l'application.

Applications en environnement et vivant

Des applications réelles et essentielles, où le changement d’échelle est déjà d’actualité, constitueront l’objectif et le banc d’essai des concepts, procédures et techniques développés dans cet axe. En particulier, nous traiterons les données issues des nouvelles techniques de séquençage de l’ADN, qu’il s’agisse de traiter ces données à très grande échelle par des algorithmes innovants [Philippe 2009], de caractériser la diversité génétique des populations en combinant théorie de la coalescence et méthodes de Monte Carlo rapides [Beaumont 2009], ou de décrypter les génomes pathogènes par des méthodes d’apprentissage statistique [Bréhélin 2008].  En traitement de données environnementales satellitaires ou aériennes, nous travaillerons sur la visualisation et la fusion [Hayat 2008], avec comme principale difficulté l'hétérogénéité, par exemple de résolution lorsqu’il s’agit de combiner données satellitaires et mesures au sol [Chauve 2009]. Une autre application pilote sera la simulation de systèmes environnementaux complexes, par exemple la modélisation et la simulation de la croissance des plantes à différentes échelles [Costes 2008] et sous le contrôle des gènes [Stoma 2008], les milieux granulaires (sols, sédiments, roches ou neige [Radjai 2010]), ou les systèmes côtiers [Isèbe 2008].