![]() |
Séminaire du LaBRI 2003-2004Le jeudi, à 14h, amphithéâtre du LaBRI. |
27 mai 2004, David Sherman (LaBRI). Algorithmes et méthodes pour la bio-informatique.
La bio-informatique cherche à résoudre des problèmes scientifiques d'origine biologiques grâce à l'outil informatique. La conjugaison de ces deux domaines scientifiques a permis des avancées considérables ces dix ans passés, allant de la production et l'analyse de données à haut débit au développement de méthodes de prédiction et de simulation in silico de processus biologiques.
Dans ce séminaire je vous propose un survol de trois projets menés au sein du projet transversal « Algorithmes et méthodes pour la bio-informatique » du LaBRI, qui illustrent bien le dialogue que nous avons su établir entre biologistes et informaticiens. Chacun est caractérisé par une problématique biologique bien définie et des défis informatiques, identifiés grâce à un travail important de collaboration.
Génolevures est un projet de génomique comparée à grande échelle, mené par un réseau national de laboratoires coordonné par un GDR du CNRS. Le LaBRI fédère les travaux de bio-informatique du réseau, développe des méthodes d'analyse originales, et assure la diffusion de l'ensemble des résultats (génomes annotés, études spécifiques) produits au sein du réseau.
Saccharomyces siliceus est une collaboration avec l'Institut de Biochimie et des Génétiques Cellulaires (CNRS) qui vise la définition de structures formelles dont le fonctionnement se rapproche d'un être vivant, donnant ainsi une meilleure compréhension de la biologie cellulaire. Ultimement il permettrait de mener des expériences in silico.
IntAct est un projet européen piloté par l'Institut Européen de Bio-informatique ayant pour but la description précise des réseaux d'interactions protéine-protéine (PPI) grâce à la constitution des ressources fédérées et le développement d'outils logiciels spécifiques. Complexome est un volet expérimental de cette activité qui met au point des techniques bio-technologiques de détection de PPI à haut débit.
Je terminerai avec un aperçu du Centre de Bio-informatique de Bordeaux, et de quelques autres projets menés par mes étudiants : Malako, Hysme et B7 (co-encadré par Isabelle Dutour).
6 mai 2004, Robert Jeansoulin (LSIS-CMI - Université de Provence). Fusion d'informations géographiques.
La collecte d'informations géographiques fait appel à de nombreuses représentations dans des modèles divers. Les objets représentés sont eux-mêmes issus de concepts divers. Cette diversité est à la fois un obstacle, et aussi une richesse qui permet parfois de mettre en oeuvre des outils logiques (révision ou fusion de connaissances) qui sont inopérants dans le cas général. Entre algorithmique de résolution et méditation métaphysique, les travaux du projet européen REVIGIS (2000-2004) ont été amenés à aborder de nombreuses pistes théoriques et pratiques. Avec parfois quelque succès et en tout cas de nombreuses illustrations (inondation, érosion côtière, aménagement urbain, évolution du paysage).
29 avril 2004, Isabelle Puaut (INSA/IRISA). Estimation de durées d'exécution pour la validation temporelle de systèmes temps-réel.
Dans les systèmes temps-réel, la date de livraison d'un résultat temps est un critère de correction du système au même titre que le résultat lui-même. Les contraintes de temps auxquelles sont soumises les applications peuvent être par exemple des échéances de terminaison des tâches ou encore des contraintes de régularité d'exécution. Dans les systèmes temps-réel strict (e.g. transports), la violation d'une contrainte temporelle peut avoir des conséquences graves sur le plan humain, économique ou écologique, et il est alors impératif de valider leur comportement temporel dans tous les scénarios d'exécution, y compris les pires. Au contraire, dans les systèmes temps-réel souple (e.g. multimédia), la violation occasionnelle d'une contrainte de temps peut être tolérée, et on peut alors se contenter de garanties probabilistes sur le respect des contraintes de temps. Dans les deux cas, il est nécessaire de valider le comportement temporel du système avant sa mise en opération. De telles méthodes de validation sont nommées analyses d'ordonnançabilité dans la communauté temps-réel. Elles consistent, à partir d'un ensemble de tâches dont les caractéristiques sont connues (lois d'arrivée, durées d'exécution), à déterminer dans quel ordre exécuter les tâches, et à donner un verdict (déterministe ou probabiliste) sur le respect des contraintes de temps.
Une entrée clé des analyses d'ordonnançabilité est le temps d'exécution des tâches. Dans les systèmes temps-réel strict, on doit déterminer une borne supérieure des temps d'exécution des tâches pour valider leur comportement temporel dans tous les cas. Nous présenterons dans l'exposé les méthodes d'analyse de programmes que nous avons mises en place pour déterminer de telles bornes, nommées WCET (Worst-Case Execution Times). En particulier, nous mettrons en avant les problèmes posés par l'architecture matérielle sous-jacente (mémoires cache notamment) et les solutions que nous avons définies pour les résoudre. Nous aborderons aussi brièvement les travaux en cours sur l'obtention de durées d'exécution sous forme probabiliste, adaptées aux systèmes temps-réel souple.
22 avril 2004, Julien Cartigny (LIFL, Lille 1). Contributions à la diffusion dans un réseau ad hoc.
Les technologies sans fils ont atteint une place dominante ces dernières années. Le fait de laisser à l'utilisateur une totale liberté de mouvement et des débits grandissants ont popularisé ce moyen de communication. Pourtant, cette liberté est loin d'être, car elle est reliée à un point fixe de coordination des communications (une borne d'accès fixe dans le cas du système Wifi ou du GSM). Les réseaux ad hoc proposent une vision sans infrastructure, où le réseau est supporté par l'ensemble des utilisateurs mobiles. Dans un tel système, chaque mobile peut relayer un message de ses voisins, dans le but de permettre à chacun des noeuds de pouvoir joindre n'importe qui d'autre dans le réseau, à condition qu'il existe des noeuds sur le chemin pouvant relayer le message.
L'opération de diffusion (ou brodcast) est une opération courante dans de tels réseaux. Elle consiste à envoyer un message à l'ensemble des mobiles participants au réseau ad hoc. A cause de la mobilité, des possibilités de collision radio, de la connaissance limitée du voisinage et de la nature distribuée des algorithmes utilisés dans chaque noeud, cette opération peut se révéler coûteuse si elle est effectuée de manière naïve.
Dans la première partie du travail de recherche exposé, l'objectif est de réduire le nombre de messages émis par l'ensemble du réseau, de manière à réduire les risques de collisions tout en assurant une couverture complète. Le protocole BRP est un algorithme probabiliste dont la décision de réémission est biaisée par l'étude du voisinage commun entre deux noeuds. Le protocole RRS utilise l'algorithme de réduction de graphe pour réduire le voisinage de chaque noeud et ainsi permettre une prise de décision à partir d'un nombre limité de voisins.
Dans la deuxième partie, l'étude est portée sur la réduction du coût énergétique, qui dépend en grande partie des communications radios. Avec des antennes omnidirectionnelles, chaque mobile peut réduire sa portée. RBOP et LBOP tirent avantage de ce procédé en utilisant les algorithmes de réduction de graphe RNG et LMST afin de réduire la consommation tout en gardant un réseau connexe. Le cas des antennes directionnelles est également envisagé, avec la proposition d'un algorithme hybride ADLBOP utilisant une communication un-vers-un ou un-vers-tous en fonction du modèle énergétique affecté au coût de la transmission et de la topologie locale.
8 avril 2004, Arnaud Legrand (LIP / ENS Lyon). Ordonnancement asymptotique de graphes de tâches identiques et indépendants sur plate-forme hétérogène.
Sur une plate-forme hétérogène, la minimisation du makespan de l'ordonnancement d'un ensemble de tâches identiques et indépendantes est un problème dont la complexité est intimement liée à l'architecture de la plate-forme (étoile, chaîne, pieuvre, arbre). Après avoir rapidement présenté quelques résultats récents à ce sujet, nous montrons que le problème de la maximisation du débit en régime permanent d'une telle plate-forme est en revanche polynomial et ce, quelle que soit l'architecture de la plate-forme. Nous expliquons ensuite comment en déduire un ordonnancement asymptotiquement optimal quand le nombre de tâches à traiter devient grand. Enfin, nous montrons comment étendre partiellement ce résultat au cas d'un ensemble de graphes de tâches identiques et indépendants.
25 mars 2004, David Schmidt (Kansas State University, actuellement chercheur invité à l'Ecole Polytechnique). Extending over-approximating models: an introduction to mixed models and separation logic.
Programs, communicating processes, and storage heaps are often modelled by graphs, which are formalized by over-approximating relations. Then, correctness properties are validated on the models. It is well known that universal (but not existential) properties can be safely validated on over-approximating models.
In this presentation, we review over-approximating models and their specification logic. Then, we consider two approaches for enriching the model and logic for validating existential properties:
The presentation introduces mixed models and separation logic and explains why they are useful for modelling and validation.
11 mars 2004, Jérôme Durand-Lose (LIP / ENS Lyon et I3S / Université de Nice-Sophia Antipolis). Calculer géométriquement sur le plan -- machines à signaux.
Cet exposé se place dans l'étude des modèles du calcul continus. Nous y montrons que la géométrie plane permet de calculer. Nous définissons un calcul géométrique et utilisons la continuité de l'espace et du temps pour stocker de l'information au point de provoquer des accumulations.
Dans le monde des automates cellulaires, on parle souvent de particules ou de signaux (qui forment des lignes discrètes sur les diagrammes espace-temps), tant pour analyser une dynamique, que pour concevoir des automates cellulaires particuliers. Le point de départ de nos travaux est d'envisager des versions continues de ces signaux. Nous définissons un modèle de calcul continu, les machines à signaux, qui engendre des figures géométriques suivant des règles strictes. Ce modèle peut se comprendre comme une extension continue des automates cellulaires.
L'exposé commence par une présentation des automates cellulaires et la mise en avant d'exemples de particules/signaux tirés de la littérature. De là, nous abstrayons le modèle, les machines à signaux.
Dans un premier temps, nous montrons comment tout calcul au sens de Turing (par la simulation de tout automate à deux compteurs) peut y être mené. Nous montrons également comment modifier une machine de manière à réaliser des transformations géométriques (translations, homothéties) sur les diagrammes engendrés. Nous construisons également les itérations automatiques de ces constructions de manière à contracter le calcul à une bande (espace borné) puis, à un triangle (temps également borné).
Dans un second temps, nous nous intéressons aux points d'accumulation. Nous montrons que la prévision de l'apparition d'une accumulation est indécidable. Ce problème est même $\Sigma_2^0$-complet (hiérarchie arithmétique), en construisant pour tout automate à deux compteurs une machine à signaux et une configuration initiale simulant l'automate pour toutes les valeurs possibles. Nous prenons ensuite un point de vue statique, et non plus dynamique, sur les diagrammes espace-temps engendrés (de même qu'entre automates cellulaires et pavages). Pour chaque position, la valeur doit correspondre au voisinage sur un ouvert suffisamment petit. Muni de cet outil, nous regardons les plus simples accumulations possibles (les singularités isolées) et proposons un critère pour y « prolonger » le calcul.
4 mars 2004, Matthieu Roy (IRISA & Université Rennes 1). Protocoles d'accord par contrainte des données.
Nous nous intéressons aux problèmes de décision, qui sont une généralisation de la notion de vote : n entités communicantes proposent une valeur, effectuent un calcul, et doivent se mettre d'accord sur une ou plusieurs valeurs communes. Ce type de problème est largement utilisé dans les systèmes répartis, par exemple pour garantir la cohérence des données distribuées sur plusieurs sites.
Il a été montré que ce problème n'a pas de solution dans un système asynchrone, et plusieurs solutions ont été proposées pour contourner ce résultat d'impossibilité. Toutes les solutions proposées jusqu'à maintenant renforcent le système d'exécution, soit en imposant des bornes temporelles, soit en y ajoutant des boîtes noires garantissant des propriétés additionnelles, comme les détecteurs de défaillances.
Dans cet exposé, nous présentons une approche orthogonale en nous intéressant non pas au système, mais aux données. Nous montrons qu'il est possible d'écrire des protocoles qui résolvent ce type de problème lorsque les valeurs proposées par les processus satisfont certaines contraintes, connues a priori.
Nous montrons que cette classe de protocoles peut être définie par des propriétés simples, et donnons des algorithmes génériques pour plusieurs problèmes d'accord. Un des avantages de cette approche est que tous les protocoles obtenus sont sûrs : si l'hypothèse sur le motif des valeurs proposées est valide, le protocole résout le problème, et si les hypothèses ne sont pas vérifiées, le protocole peut converger, mais dans tous les cas garantit la spécification du problème.
Nous montrons aussi que cette approche permet de choisir entre le nombre de cas dans lesquels le protocole converge et la quantité de communication nécessaire. A cet effet, nous présentons un algorithme à qualité de service modulable, qui permet de synchroniser les vues qu'ont les processus de l'état global du système.
L'intérêt de cette approche est à la fois théorique et pratique : la sûreté garantie des algorithmes permet de les utiliser comme oracle afin d'accélérer les protocoles habituellement employés à la résolution des tâches d'accord distribué.
12 février 2004, Ofer Hadar (Ben Gurion University). Perceptual Video Assessment Modeling and Error Concealment for Video Transmission over QoS - IP Networks.
Digital video communication systems exhibit diverse types of distortions that are strongly influenced by actual video content, compression methods and transmission capabilities. Recently, with the beginning of the deployment of commercial visual services over packet switching networks, the motivation to optimize performance and assure a grade of service of digital video communication systems has become a necessity. This research area is very promising and it is expected that in the future most communication systems will be involved with multimedia communication.
In this seminar I begin with an extended introduction on video coding, and current problems with transmission of compressed-video over IP networks. Then I will describe our recent results in perceptual video assessment modeling and quality metrics for Quality of Service (QoS)- IP networks transmission. In this research the proposed models and metrics are fitted to human perception using extensive data from subjective experiments. A wide range of scenes and test conditions were applied in the subjective experiments in order to establish the relationship between the perceived qualities and the computational models. The computational results of these experiments can be used to optimize the performance of digital imaging systems with respect to visual content, compression and transmission.
At the end of the seminar I will present a new hybrid error concealment algorithm for a compressed video transmitted over a lossy packet switching network, which may cause serious and visible degradation to the decoded video stream. This algorithm includes consideration of the spatial and temporal activity in the surrounding of a lost block, and introduces 4 thresholds, which lead to choosing the optimal concealment scheme for each block.
This work is a joint research with my Ph.D. student Ron Shmueli and my Master students Merav and Revital Huber.
29 janvier 2004, Patrick Amar (LRI, Orsay). Modélisation d'interactions protéine-protéine avec un automate cellulaire.
De nombreuses voies métaboliques dans les cellules (eucaryotes et procaryotes) mettent en évidence des réactions catalysées par des protéines (fonction enzymatique). Dans les expériences faites 'in vitro' le milieu est homogène et le volume considérablement plus grand que dans une cellule, on doit mettre de grosses quantité de réactifs pour obtenir la concentration nécessaire à l'établissement des réactions chimiques. A contrario dans une cellule, la quantité de réactifs est tellement faible que, bien que le volume soit lui aussi très réduit, la concentration est largement trop basse pour que les réactions métaboliques puissent avoir lieu : la cellule ne devrait pas survivre... L'idée est que les concentrations locales sont elles suffisamment élevées pour les réactions se fassent et que les processus métaboliques aient lieu.
Pour modéliser le fonctionnement de ces voies métaboliques 'in vivo' les systèmes continus (à base d'équations différentielles de réaction/diffusion) ne sont pas adaptés: dans certains processus cellulaires un très petit nombre de molécules sont mises en jeu (de l'ordre de quelques dizaines), peut-on encore parler de propriétés macroscopiques avec si peu d'intervenants ?
On a donc opté pour un modèle discret au niveau macromoléculaire (de l'ordre de grandeur d'un protéine). La cellule est représentée par un volume limité par une membrane qui contient le nombre de molécules des réactifs de la voie métabolique étudiée correspondant à ce qui existe réellement dans une cellule vivante. La cellule simulée peut contenir des compartiments, et le milieu n'est pas forcément homogène (la viscosité peut etre fonction de la localisation spatiale). Le simulateur prend en entrée un fichier décrivant les réactifs: type, vitesse nominale de diffusion, etc. et les réactions: formation de complexes, échange de groupes (phosphorylation et déphosphorylation par exemple), ainsi que la cinétique de ces réactions. En cours de fonctionnement, le simulateur produit à la fois un affichage 3D de la cellule et de son contenu, en reconnaissant et affichant les complexes (agrégats de macromolécules) avec leur localisation dans la cellule, et un affichage sous forme de courbes de l'évolution des concentrations des divers produits (de façon analogue aux courbes résultant des expériences 'in vitro'). Un histogramme du nombre et de la taille des complexes est aussi affiché.
L'accent est particulièrement porté sur l'étude des complexes car il est montré que les réactions peuvent être de plusieurs ordres de grandeur plus efficaces avec les chaînes enzymatiques agrégées plutôt que par libre diffusion, ce qui expliquerait pourquoi dans une cellule vivante certaines voies métaboliques fonctionnent avec une faible concentration de réactifs.
L'hypothèse biologique qu'on veut valider est celle d'hyperstructure, c'est a dire un agrégat de protéines qui s'auto-assemble, qui perdure du fait même de son fonctionnement, et qui se désagrège lorsque le fonctionnement est terminé.
Au cours de l'exposé je montrerai deux (ou plus si j'ai le temps!) exemples de simulation: le système de phosphotranspherase (PTS) du glucose qui permet de recruter des sucres depuis l'extérieur de la cellule (procaryote) et de le transporter à l'intérieur, et la formation de filaments d'actine (qui est l'un des composants du cytosquelette des cellules).
8 janvier 2004, César Viho (IRISA & université Rennes I). Nouvelles orientations en matière de tests d'interopérabilité.
L'objectif principal dans le domaine des réseaux de télécommunication est l'interopérabilité des composants (développés éventuellement par des constructeurs différents) qui interviennent dans l'acheminement des informations. Pour atteindre cet objectif, différents types de tests (dont le test de conformité et d'interopérabilité) sont réalisés pour s'assurer, dans la mesure du possible, de l'interopérabilité de ces composants avant leur déploiement effectif. Le test de conformité s'intéresse à une implémentation particulière et essaie de vérifier que son comportement correspond à ce qui est décrit dans la spécification d'origine. Le test d'interopérabilité essaie d'évaluer la capacité de deux ou plusieurs implémentations à interagir correctement. Le domaine du test de conformité est relativement bien maîtrisé, avec notamment l'existence d'une norme ISO-9646 qui donne un cadre méthodologique formalisé pour le test de conformité, voire l'existence d'outils de génération automatique de tests de conformité à partir de spécifications formelles. A l'inverse et malgré de nombreuses tentatives, il n'existe pas de définition précise de la notion d'interopérabilité et encore moins de méthodologie bien précise pour le test d'interopérabilité. Ainsi, il existe plusieurs architectures et plusieurs méthodes pour le test d'interopérabilité. Ce qui pose le problème de la validité des résultats de test obtenus et de degré effectif d'interopérabilité des produits testés. Cependant, force est de constater que la pratique industrielle du test d'interopérabilité donne des résultats relativement satisfaisants.
Cette présentation sera composée de deux parties. Dans la première partie, je me propose de présenter l'état de l'art en matière de test d'interopérabilité. Nous y traiterons des points suivants :
Dans la deuxième partie, je donnerai quelques éléments sur la pratique industrielle du test d'interopérabilité et notamment dans la communauté Internet en m'appuyant sur l'activité autour du test d'interopérabilité des protocoles IPv6 (la nouvelle version du protocole Internet). Nous y aborderons les points suivants :
Jean Bétréma, bureau 303, LaBRI, tél. (05-40-00) 60-95.
Actes du séminaire :