Liste des événements uniques du groupe BioInformatique et Visualisation


2019-11-07Integer Programming solutions for international kidney exchange programmes
11:00-12:00
salle 178, LaBRI
In kidney exchange programmes patients with end-stage renal failure may exchange their willing, but incompatible living donors among each other. National kidney exchange programmes are in operation in ten European countries, and some of them have already conducted international exchanges through regulated collaborations. The exchanges are selected by conducting regular matching runs (typically every three months) according to well-defined constraints and optimisation criteria, which may differ across countries. In this work we give integer programming formulations for solving international kidney exchange problems, where the optimisation goals and constraints may be different in the participating countries and various feasibility criteria may apply for the international cycles and chains. We also conduct simulations showing the long-run effects of international collaborations for different pools and under various national restrictions and objectives.
 Plus d'infos  


2017-10-19Finding a gene tree in a phylogenetic network
11:00-12:00
salle 178, LaBRI
Phylogenetic networks have been introduced as a model generalizing phylogenetic trees in order to represent the evolution of species. Contrary to trees, it allows to represent the transfer of genetic material between coexisting species or populations, through recombination, hybridization or horizontal gene transfers. Several methods have been proposed to reconstruct phylogenetic networks by combining together gene trees, where each gene tree represents the evolution of one gene. These methods expect the gene trees to be contained in the reconstructed phylogenetic network, but given the tree and the network, just checking if the tree is contained in the network is already an NP-hard problem. We will present some subclasses of phylogenetic networks where polynomial-time algorithms can be found for this decision problem, as well as a system describing those subclasses and their inclusions.
 Plus d'infos  


2016-12-08D-Wave, le début de l'informatique quantique
10:00-11:00
Amphi, LaBRI
La société canadienne D-Wave a commencé la commercialisation de la machine D-Wave 2X, présentée comme le premier calculateur quantique disponible.
Quelles sont les capacités de cette machine? Comment fonctionne-t-elle? Je vais tenter de répondre à ces questions, et présenterai les résultats des premiers tests effectués sur de l'algorithmique des graphes.
 Plus d'infos  


2016-06-30Mécanique chromosomique de l’oncogenèse des Leiomyosarcomes
11:00-12:00
178
Depuis 2009, le consortium international ICGC (International Cancer Genome Consortium) a pour objectif de séquencer le génome de 50 types de cancers différents. Parmi ceux-ci nous avons la charge de celui des Leiomyosarcomes, tumeur mésenchymateuse très agressive. Ces sarcomes sont caractérisés par une génétique très complexe basée sur de nombreux réarrangements chromosomiques et mutations. Nous présenterons comment l’analyse des données de séquençage (WGseq et RNAseq) d’une première série de 68 LMS nous permet d’avancer dans notre compréhension de cette oncogenèse.
 Plus d'infos  


2016-06-23Analyse de l'hétérogénéité clonale
11:00-12:00

Le cancer demeure la principale cause de décès dans le monde en raison de sa capacité à échapper aux traitements disponibles. Les progrès récents dans le séquençage de l'ADN ont permis de mettre en avant certaines caractéristiques des tumeurs. En effet, les cellules tumorales d'une même tumeur ne partagent pas toutes le même ADN et certaines d'entre elles développent des caractéristiques génétiques uniques qui les amènent à réagir différemment à certaines thérapies. Ainsi, la caractérisation génotypique des différentes sous-populations tumorales présentent dans la tumeur du patient semble essentielle au choix du traitement à administrer. C'est dans ce contexte que nous avons répondu au challenge SMC-Het qui vise à évaluer différents algorithmes développés par des équipes de bio-informatiques à l'international en proposant une nouvelle approche. Nous allons vous présenter deux approches que nous avons développer.
 Plus d'infos  


2016-06-09Réseaux multiplexes, sciences sociales et bases de données de graphes: la nécessité plutôt que l’obsession du "big data"
11:00-12:00
178
Cette présentation se propose d’illustrer en quoi les bases de données de
graphes s’imposent lorsque le modèle de données met en jeu un graphe faisant
apparaître des attributs variés et complexe. Même dans le cas où le graphe est
“petit”, parce qu’il est “complexe”, les approches relationnelles classiques
sont mises à mal alors que les bases de données de graphes épousent
naturellement et efficacement le modèle de données. Ce constat se base sur une
expérimentation menée en collaboration avec des chercheurs en sociologie et en
droit.
 Plus d'infos  


2016-05-191-2-3-4: a story about whole genome duplications in fish and other vertebrates
11:00-12:00
178

Gene and genome duplications, which increase gene copy number at different scales, are considered to be important contributors to the evolution of organisms. During the evolution of vertebrates, two successive rounds of whole genome duplication, called 1R and 2R have highly influenced the organization of gene content of genomes. After WGDs, genomes returned progressively to a diploid state, but a certain amount of genes were kept as duplicates, which led to the formation and extension of many gene families. A fish-specific genome duplication called 3R occurred at the base of the teleost fish lineage. A fourth round of WGD has also been characterized in the Salmonidae. Examples of gene family expansion in vertebrates will be presented.
 Plus d'infos  


2016-04-28Patterns en biodiversité et formes de nuages de points
11:00-12:00
178
L'étude de la biodiversité a été l'un des piliers de la biologie, et son unique objet pendant des siècles. La théorie de l'évolution est un cadre unificateur qui permet de comprendre les processus qui l'ont façonnée. Depuis une vingtaine d'années, la diversité taxonomique est étudiée sous l'angle moléculaire. Cette approche a été le point de départ de très nombreuses études de phylogénies moléculaires (la diversité comme fruit de l'histoire). Récemment, l'accès à la diversité du vivant s'est élargi par la production massive de données, via les technologies NGS.

Dans ce séminaire, je présenterai un cadre pour aborder quelques questions liées aux patterns de biodiversité avec un effort de formulation rigoureuse, et des pistes de connexion avec des domaines en mathématiques et informatiques appliquées, en ayant en tête le fameux " passage à l'échelle " devant l'afflux massif de données issues de NGS. Cela impose de travailler sur des matrices de distances, ou dissimilarités, plus que des approches phylogénétiques.

Trois types d'approches seront présentées, avec à chaque fois une approche classique, un exemple, des questions pour connecter ces approches à un domaine, en général du " machine learning ", et des façons d'aborder le passage à l'échelle :

comment construire des OTUs ("Operational Taxonomic Units ", une question de clustering non supervisé, à la fois avec une approche géométrique (isométries dans un espace euclidien ou pseudo-euclidien), ou structurales (cliques, communautés ou composantes connexes sur graphes)
comment construire un inventaire taxonomique connaissant un ensemble de reads issus de séquençages NGS et une base de référence annotée (classification supervisée).
 Plus d'infos  


2016-04-14Prefrontal cortex model for language acquisition as abstract sequence learning applied to human robot interaction, and some canary songs ...
11:00-12:00
178
The topic of this presentation is embedded in the general topic of symbolic sequence processing with artificial neural networks. Primates can learn complex sequences that can be represented in the form of categories, and even more complex hierarchical structures such as language. The prefrontal cortex plays a major role in these processes. We model part of the prefrontal cortex using the Reservoir Computing framework: random recurrent neural networks allowing for high-dimensional dynamics. The model we generated, was applied to language processing using grammatical constructions. Even without world semantic information, the model network is able to generalize to unknown sentence constructions and make online predictions of thematic roles (" Who did what to whom? ") concerning future words. We propose a link between the model dynamics and Evoked-Related Potentials (ERP) observed when unusual sentences are processed by humans. The model was successfully applied to Human-Robot interaction in order to enable human users to teach the robot natural language sentences. Recently we showed that the very same instance of the model (same random connections) could learn both English and French sentence constructions simultaneously.
A short glimpse on a current study about the structure of canary songs will also be given.

** Relevant references:
* Core description of the model:
http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0052946
* Model applied to user corpus for robot commands processing both English and French at the same time:
https://www.researchgate.net/publication/284691419_A_Recurrent_Neural_Network_for_Multiple_Language_Acquisition_Starting_with_English_and_French
* Implementation of the model on the iCub and inverse model for language production
http://journal.frontiersin.org/article/10.3389/fnbot.2014.00016/abstract

** Video of an application to Nao robot with 2 collaborators (on 3D vision and speech):
http://bit.ly/humanoidly-speaking

** My last project: EchoRob (that I just finished in Hamburg):
https://www2.informatik.uni-hamburg.de/WTM/projects/EchoRob/EchoRob.shtml
 Plus d'infos  


2016-03-31Résumer le Negative-Skycube pour optimiser les requêtes skyline multidimensionnelles
11:00-12:00
178
Soient T une table et D l'ensemble des attributs décrivant les tuples de T. Soient t et u deux tuples
appartenant à T. on dit que t domine u si et seulement si t est au moins meilleur que u dans chaque
dimension et il existe au moins une dimension dans laquelle t est strictement meilleur que u. On dira
également que t est un point skyline de T si et seulement s'il n'est dominé par aucun point de T. Une
requête skyline relative à un espace X inclus dans D retourne l'ensemble des points skyline
relativement à X. Le skycube de T est l'ensemble des skyline obtenus en considérant chaque sous-
ensemble de D.
En raison du nombre exponentiel de requêtes skyline, il est crucial de résumer cette information.
Les précédents travaux résument la liste des sous-espaces de D pour lesquels un tuple particulier t
appartient au skyline. Dans ce travail, nous considérons l'approche complémentaire qui consiste à
résumer l'ensemble des sous-espaces pour lesquels un tuple t ne fait pas partie du skyline (Negative-
Skycube). Malgré l'apparente équivalence entre ces deux approches, nos résultats expérimentaux
montrent qu'elles ne nécessitent pas le même effort. Par exemple, notre approche nécessite moins
d'espace et de temps lorsque le nombre de tuples ou le nombre de dimensions augmente. Ceci
pourrait s'expliquer par le fait que lorsque le nombre de dimensions augmente, les tuples ont
tendance à être incomparables (l'un ne domine pas l'autre et réciproquement), rendant la taille du
skyline plus grande. De ce fait, la proportion de sous-espaces dans lesquels un tuple t n'appartient
pas au skyline tend à diminuer. Plus précisement, nos expérimentations sur données synthétiques et
sur données réelles montrent que (i) le résumé du Negative-Skycube peut être obtenu plus
rapidement que les techniques de l'état de l'art, (ii) en général, celui-ci requière moins d'espace et
(iii) les requêtes skyline en sont retournées plus rapidement.
 Plus d'infos  


2016-03-03Le soft computing pour la biométrie
11:00-12:00
178
Face à un marché de la sécurité en plein essor, et aux méthodes informatiques traditionnelles employées (accès
par codes et/ou mots de passe) dont les limites ont rapidement été démontrées, la biométrie s'impose de manière
indéniable comme la technologie d'avenir dans le domaine de la sécurité mais aussi du confort d’utilisation. La
biométrie est le domaine technologique traitant de la vérification d'identité et/ou de l'identification de personnes
par leurs caractéristiques individuelles, pouvant être morphologiques ou comportementales. Cependant l'usage
de la biométrie souffre de certains problèmes tels que les problèmes de faux rejet, de fausse acceptation. De
plus, les systèmes biométriques uni-modaux permettent de reconnaître une personne en utilisant une seule
modalité biométrique, mais ne peuvent pas garantir avec certitude une bonne identification car chaque modalité
biométrique souffre de limitations qui lui sont propres et qui dégradent les performances du système biométrique.
Afin de surmonter ces limites, les systèmes biométriques multimodaux ont été mis en place. Ces systèmes utilisent
plusieurs signatures biométriques d'une même personne. Le domaine de la biométrie comporte plusieurs sous
modules tels que le domaine de traitement d'image biométrique, le domaine d'extraction de caractéristiques
et le domaine de la fusion des données biométriques. Ces domaines étant de nature informatique reste loin
d'être résolue à cause de la nécessité de traiter des quantités très élevées d'information ce qui donne lieu à une
complexité algorithmique très élevée. Le soft computing est une voie d'études qui a fait l'objet de recherches
intensives depuis plusieurs années. Ce domaine s'intéresse à la réduction de la complexité algorithme en faisant
un compromis entre le temps et la qualité de la solution recherchée. Il couvre un large éventail de problèmes
qui surgissent dans de nombreux domaines applicatifs comme l'industrie, le transport, la télécommunication et
le traitement d’image.
Dans notre projet de thèse, nous proposons de nouvelles approches qui utilisent le soft computing, plus
précisément les méta-heuristiques comme un outil de résolution des problèmes rencontrés en biométrie.
 Plus d'infos  


2016-02-18Exploration interactive et visuelle de larges collections d'images
11:30-12:00
178
L'objectif de ces travaux de recherche est de permettre l'exploration de collections d'images.

Une attention particulière est portée sur les 3 contraintes suivantes :

(i) permettre d'explorer de larges collections d'images (plus d'1 million);

(ii) gérer des collections dynamiques (e.g. rajout d'images au cours du temps);

(iii) proposer une interface interactive et intuitive à l'utilisateur.



Pour ce faire, nous utilisons des structures hybrides arbre-graphe.

Ces dernières sont ensuite visualisées au sein d'une plateforme web de visualisation de graphes d'images.



Une digression sur l'application au domaine du 'Document Image Analysis' sera aussi faite pour rebondir sur le projet ACID du LaBRI
 Plus d'infos  


2016-02-11Stevia rebaudiana : Etude de la diversité génétique et phénotypique. Premières contributions à son amélioration génétique en vue d’une adaptation à l’agriculture biologique en France.
11:00-12:00
178
Les glycosides de steviol extraits de Stevia rebaudiana constituent des édulcorants naturels puissants acaloriques. L’utilisation de ces composés naturels en agro alimentaire explose et leur marché est en pleine expansion.
En Europe, la totalité des extraits sont importés et 90% proviennent de Chine sans aucune traçabilité. Dans ce contexte, développer, en France et en particulier dans le Sud-Ouest, une filière de production biologique, permettrait d’une part de positionner les agriculteurs sur ce marché et d’autre part de proposer à l’industrie et au consommateur des produits de qualité à haute valeur ajoutée. Ceci nécessite de connaitre la variabilité génotypique et phénotypique existante et de pouvoir proposer dans le futur de nouvelles variétés adaptées aux conditions régionales de production.
Afin de répondre à cette demande, en partenariat avec les sociétés Oviatis, Rouages et Invénio, nous caractérisons la variabilité génétique à notre disposition de Stevia rebaudiana et les phénotypes de production de glycosides de stéviol associés dans un contexte de production biologique dans le Sud-Ouest Nous réalisons des descendances pour détecter les zones du génome associées aux caractères d'intérêt et amorcer une démarche de sélection. Nous envisageons une démarche de séquençage complet de cette espèce.
 Plus d'infos  


2016-02-04Les mécanismes épigénétiques chez les végétaux ou la mémoire des plantes : Le cas du mûrissement des fruits de tomate
11:00-12:00
178
Si le génotype peut être défini comme l’ensemble de l’information stockée dans le génome d’un individu, c’est bien l’expression de ce génome qui permet de créer un phénotype particulier. Or il est maintenant bien établi que l’expression du génome est influencée par de nombreux paramètres internes aux individus (développement) mais aussi en lien avec leur environnement. Par exemple, une larve d’abeille deviendra une reine ou une ouvrière simplement en fonction de la façon dont elle est nourrie. Cette différence de devenir n’est pas due à un changement de l’information génétique elle-même, mais à la façon dont elle a été utilisée. Ainsi, l’épigénétique a pour sujet l’étude «des changements d'activité des gènes — donc des changements de caractères — qui sont transmis au fil des divisions cellulaires ou des générations sans faire appel à des mutations de l'ADN».
L’ADN est un polymère composé d’un enchaînement de nucléotides (une base azotée A, T G ou C associé à un sucre et à un phosphate). Chez les eucaryotes, une des bases azotées, la cytosine (C), peut être méthylée. La méthylation des cytosines est une des marques épigénétiques les plus importantes, impliquées dans de nombreux processus liés au fonctionnement du génome, tels que l’expression des gènes, la mobilité des éléments génétiques mobiles ou encore la recombinaison de l’ADN. Toutes les cytosines d’un génome ne sont pas méthylées et leur distribution, caractéristique d’un type cellulaire donnée, peut être influencée par l’environnement de la cellule
Nous avons analysé les mécanismes responsables de la dynamique des cytosines dans le contexte du développement et du murissement des fruits de tomate. Nos travaux montrent que lorsque l’on interfère soit avec les processus de méthylation soit avec ceux permettant de déméthyler l’ADN, le développement et la maturation des fruits sont fortement altérés. Cela se traduit par un changement de forme, de couleur ou encore de la composition en métabolites des fruits et s’accompagne d’un changement profond du fonctionnement du génome. Nous avons démontré que le changement de fonctionnement de certains gènes ciblés est strictement corrélé à une redistribution locale des cytosines méthylées. Nous avons maintenant pour objectif d’étudier à l’échelle du génome de tomate entier, la redistribution globale des cytosines méthylées afin d’établir les liens existant entre changement de phénotype des fruits, expression des gènes et redistribution des cytosines méthylées. Enfin nous avons initié des études similaires chez d’autres types de fruits (ex : la baie de raisin) afin d’évaluer si les mécanismes identifiées chez la tomate ont une importance plus générale.
 Plus d'infos  


2016-01-28Importance de la conformation de l’ADN dans la régulation de l’expression génique
11:00-12:00
LaBRI, salle 178
Introduction à l’analyse de données Hi-C: des reads aux interactions. Hi-C est l’une des principales méthodes d’investigation de la co-localisation spatiale de l’ADN. Cette co-localisation représente les interactions ADN-ADN. Cependant, les données brutes issues des expériences Hi-C comportent des biais importants et des contacts aléatoires, ce qui rend l’identification des interactions réelles difficile. Les méthodes bioinformatiques existantes sont basées sur des modèles complexes pour prendre en compte les biais et ne fournissent pas de seuil de significativité pour détecter les interactions. Je vais vous présenter un modèle probabilistique binomial simple qui résout les biais complexes et distingue les vraies interactions des fausses. Le modèle corrige les biais d’origine connue et inconnue et calcule une p-valeur pour chaque interaction, fournissant un seuil fiable basé sur cette significativité. Nous avons montré ceci expérimentalement en testant l’outil sur un experience d’interactions aléatoires. Cette méthode donne de meilleurs résultats que les méthodes précédentes et fournit un framework statistique pour de futures analyses, comme la comparaisons d’interactions Hi-C entre différentes conditions.
 Plus d'infos  


2015-12-17Can we improve the usefulness and engineering of biomedical ontologies?
11:00-12:00
LaBRI, salle 178
The Gene Ontology has demonstrated in the last years the usefulness of ontologies for supporting the analysis of biomedical data. Such success has provoked the development of many biomedical ontologies, and repositories like BioPortal store nearly 500 hundred ontologies. The content of these ontologies is usually rich in natural language (friendly for humans) but not so rich in logical axioms (not so friendly for machines), which limits the automatic exploitation of the content by means of applications and the possibilities of more fine-grained data analyses. This is usually called hidden semantics. In this talk, we will describe the efforts made to analyze convert such hidden semantics into explicit content and potential applications to detect irregularities and flaws in the design and engineering of the ontologies. Examples with relevant ontologies and terminologies like the Gene Ontology and SNOMED CT will be presented.
 Plus d'infos  


2015-12-03Introduction aux Interfaces Tangibles
11:00-12:00
178
 Plus d'infos  


2015-10-15All [I know] about common and conserved nested intervals
11:00-12:30
salle 178, LaBRI
In this talk I will first recall the notion of common and conserved intervals or permutations. Then I will explain how to easily compute gene clusters formalized by generalized nested common or conserved intervals between a set of K genomes represented as K permutations. A b-nested common (resp. conserved) interval I of size |I| is either an interval of size 1 or contains another b-nested common (resp. conserved) interval of size at least |I|-b. When b=1, this corresponds to the original notion of nested interval. I will exhibit two simple algorithms to output all b-nested common or conserved intervals between K permutations in O(Kn+nocc) time, where nocc is the total number of such intervals. I will eventually explain how to count all b-nested intervals in O(Kn) time.
Joint work with Fabien de Mongolfier (LIAFA, Paris-7) and Irena Rusu (LINA, Univ. of Nantes).
 Plus d'infos  


2015-09-08Forage des réseaux sociaux
14:00-15:00
178
Un réseau social est un graphe dont les nœuds sont des individus interconnectés par des liens représentant des relations ou des intérêts en commun. Actuellement, les sites de réseaux sociaux (p. ex. : Facebook, Twitter, Blogs, etc.) mettent en réseaux des millions d’utilisateurs ce qui permet aux entreprises qui opèrent dans cette industrie de collecter des masses importantes de données sur les utilisateurs de ces services. Ces données cachent des connaissances décisives face au marché et à la concurrence et leurs analyses deviennent une tâche primordiale. Les techniques d’analyse des réseaux sociaux sont spécifiquement désignées à cette fin. L'analyse des réseaux sociaux dans le Web couvre un ensemble de problèmes dont les principaux sont : l’extraction des communautés, l'identification des rôles des individus, l'étude et la prédiction de l'évolution des réseaux. Dans le cadre de cet exposé, nous présenterons nos travaux qui se rattachent à la détection des communautés dans les réseaux unidimensionnels et multidimensionnels ; l’identification des acteurs influent et malicieux dans médias sociaux ; la détection de changements structuraux dans l’évolution du réseau.
 Plus d'infos  


2015-09-08New Challenges for Multimedia Big Data
10:00-12:00
178
Two unique paradigms may be revolutionary for big data. The WWW was invented to create a Web of documents about 25 years ago. The 21st century began with a major disruption: Photos are the new “documents.” Photos and videos communicate directly, without the need for language or literacy. We urgently need a new type of web to navigate this ever-increasing global repository of knowledge and experiences. This Visual Web offers opportunities to address new societal issues and solve many difficult yet unsolved problems.
The second challenging problem is to connect needs of people to appropriate resources efficiently, effectively, and promptly. Availability of enormous volumes of heterogeneous Cyber-Physical-Social (CPS) data streams allows design and implementation of networks to detect situations as they evolve. Such systems are very useful for solving many important problems. We are developing an approach towards building social life network that are first step towards building such smart social systems that connect needs to resources.
In this presentation I will discuss implications of Visual Web and Social Life Networks in emerging applications.
 Plus d'infos  


2015-06-25SAT-based Metabolics Pathways Analysis without Compilation
11:00-12:00
178

Elementary flux modes EFMS are commonly accepted tools for meta-bolic network
analysis under steady state conditions. They can be defined as the smallest
sub-networks enabling the metabolic system to operate in steady state with all
irreversible reactions proceeding in the appropriate direction. However, when
networks are complex, the number of EFMSquickly leads to a
combinatorial explosion, preventing from drawing even simple conclusions from
their analysis. Since the concept of EFMSanalysis was introduced
in 1994, there has been an important and ongoing effort to develop more
efficient algorithms. However, these methods share a
common bottleneck: they enumerate all the efms which make the computation
impossible when the metabolic network is large and only few works try to search
only efms with specific properties. As we will show in this paper, enumerating
all the efms is not necessary in many cases and it is possible to
directly query the network instead with an appropriate tool. For ensuring
a good query time, we will rely on a state of the art SAT solver, working on a
propositional encoding of EFMS, and enriched with a simple SMT-like solver
ensuring efms consistency with stoichiometric constraints. We illustrate our
new framework by providing experimental evidences of almost immediate answer
times on a non trivial metabolic network.
 Plus d'infos  


2015-06-18Looking for mutations in PacBio cancer data: an alignment-free method
11:00-12:00
salle 178, LaBRI
L'étude clinique EORTC 10994 a été mise en place afin de déterminer si le statut de p53 permet de sélectionner la thérapie des patientes atteintes de cancers du sein. L'identification des mutations du gène TP53 par séquençage NGS des ARNm de TP53 s'est révélée efficace lors d'une étude pilote effectuée. Afin de déterminer les mutations TP53 présentes chez l'ensemble des patientes (plus ou moins 1500), l'ARNm TP53 tumoral a été séquencé par la technologie de séquençage de troisième génération "Pacific Bioscences". Cependant, le pipeline de ''étude pilote ainsi que ceux utilisant GATK se sont révélés inappropriés pour ce type de données. En effet, au fort taux d'erreurs de séquençage généré par PacBio (plus ou moins 15%) s'ajoute la contamination des échantillons tumoraux par le tissus sain. Le faible taux de mutation attendu pour certains échantillons rend impossible la différenciation des erreurs de séquençage des réelles mutations par les outils standards. Afin de contourner ce problème, nous avons mis en place une méthodologie de détection de mutations par utilisation des graphes de De Bruijn que je vais vous présenter dans le cadre de ce séminaire.
 Plus d'infos  


2015-06-11Exposés scientifiques des étudiants de M2
11:00-12:45
178
* Antoine Laumond (G. Melançon)
* Tristan Brachelaire (R. Uricaru et G. Blin)
* Marie Gasparoux (M. Nikolski)
* Haolin Ren (G. Melançon)
 Plus d'infos  


2015-06-04Exposés scientifiques doctorants 1ère année
11:00-12:00
salle 178, LaBRI
1ère partie
Orateur: Alexandre Perrot

Titre: Architectures pour la visualisation multi-niveaux de données massives

Résumé:
La visualisation de données massives pose de nombreux défis pour les techniques actuelles.
Dans cette présentation, nous verrons tout d'abord un système de visualisation de carte de chaleur issues de données géolocalisées, en utilisant une approche multi-niveaux grâce du calcul distribué.
Ensuite, je présenterai une bibliothèque de visualisation permettant de réaliser des animations fluides avec de nombreux éléments affichés, en utilisant le "double buffering pour la visualisation.

2ème partie
Orateur: Antoine Hinge

Titre: Calcul distrbué pour le dessin de grand graphes

Résumé:
Le dessin de graphe est confronté aujourd'hui au problème de la taille toujours plus importante des jeux de données. Une solution peut y être trouvée en utilisant le calcul distribué.
Nous présenterons un algorithme distribué de dessin de graphe par modèle de forces ainsi que les technologies utilisées pour son implémentation. En plus de nos premiers résultats, nous proposons une ouverture sur la suite de nos travaux de thèse.
 Plus d'infos  


2015-05-28Read mapping and read compression on de Bruijn graphs
11:00-12:00
salle 178, LaBRI
1st part: Read mapping

Mapping reads on references is a central task in numerous genomic studies. Since references are mainly extracted from assembly graphs, it is of high interest to map efficiently on such structures.
During this seminar I'll motivate the problem of mapping reads on a de Bruijn graph and I'll present a practical solution and its implementation called BGREAT. BGREAT handles real world instances of the problem with moderate resources, as witnessed by the results that will also be presented.

2nd part: Read compression

Data volumes generated by NGS is a major concern. It triggered the need for more efficient methods than general purpose compression tools like gzip.
In this seminar I will introduce Leon, a reference-free compression method based on a de Bruijn graph. A 'light' graph is constructed and used as a reference to map and store reads efficiently, the same structure is also used for quality scores compression. I will present the algorithm and comparative results.
 Plus d'infos  


2015-04-16Fuzzy Multilevel Graph Embedding for Recognition, Indexing and Retrieval of Graphic Document Images
11:00-12:00
178
As warm-up, I will show two videos of approx. 2 min each. First one on the document scanners and second one on the SmartDoc competition that we are organizing for ICDAR2015.

For the scientific part, in first part of the talk I will focus on presenting a new method of explicit graph embedding. The proposed graph embedding method exploits multilevel analysis of graph for extracting graph level information, structural level information and elementary level information
from graphs. It embeds this information into a numeric feature vector. The method employs fuzzy overlapping trapezoidal intervals for addressing the noise sensitivity of graph representations and for minimizing the information loss while mapping from continuous graph space to discrete vector space. The method has unsupervised learning abilities and is capable of automatically adapting its parameters to underlying graph dataset.

In the second part I will focus on presenting a framework for automatic indexing of graph repositories for graph retrieval and subgraph spotting. This framework exploits explicit graph embedding together with classification and clustering tools. It achieves the automatic indexing of a graph repository during its off-line learning phase, where its extracts the cliques of order 2 from graphs and embeds them into feature vectors by employing the aforementioned explicit graph embedding technique. It clusters the feature vectors into classes, learns a classifier and builds an index for the graph repository. During on-line spotting phase, it extracts the cliques of order 2 from query graph, embeds them into feature vectors and uses the index of the graph repository to retrieve the graphs from repository. The framework does not require a labeled learning set and can be easily deployed to a range of application domains, offering ease of query by example (QBE) and granularity of focused retrieval.
 Plus d'infos  


2015-04-09Reconstruction of Metabolic Models, with applications to Biofuel and Biomining
11:00-12:00
salle 178, LaBRI
Genome-scale metabolic models are a powerful tool to study the inner workings of biological systems and to guide industrial applications. The advent of cheap sequencing has brought the opportunity to create metabolic maps of biotechnologically interesting organisms. I'll present several methods, both published and under development, that leverage this experimental data to reconstruct and validate metabolic models. I'll also show some of the models we have built using our methods, and their applications to biofuel production and biomining, both high priorities for Chilean biotechnology.
 Plus d'infos  


2015-04-02xHeinz: discovering conserved and active network modules across species
11:00-12:00
salle 178, LaBRI
On one hand, biological network mining is an essential approach for the inspection of differential analysis expression profiles. On the other hand, for experimental purposes, molecular profiles measurements are often performed on model organisms and are not immediately transferable to other species, such as human.

In this presentation, we are going to introduce a new mathematical model that enables us to discover subnetworks of high differential activity across two species. Our model uses a flexible approach to conservation, which is the key to our results. We introduce a new graph-theoretical problem that we call Maximum-Weight Cross-Connected Subgraph and show that it is an APX-hard problem. Finally, we will present our Mixed-Integer Programming solver implementation for our model: xHeinz.
 Plus d'infos  


2015-03-26A hierarchical model with latent variables to represent high-dimensional and highly correlated data ; application to the modeling of genotypic data to help detect genetic risk factors of diseases
11:00-12:00
178
The first part of the talk will be dedicated to the general presentation of the FLTM model. We have designed a novel class of probabilistic graphical models, called forest of latent tree models (FLTM). We have developed a scalable algorithm able to construct such FLTMs. The construction is a bottom up process based on hierarchical clustering. The (correlated) variables grouped in the same cluster are subsumed by a latent variable. This latent variable is created through the learning of a simplistic Bayesian network. Our construction algorithm relaxes the constraints imposed by alternative proposals, based on Bayesian networks, such as binarity of the tree topology or binarity of the cardinality of the latent variables. However our algorithm can still be run on a laptop (less than one day for 5 000 observations each described by 100 000 variables). Besides, as regards the modeling of genetic data at the genome scale, our construction algorithm allows long-range dependences. Thus our algorithm is more faithful to the underlying biological reality.

The second part of the talk will briefly focus on the construction algorithm. We have studied the impact of the choice of the clustering method plugged in the construction algorithm. So far, we have used two versions of the CAST algorithm, DBSCAN and the Louvain method. We are currently writing a novel version of our algorithm, to decrease the time and space complexities.

The first motivation for the design of the FLTM model was to implement dimension reduction, thanks to the multi-scale approach, in further downstream analyses. Visualization, multidimensional partitioning and data mining are examples of such downstream analyses. Besides visualization of the complex dependences intrinsic to genetic data (the so-called linkage disequilibrium), another motivation was to implement multilocus genome-wide associations studies (GWASs). The third part of the talk will focus on the use of the FLTM model to further implement GWAs, when applied to genetic data. The purpose of GWASs is to identify dependences - or associations - between genotypic data and a studied disease. GWASs rely on genetic markers. Single Nucleotide Polymorphim (SNP) is one of the most popular classes of genetic markers. In standard (single-SNP) GWASs, linkage disequilibrium is not fully exploited. In contrast, the FLTM model allows to implement a multilocus GWAS where latent variables (that is groups of correlated SNPs) are tested against the disease. We will first present a validation study about the use of FLTMs in GWASs, based on both simulated and real data. First results on real data will then be shown.

On-going works related to GWASs concern the integration of multiple heterogeneous sources of data (literature, databases available on the Internet, experimental data (omics)). The objective is to increase the power of the GWAS. For a more generic use, we are now developing a visualization tool based on Tulip software. In the specific case of the modeling of genetic data, the end-user will be able to navigate through the FLTM, zoom in narrower regions of the genome and have feedback about some downstream analysis (e.g. a GWAS) thanks to various layers of annotations. Finally, we are also in the process of parallelizing the code of the construction algorithm.

As regards genetic analysis, our collaborators are the INSERM at Nantes and the INRA at Angers.

Much effort is devoted to the use of the FLTMs for data mining and visual exploration of genetic data in the context of the ANR project SAMOGWAS (Numerical Models). However, more generically, the FLTM model fits the purposes of compression of spatially highly correlated data (e.g. image processing) and of abstraction.
 Plus d'infos  


2015-03-19Enhanced Template Update for Keystroke Dynamics: Preliminary Results
11:00-12:00
178
Keystroke Dynamics is a biometric modality which attempts to recognize users by their typing rhythm. This is usually done by computing features over the pressing and releasing instants of each typed key on the keyboard. Most of current literature considers this biometric technology in a static context. In such a context, a model of the user is generated and it is not updated over time. However, it has been reported that the typing behaviour changes over time, suggesting that the user model (template) should be continuously updated. There are some work on the literature studying the usage of adaptive biometrics/template update methods on keystroke dynamics. Nevertheless, they mainly consider only positively (legitimate) classified examples for adaptation/update. A new proposed approach, called Enhanced Template Update, also involves the usage of information from negatively classified examples (impostor). The presentation will show a brief overview of the keystroke dynamics field along with some basic adaptive biometric methods. Afterwards, Enhanced Template Update will be introduced and preliminary results will be discussed.

 Plus d'infos  


2015-02-19XEML-Lab, un outil graphique pour la conception d'expériences et la gestion de métadonnées environnementales et expérimentales
11:00-12:00
salle 75, LaBRI
Exploiter le potentiel énorme du nombre toujours croissant d'études en Métabolomique nécessite une annotation structurée des métadonnées associées à l'expérience afin de permettre une intégration de données pertinente et d'élaborer une analyse d'exploration de données. Nous avons mis au point un outil logiciel pour la capture de métadonnées, XEML-Lab Designer permettant la conception intuitive d'expériences. XEML-Lab a été à l'origine conçu pour la capture de métadonnées environnementales afin d'inviter les biologistes à partager leurs données environnementales. Pour améliorer la visibilité et l'utilisation par la communauté, XEML-Lab a été développé pour fonctionner sur toutes les plates-formes (Windows, Linux et Mac). Beaucoup de fonctionnalités nouvelles ou améliorées ont été intégrées dans le nouveau XEML-Lab, y compris l'importation de données environnementales à partir d'un fichier tabulaire (csv, tsv), le tracé de chaque variable quantitative pendant le temps de l'expérience ou encore l'exportation de l'expérience au format ISA-tab pour déposer sur Metabolights. Pour décrire et capturer les métadonnées, il est maintenant possible d'utiliser différents types d'ontologies, environnementales, structurelles ou des stades de développement (XEO, Envo, EO, Xeo_positioning, PO_developmental et PO_Structure). Afin d'avoir une meilleure appréhension de l'expérience, ces données environnementales sont corrélées avec les données expérimentales stockées dans les bases de données dédiées. La connexion avec la base de données PLATO (INRA) a ainsi été réalisée. tout cela permet de décrire plus finement le design expérimental, les conditions et ainsi d'expliquer l'apparition d'un phénotype ou d'une réponse à un traitement donné.
 Plus d'infos  


2015-02-05Genome evolution and unexpected bacterial content in isolates of the model fungal pathogen Magnaporthe
11:00-12:00
salle 178, LaBRI
We have analyzed and compared a dataset of ten closely related genomes of the Magnaporthe oryzae/grisea species complex, a model pathogen fungus infecting rice and other Poaceaes.
Nine new genomes were sequenced, assembled and compared to the reference public genome of the 7015 isolate. De novo structural annotation was carried out to predict genes and to annotate Transposable Elements (TEs) in these nine genomes. Four of them exhibited large supplementary genomic regions potentially issued from an unknown bacterial strain of the Burkholderia genus. We used a parametric method based on genomic signature to accurately quantify, characterize and filter these regions in all the affected genome scaffolds. Detection of potential horizontal transfers was also performed using dedicated genome signatures.
We then constructed gene families to determine the core and pan-genomes of the 10 M. oryzae/grisae isolates. Evolutionary history of the predicted ortholog families was investigated using a recent method named Bayesian Concordance Analysis. We built a reference genealogy of these 10 isolates and showed a bifurcating evolution outside the lineage of isolates pathogenic to rice, and reticulate evolution within this lineage. The low level of nucleotidic diversity within the “rice” lineage suggested its recent divergence. The reticulate evolution observed in this lineage was consistent with a weak signal of recombination, but might be mainly due to incomplete lineage sorting. We also showed that a small but non-negligible proportion of the 7015 genome has a non-rice origin.
 Plus d'infos  


2015-01-08 Une approche de visualisation analytique pour comparer les modèles de propagation dans les réseaux sociaux
11:00-12:00
178
Les modèles de propagation d'informations, d'influence et d'actions dans les réseaux sociaux sont nombreux et diversifiés rendant le choix de celui approprié à une situation donnée potentiellement difficile. La sélection d'un modèle pertinent pour une situation exige de pouvoir les comparer. Cette comparaison n'est possible qu'au prix d'une traduction des modèles dans un formalisme commun et indépendant de ceux-ci. Nous proposons l'utilisation de la réécriture de graphes afin d'exprimer les mécanismes de propagation sous la forme d'un ensemble de règles de transformation locales appliquées selon une stratégie donnée. Cette démarche prend tout son sens lorsque les modèles ainsi traduits sont étudiés et simulés à partir d'une plate-forme de visualisation analytique dédiée à la réécriture de graphe. Après avoir décrit les modèles et effectué différentes simulations, nous exhibons comment la plate-forme permet d'interagir avec ces formalismes, et comparer interactivement les traces d'exécution de chaque modèle grâce à diverses mesures soulignant leurs différences.
 Plus d'infos  


2014-12-18Genome-wide detection of sRNA targets with rNAV
11:00-12:00
178
The central dogma in molecular biology postulated that ’DNA
makes RNA makes protein’, however this dogma has been recently
extended to integrate new biological activities involving small non-
coding RNAs, called sRNAs. Accordingly, an increasing attention
has been given to these molecules over the last decade and related
experimental works have shown a wide range of functional activ-
ities for these molecules. In this paper, we present rNAV (for rna
NAVigator), a new tool for the visual exploration and analysis of
sRNA-mediated regulatory networks. rNAV has been designed to
help bioinformaticians and biologists to identify, from list of thou-
sands of predictions, pertinent and reasonable sRNAs and target
candidates for carrying out experimental validations. We propose
a list of dedicated algorithms and interaction tools that facilitate
the exploration of such networks. These algorithms can be gath-
ered into pipelines which can then be saved and reuse over several
sessions. To support exploration awareness, rNAV also provides an
exploration tree view that allows to navigate through the steps of the
analysis but also to select the -sub-networks to visualize and com-
pare. These comparisons are facilitated by the integration of mul-
tiple and fully linked views. We demonstrate the usefulness of our
approach by a case study on Escherichia coli bacteria performed by
domain experts.
 Plus d'infos  


2014-12-04Predicting Bikeshare System Usage
11:00-12:00
178
Bike sharing systems are present in several modern
cities. They provide citizens with an alternative and ecological
mode of transportation, allowing them to avoid the use of
personal car and all the problems associated with it in big
cities (i.e., traffic jam, roads reserved for public transport, . . . ).
However, they also suffer from other problems due to their
success: some stations can be full or empty (i.e., impossibility
to drop off or take a bike). Thus, to predict the use of such
system can be interesting for the user in order to help him/her
to plan his/her use of the system and to reduce the probability of
suffering of the previously presented issues. This paper presents
an analysis of various regressors from the state of the art on
an existing public dataset acquired during two years in order to
predict the global use of a bike sharing system. The prediction
is done for the next twenty-four hours at a frequency of one
hour. Results show that even if most regressors are sensitive to
over-fitting, the best performing one clearly beats the baselines.
 Plus d'infos  


2014-11-18An efficient method for correcting long PacBio reads
14:00-15:00
AMPHI LaBRI
PacBio Single Molecule, Real Time sequencing is a third generation sequencing technique producing long reads with comparatively lower throughput and higher error rate. Errors include numerous indels and complicate downstream analysis like mapping or de novo assembly. A hybrid strategy that takes advantage of the high accuracy of Second Generation short reads has been proposed for correcting long reads. Mapping of short reads on long reads provides sufficient coverage to eliminate up to 99% of errors, however at the expense of prohibitive running times and considerable amounts of disk and memory space.
We present LoRDEC, a hybrid error correction method that builds a succinct de Bruijn graph representing the short reads, and seeks a corrective sequence for each erroneous region in the long reads by traversing chosen paths in the graph. In comparisons, LoRDEC is at least six times faster and requires at least 93% less memory or disk space than available tools, while achieving comparable accuracy.
LoRDEC software is available on the ATGC platform (http://www.atgc-montpellier.fr/lordec).

References
[1] L. Salmela and E. Rivals. LoRDEC: accurate and efficient long read error correction. Bioinformatics,
August 26 2014. On line doi:10.1093/bioinformatics/btu538.
 Plus d'infos  


2014-11-13Semantic Zooming and Navigation in Metabolic Networks
11:00-12:00
salle 178, LaBRI
The complexity of genome-scale metabolic models makes them quite difficult for human users to read, since they contain thousands of reactions that must be included for accurate computer simulation. For example, the metabolic network of the bacterium E. coli contains 2 168 reactions, the yeast 7 metabolic network model of S. cerevisiae includes 2 352 reactions, and recon 2, a global human metabolism reconstruction, has 7 440 reactions. Interestingly, hidden similarities between groups of reactions can be discovered, and generalized to reveal higher-level patterns.

The web-based navigation system Mimoza allows a human expert to explore metabolic network models in a semantically zoomable manner: The most general view represents the compartments of the model; the next view shows the generalized versions of reactions and metabolites in each compartment; and the most detailed view represents the initial network with the generalization-based layout (where similar metabolites and reactions are placed next to each other). It allows a human expert to grasp the general structure of the network and analyze it in a top-down manner.
 Plus d'infos  


2014-10-16A Gondwanan Imprint on Global Diversity and Domestication of Wine and Cider Yeast Saccharomyces uvarum
11:00-12:30
salle 178
Présentation de l'article récemment publié dans Nature Communications.
Il sera question de génomique des populations de Saccharomyces uvarum,
avec au menu : levures, biodiversité, domestication, génomique, SNP,
introgression, génétique des populations et, bien sur, Gondwana ...
 Plus d'infos  


2014-03-20Recombinaisons modulaires: couper-coller chez les bactériophages
10:00-11:00
salle 178, bat A30
Les virus qui infectent les bactéries, appelés bactériophages, ont des génomes très compacts qui codent pour un nombre restreint de fonctions biologiques. Les bactériophages qui infectent une même souche de bactéries utilisent régulièrement une forme de réarrangement de génomes, appelée recombinaison modulaire, qui consiste à échanger un module qui code pour une fonction contre un autre qui remplit le même rôle, tout en n'ayant aucune similarité détectable. Un peu comme on pourrait remplacer un groupe électrogène à essence par une éolienne.
Dans cet exposé, nous allons discuter des propriétés combinatoires des opérations de recombinaisons modulaires et des problèmes de reconstruction des bactériophages ancestraux. Nous allons également montrer que, même en l'absence de similarité, il est possible d'aligner des génomes de bactériophages lorsqu'ils sont co-linéaires.
 Plus d'infos  


2014-03-20Pancakes and the “Sex Ratio”: a Story of Genome Rearrangements
11:00-12:00
salle 178, bat A30
Towards the beginning of the 20th century, Sturdevant discovered that the genes of Drosophila are organized linearly on the chromosomes. Later, through hybridization experiments on polytene chromosomes, Sturdevant and Dobzhanski noticed that a substrand of the fruit fly DNA can be inverted; in some strains of fruit fly the sequence of genes on the chromosome appears in reverse order. Further, he showed that these inversions were linked to the phenotype of those individuals that possessed it: male flies with a particular inversion had few or no male offspring. So as early as 1936, evolutionary histories between species of fruit fly were being inferred based on inversion histories. It is now known that rearrangements can both be fixed in a population, serving to insulate cross species fertilization, and are associated with a multitude of diseases. It was not for another half a century that appropriate questions were asked about the inference of rearrangement histories. In this talk we introduce concepts and models for understanding rearrangement histories, and present the most important algorithmic and modeling developments of the last twenty years.
 Plus d'infos  


2014-03-13GosperMap: Using a Gosper Curve for Laying Out Hierarchical Data
11:00-12:00
salle 178, bat A30
The emergence of very large hierarchies that result from the increase in available data raises many problems of visualization and navigation. On data sets of such scale, classical graph drawing methods do not take advantage of certain human cognitive skills such as shape recognition. These cognitive skills could make it easier to remember the global structure of the data. In this paper, we propose a method that is based on the use of nested irregular shapes. We name it GosperMap as we rely on the use of a Gosper Curve to generate these shapes. By employing human perception mechanisms that were developed by handling, for example, cartographic maps, this technique facilitates the visualization and navigation of a hierarchy. An algorithm has been designed to preserve region containment according to the hierarchy and to set the leaves' sizes proportionally to a property, in such a way that the size of nonleaf regions corresponds to the sum of their children's sizes. Moreover, the input ordering of the hierarchy's nodes is preserved, i.e., the areas that represent two consecutive children of a node in the hierarchy are adjacent to one another. This property is especially useful because it guarantees some stability in our algorithm. We illustrate our technique by providing visualization examples of the repartition of tax money in the US over time. Furthermore, we validate the use of the GosperMap in a professional documentation context and show the stability and ease of memorization for this type of map.
 Plus d'infos  


2013-10-03Visualisations novatrices pour faciliter la compréhension de réseaux et de logiciels complexes
11:00-12:00
178
La visualisation d'information peut faciliter la découverte de secrets enfouis dans les données. Il existe toutefois une grande variété de données que l'on cherche à comprendre sous diverses perspectives. Les techniques de visualisation actuelles sont efficaces dans certains contextes spécifiques et comportent des limitations. Dans le but d’explorer de nouvelles options de visualisations, nous avons d'abord classifié les travaux antérieurs avec des taxonomies. Des prototypes ont par la suite été conçus pour faciliter des tâches de compréhension de réseaux. Les contributions de cette thèse couvrent différents aspects de la visualisation de réseaux. D'abord, le premier chapitre se concentre sur une visualisation hybride de réseaux statiques comportant des hiérarchies. Le prototype décrit dans le deuxième chapitre combine aussi des représentations visuelles, mais peut en plus modéliser des graphes dynamiques. Enfin, le troisième chapitre présente une nouvelle méthode visuelle appliquée afin de tracer l'évolution de structures de conception dans des logiciels.


Mots-clés : visualisation d'information, réseau, taxonomie, visualisation hybride, visualisation de logiciels
 Plus d'infos  


2013-09-12AG de rentrée
11:00-13:00
amphi
AG de rentrée pour la nouvelle année
 Plus d'infos  


2013-07-18Numerical Linear Algebra in a Database System for Big Data Analytic s
11:00-12:00
178
Linear algebra is behind most scientific analytic computations, including numerical methods, statistics,
physics and data mining. On the other hand, database systems provide extensive features to manage and
query data, but not to analyze it. The integration of linear algebra algorithms into a database system is
difficult due to the relational model discrete set foundation, which in consequence hinders efficient array
processing. In this talk, we discuss our progress towards solving two prominent linear algebra problems
on large data sets: singular value decomposition and least squares regression. We present a common
matrix foundation to summarize large data sets with an outer product and exploiting such summarization
we discuss how to efficiently solve linear algebra problems with iterative methods.
 Plus d'infos  


2013-07-11One graph, multiple drawings
11:00-12:00
178
Being able to produce a wide variety of layouts for a same graphs may prove useful when users have no preferred visual encoding for their data.
The first contribution of this paper is a enhanced force-directed layout capable of producing different layouts of a same graph. We turn a well known force-directed algorithm (GEM) into a highly parametrizable layout and control it from a genetic algorithm framework. The genetic algorithm allows to efficiently explore the parameter space of this highly parametrisable layout.
The second contribution of this paper is a similarity metric used as a fitness function for the genetic algorithm. Its main features are its computational cost of $O(n^2)$ (with $n$ the number of vertices) and its insensitivity to planar homotheties.
 Plus d'infos  


2013-06-27ServOMap, un système d'alignement à large échelle d'ontologies
11:00-12:00
178
L'objectif du séminaire, est de faire dans un premier temps, un bref panorama des thèmes de recherche traités au sein de l'équipe l'Equipe de Recherche en Informatique Appliquée à la Santé (ERIAS) et l'illustrerons par quelques projets de recherche.
Dans un second temps, nous ferons un focus sur ServOMap, un système d'alignement à large échelle d'ontologies, et plus largement de systèmes d'organisation de connaissances, que développe l'ERIAS.
Plusieurs travaux traitent de la question d'alignement, notamment pour les besoins d'intégration, mais peu de systèmes arrivent à traiter des ontologies contenant des dizaines voire des centaines de millier d'entités, comme cela peut être le cas dans le domaine biomédical. ServOMap repose sur un serveur d'ontologies (ServO) et est basé sur des techniques de RI pour la recherche de similarité entre entités. Nous présenterons les résultats obtenus lors de l'édition 2012 de la campagne internationale Ontology Alignment Evaluation Initiative (OAEI) pour le track qui concerne les larges ressources biomédicales.
Au cours de la présentation, nous mettrons en évidence, où c'est nécessaire, nos besoins en visualisation de données.
 Plus d'infos  


2013-04-25Le Cloud Privé Mabiovis
11:00-12:00
178
Depuis huit ans l'équipe gère un cluster de calcul dans la salle 006 qui est aujourd'hui configuré avec deux services colocalisés : un traitement par lots classique, et un cloud privé. Ce dernier permet le déploiement à volonté d'images de machines et un partage de données, exactement comme Amazon Elastic Cloud, mais en local dans notre bâtiment. Je présenterai les services proposés par notre cloud privé ainsi que quelques exemples de l'utilisation que nous en faisons.
 Plus d'infos  


2013-04-18Contributions à la gestion et à la fouille de données spatiotemporelles floues
11:00-12:30
178
Ce travail se positionne dans le cadre de la manipulation de données spatiotemporelles réelles en tenant compte de leur imperfection et plus particulièrement de leur imprécision. La démarche présentée s'inscrit dans la volonté d'aller vers une meilleure gestion de celles-ci tant pour leur représentation que pour leur analyse et leur visualisation. Dans ce contexte, nos contributions portent d'une part sur la gestion des données floues tant au niveau conception et construction des systèmes d'information géographique que de l'interrogation des données, et, d'autre part, sur l'exploration, possiblement visuelle, des bases ainsi construites. Nos méthodes se basent notamment sur la définition d'indices temporels flous, de graphes, de rangs, de coloriage guidé par les données, etc. La démarche sera illustrée autour d'applications sur des données issues de l'archéologie préventive et sur des cas d'études prospectifs en agronomie et en urbanisme.
 Plus d'infos  


2013-04-11Static Analysis for Optimizing the Update of Large Temporal XML
11:00-12:30
178
The last decade has witnessed a rapid expansion of XML as a format for representing and exchanging data through the web. In order to follow this evolution, many languages have been proposed to query, update or transform XML documents. At the same time, a range set of systems allowing to store and process XML documents have been developed. Among these systems, main‐memory engines are lightweight systems that are the favored choice for applications that do not require complex functionalities of traditional DBMS such as transaction management and secondary storage indexes. These engines require to loading the documents to be processed entirely into main‐memory. Consequently, they suffer from space limitations and are not able to process quite large documents. XML projection is a prominent technique that has been proposed for overcoming the limitations of main‐memory engines in the context of querying. It consists in pruning out, at loading time, the parts of the queried document that are not required to perform the query. As in general queries are selective, the resulting document is likely to be small and fit within main‐memory. The projection technique developed for queries cannot be directly applied for updates. Obviously, updating a projection of a document t is not equivalent to updating the document t itself since the pruned out sub‐trees will be missing. Using projection in the context of updates requires thus a mechanism for propagating, on the original documents, the effects of the updates performed over the projected documents.

This talk consists in two parts. The first part focuses on presenting the projection‐based technique we have developed for optimizing the update of XML documents. This technique relies on a static analysis of the update expression and exploits the schema information. The conducted experiments testify the effectiveness of the method wrt space consumption and execution time as well.

The second part of my talk addresses the issue of efficiently building and maintaining timestamped XML documents encoding the evolution of XML documents. I will present two methods. For the first one, called general method, no restriction is made on the evolution of the XML documents whereas for the second one, called updatebased method, changes are assumed to be specified by updates. For both methods, the issue is to enable processing very large documents, to use existing engines and to comply to XQuery Update Facility. The two methods are compared in terms of space‐efficiency. The update‐based method produces time‐stamped XML documents that are more satisfactory wrt space‐efficiency than the general method.
 Plus d'infos  


2013-04-04Organisation des gènes le long des génomes : programmation linéaire et statistiques
11:00-12:30
178
Je présenterai dans un premier temps mes travaux en génomique comparative. Pour illustrer la puissance de la programmation linéaire à variables booléennes, je parlerai du calcul du nombre d'adjacences au travers de trois modèles de génomes. Ces trois modèles sont de plus en plus complexes, mais surtout de plus en plus biologiquement pertinents : (i) aucune duplication de gène (identité de séquence vs permutation), (ii) duplications de gènes acceptées (maximisation d'un couplage), (iii) familles de gènes non-prédéfinies (maximisation à partir d'un graphe bipartite).

Dans un deuxième temps, je parlerai de mes études portant sur l'organisation des gènes co-fonctionnels chez le génome humain. À l'aide de statistiques, nous évaluerons la concentration ou la dispersion de groupes de gènes. Ces groupes sont par exemple des ensemble de gènes codant pour les protéines intervenant dans une même voie de signalisation ou codant pour les mêmes ARNs de transfert. Nous observerons si ces groupes sont concentrés le long des chromosomes, dans un faible nombre de chromosomes et/ou dans l'espace à 3 dimensions.
 Plus d'infos  


2013-01-31calcul distribué de requêtes type "Skyline"
11:00-12:30
178
Une requête "skyline" consiste à calculer les "meilleurs"
enregistrements dans un ensemble. Par "meilleur" on entend ceux pour qui
il n'existe pas un autre élément meilleur qu'eux. Optimiser ce calcul
quand les données sont distribuées revient essentiellement à bien ordonnancer
les calculs locaux afin de réduire au maximum la quantité de données à transférer
(c'est ce qui prend le plus de temps). Quelques solutions seront décrites.
 Plus d'infos  


2013-01-17Mesurer l’intrication sémantique dans une collection de documents
11:00-12:30
salle 3 Bâtiment A29
Avec l’explosion des ressources en ligne, l’exploration efficace de collections de documents est une tâche quotidienne pour bon nombre de professions,
mais paradoxalement reste un enjeu pour la recherche. Nous proposons trois outils pour aider à percevoir le contenu sémantique d’un ensemble de
documents: un réseau pondéré d’interaction des termes associés au jeu, une mesure d’intensité et une mesure d’homogénéité d’intrication sémantique reflétant les caractéristiques de partage des termes par les différents items de la collection. De plus, ces mesures sont utilisées pour catégoriser les collections.
 Plus d'infos  


2012-12-13Algorithmic and Compact Data Structures for NGR and NGS
11:00-12:00
178
In this talk, we will address two different topics. In a first part,
we will present some algorithmic results on the "Next Generation
Radiotherapies". Radiation therapy is one of the commonly used cancer
therapies. The radiation treatment poses a tuning problem: the
radiation needs to be effective enough to destroy the tumor, but it
should maintain the functionality of the organs close to the tumor
(organs at risk). Towards this goal, the design of radiation treatment
has to be customized for each patient. We will mainly focus on
Intensity Modulated Radiation Therapy using Multi-Leaf Collimator and
on Brachytherapy and give some algorithmic results we recently
achieved.

In a second part, we will present the succinct data structure of
wavelet tree and its usefulness for "Next Generation Sequencing".
Wavelet tree is a succinct data structure used to efficiently store
strings over an alphabet sigma in compressed space that support
Access(x), Rank(y,x) and Select(y,x) operations in O(log(|sigma|))
time. Access(x) returns the character at position x while Rank(y,x)
returns the number of occurences of character y before position x.
Finally, Select(y,x) returns the position of the xth occurence of
character y. After presenting the basics of wavelet trees, we will
show how it can be used to efficiently index reads for assembly
purpose.
 Plus d'infos  


2012-12-06 LCA Skeleton Tree in Linear Time
11:00-12:30
178
Fischer and Huson introduced in 2010 the notion of LCA skeleton tree: the restriction of a tree to a given subset of the nodes, and they gave an algorithm for computing the LCA skeleton tree of a subset of $m$ nodes in a tree with $n$ nodes in $O(mlog{n}/loglog{n})$ time after $O(n)$ time preprocessing, based on the fact that the LCA of any two nodes in a tree with $n$ nodes can be determined in $O(1)$ time after $O(n)$ time preprocessing. In this talk, we present a simple algorithm for computing the LCA skeleton tree of a subset of $m$ nodes in a tree with $n$ nodes in $O(m)$ time, after $O(n)$ time preprocessing. The LCA skeleton tree of a taxonomic tree has applications in the taxonomic assignment of sequence reads in metagenomics.
 Plus d'infos  


2012-11-19Efficient data structures for large-scale genome sequencing data.
14:00-15:30
salle de réunion Sud, CGFB
To assemble and/or detect variants in large-scale genomics data, an algorithmic
ingredient of choice is the de Bruijn graph. On large datasets, analyzing
such graph requires a significant amount of system memory.
This talk deals with ultra-low memory representation of de Bruijn graphs.
We propose a new encoding, which occupies an order of magnitude less space
than current representations. The encoding is based on a Bloom filter, with
an additional structure to remove critical false positives. An assembly
software implementing this structure, Minia, performed a complete de novo
assembly of human genome short reads using 5.7 Gb of memory in 23 hours.
The article (and in the near future, the public source code) can be found
on the webpage of Minia: http://minia.genouest.org/
 Plus d'infos  


2012-11-08Assemblage du génome de l'agent de la peste noire.
11:00-12:00
178
La peste noire est une pandémie de peste bubonique qui a ravagé l'Europe au XIVème siècle. L'étiologie de cette pandémie a fait l'objet d'un vif débat, sans doute clos par le récent travail de Bos et al. (Nature 478, 506-510), qui ont séquencé le génome de l'agent de la peste noire, et ont montré qu'il s'agissait dune bactérie de la famille Yersinia pestis, ancêtre de plusieurs souches actuelles de Yersinia pestis. Ce travail de séquencage et assemblage d'un paléogénome a produit environ 2000 contigs de 500bp et plus, dont l'analyse suggère une forte conservation de séquence dans les souches descendantes de l'agent de la peste noire.
Le travail que je vais présenter consiste à corriger et assembler ces contigs en un unique échafaudage (scaffold), ouvrant la porte à des analyses à une plus grande échelle, montrant par exemple un grand nombre de réarrangements génomiques.
Les techniques utilisées des techniques de paléogénomique et de génomique évolutionaires, et tirent parti de la caractéristique unique de jeu de données, à savoir un génome partiellement assemblé mais dont on dispose de descendants.

Travail en collaboration avec Ashok Rajara,man (Simon Fraser University) et Eric Tannier (INRIA-Lyon)
 Plus d'infos  


2012-10-25Formation Cloud
10:30-17:30
178
Formation niveau II Partie 1
 Plus d'infos  


2012-10-18Formation Cloud
10:30-17:30
178
Formation niveau I
 Plus d'infos  


2012-10-11Formation Cloud
09:30-16:00
178
Formation niveau II Partie 2
 Plus d'infos  


2012-10-04PETITE ECOLE : Acorn: A grid computing system for constraint based modeling and visualization of the genome scale metabolic reaction networks via a web interface
11:00-12:00
178
Sroka J, Bieniasz-Krzywiec L, Gwóźdź S, Leniowski D, Lącki J, Markowski M, Avignone-Rossa C, Bushell ME, McFadden J, Kierzek AM.
Source

Institute of Informatics University of Warsaw, Poland.

Abstract
BACKGROUND:
Constraint-based approaches facilitate the prediction of cellular metabolic capabilities, based, in turn on predictions of the repertoire of enzymes encoded in the genome. Recently, genome annotations have been used to reconstruct genome scale metabolic reaction networks for numerous species, including Homo sapiens, which allow simulations that provide valuable insights into topics, including predictions of gene essentiality of pathogens, interpretation of genetic polymorphism in metabolic disease syndromes and suggestions for novel approaches to microbial metabolic engineering. These constraint-based simulations are being integrated with the functional genomics portals, an activity that requires efficient implementation of the constraint-based simulations in the web-based environment.
RESULTS:
Here, we present Acorn, an open source (GNU GPL) grid computing system for constraint-based simulations of genome scale metabolic reaction networks within an interactive web environment. The grid-based architecture allows efficient execution of computationally intensive, iterative protocols such as Flux Variability Analysis, which can be readily scaled up as the numbers of models (and users) increase. The web interface uses AJAX, which facilitates efficient model browsing and other search functions, and intuitive implementation of appropriate simulation conditions. Research groups can install Acorn locally and create user accounts. Users can also import models in the familiar SBML format and link reaction formulas to major functional genomics portals of choice. Selected models and simulation results can be shared between different users and made publically available. Users can construct pathway map layouts and import them into the server using a desktop editor integrated within the system. Pathway maps are then used to visualise numerical results within the web environment. To illustrate these features we have deployed Acorn and created a web server allowing constraint based simulations of the genome scale metabolic reaction networks of E. coli, S. cerevisiae and M. tuberculosis.
CONCLUSIONS:
Acorn is a free software package, which can be installed by research groups to create a web based environment for computer simulations of genome scale metabolic reaction networks. It facilitates shared access to models and creation of publicly available constraint based modelling resources.

PMID:
21609434
 Plus d'infos  


2012-09-20Petite ecole : Unraveling Protein Networks with Power Graph Analysis
11:00-12:00
178
Royer L, Reimann M, Andreopoulos B, Schroeder M (2008) Unraveling Protein Networks with Power Graph Analysis. PLoS Comput Biol 4(7): e1000108.

Networks play a crucial role in computational biology, yet their analysis and representation is still an open problem. Power
Graph Analysis is a lossless transformation of biological networks into a compact, less redundant representation, exploiting
the abundance of cliques and bicliques as elementary topological motifs. We demonstrate with five examples the
advantages of Power Graph Analysis. Investigating protein-protein interaction networks, we show how the catalytic
subunits of the casein kinase II complex are distinguishable from the regulatory subunits, how interaction profiles and
sequence phylogeny of SH3 domains correlate, and how false positive interactions among high-throughput interactions are
spotted. Additionally, we demonstrate the generality of Power Graph Analysis by applying it to two other types of networks.
We show how power graphs induce a clustering of both transcription factors and target genes in bipartite transcription
networks, and how the erosion of a phosphatase domain in type 22 non-receptor tyrosine phosphatases is detected. We
apply Power Graph Analysis to high-throughput protein interaction networks and show that up to 85% (56% on average) of
the information is redundant. Experimental networks are more compressible than rewired ones of same degree distribution,
indicating that experimental networks are rich in cliques and bicliques. Power Graphs are a novel representation of
networks, which reduces network complexity by explicitly representing re-occurring network motifs. Power Graphs
compress up to 85% of the edges in protein interaction networks and are applicable to all types of networks such as protein
interactions, regulatory networks, or homology networks.
PMID:18617988
 Plus d'infos  


2012-09-18Challenges in Computational Phylogenetics
10:00-11:00
salle de réunion Nord du CGFB à Bordeaux 2
Phylogenies, or evolutionary histories, play a central role in modern biology, illustrating the interrelationships between species, and also aiding the prediction of structural, physiological, and biochemical properties. The reconstruction of the underlying evolutionary history is difficult since the favored optimality criteria are NP-hard, and the space of possible answers is huge. We will discuss computational challenges in producing optimal phylogenetic trees and analyzing, visualizing, and comparing evolutionary histories.
 Plus d'infos  


2012-07-05Reproducibility challenges of data-driven biology
11:00-12:00
Salle de Conférences du Centre de Génomique Fonctionnelle Bordeaux (CGFB) , Université Bordeaux Segalen
Continuing evolution of DNA sequencing has transformed modern biology. Areas of life science research that were previously distant from each other in ideology, analysis practices, and toolkits such as microbial ecology and personalized medicine or conservation biology and cell and molecular biology have all embraced techniques that rely on next generation sequencing (NGS) instruments. These rapid and dramatic developments have enabled researchers to design and implement studies that were unthinkable just a few years ago. Yet the capacity to generate the data greatly outpaces our ability to analyze it. Existing sequencing technologies are much more mature and accessible than the methodologies for individual researchers to move, store, analyze, and present data in a fashion that is transparent and reproducible. Although this phenomenon is only natural -sequencing technologies advanced so rapidly that the analytical approaches simply have not had time to catch up - life sciences have reached a pivotal point where scalable and widely available analysis solutions are needed to truly achieve progress and move the field forward. Here we discuss currently pressing issues, discuss promising solutions, and venture into potential future developments.
 Plus d'infos  


2012-06-28Adapting comparative genomics to MapReduce
11:00-12:00
178
Comparative genomics seeks to understand the history and function of genomes by large-scale analysis of the relations between genomic elements, as contrasted with analyzing of those elements individually.We attempt to define some ground rules for successful conversion of global bioinformatic analyses to highly scalable MapReduce deployments. We illustrate our approach with two successful conversions of global comparative genomics analyses: systematic identification of gene fusion and fission events and consensus clustering for multi-genome protein families.
 Plus d'infos  


2012-04-26Des approches applicatives de fouille de données semi-supervisées ou non supervisées
11:00-12:30
178
Les approches semi-supervisée ou non supervisée de la fouille de données permettent de mettre l'utilisateur au centre du processus pour suivre ses desiderata (semi-supervisée) ou lui fournir, clefs en main, les éléments qu'il veut analyser (non supervisée), sans pour autant lui demander une forte implication (supervisée).

De l'analyse d'images cérébrales à l'exploration de traces d'exécution de processus en passant par l'homogénéisation des évaluations des cours d'eau d'Europe, la fouille de données s'impose dès que les volumes de données deviennent massifs, c'est à dire, au 21ème siècle : partout !

Seront présentées des approches de clustering d'images (avec et sans guidage sémantique), de pattern mining (par du Formal Concept Analysis de contextes doublement complexes : multi-valués et flous et par des patterns périodiques à intervalles variables) et de graph mining scalable (par des polynômes de matrice).
 Plus d'infos  


2012-04-19Recherche de motifs dans des réseaux d'interactions
11:00-12:00
050 (Amphi)
Un réseau d'interactions peut être représenté par un graphe coloré. Une grande partie de la littérature est dédiée à la recherche de motifs dans ces graphes, avec une topologie donnée sur le motif (chemin, arbre, graphe...). Récemment, Lacroix et al. ont établi un nouveau problème où le motif n'a pas de topologie mais est simplement un (multi) ensemble de couleurs. On cherche alors un sous-graphe connexe contenant ce motif. Je présenterai différents résultats algorithmiques (complexité paramétrée, approximation) sur ce problème.
 Plus d'infos  


2012-04-10De la cellule virtuelle au robot réel
15:00-16:00
74
Les robots modulaires développés ces dernières années sont de plus en plus complexes. Habituellement basés sur des blocs cubiques, ils embarquent une "mécatronique" extrêmement complexe afin de les rendre plus précis, plus efficaces et plus diversifiés. Plusieurs projets existent actuellement pour produire des robots complexes à partir de ces unités fonctionnelles. Beaucoup de travaux ont aussi été effectués afin de générer des robots modulaires virtuels. Parmi les tous premiers, les travaux de Karl Sims en 1994 sont souvent cités comme les bases du domaine. Ils consistent en un assemblage de blocs dans un environnement physique simulé. Ces robots virtuels sont souvent développés à l'aide de graphes (les "graphtals") ou de grammaires (les "L-Systèmes"). Depuis une dizaine d'année, un nouveau domaine fortement inspiré de la biologie tente d'utiliser des mécanismes inspirés de la prolifération cellulaire afin de développer des créatures artificielles ayant une morphologie et, dans quelques rares cas, une fonction définie par l'utilisateur du système. Cependant, aucune application à la robotique n'a été proposé pour le moment.
Notre approche consiste à utiliser un modèle de développement cellulaire afin de produire le plan et le comportement de robots modulaires. Une cellule virtuelle, contrôlée par un réseau de régulation génétique et un système hormonal, est capable de se diviser dans un environnement physique simulé afin de produire un organisme doté de cellule musculaire et "articulaire". Cet organisme est ensuite transformé en robot réel qui est capable d'effectuer les même action que son équivalent virtuel. Après un résumé des travaux du domaine de la robotique modulaire et des modèles de développement, ce séminaire présentera les modules robotique utilisés dans ces travaux ainsi que le modèle de développement produisant leurs plans. Les premiers résultats de cette approche seront aussi exposés.
 Plus d'infos  


2012-04-05Algorithmes de comparaison de génomes appliqués aux génomes bactériens
11:00-12:30
178
Grâce au grand nombre de génomes complets disponibles (avec une majorité venant de bactéries), les analyses comparatives de génomes deviennent indispensables pour leur annotation fonctionnelle, ainsi que pour la compréhension de leur structure et leur évolution. L'une des approches les plus utilisées pour comparer des génomes est l’alignement de leurs séquences d’ADN, appelé l'alignement de génomes complets, c.à.d. identifier les régions de similarité en s'affranchissant de toute annotation. Outre leurs grandes tailles qui rendent les solutions classiques basées sur la programmation dynamique inutilisables, l’alignement de génomes complets pose des difficultés supplémentaires dues à des mécanismes d’évolution particuliers comme la divergence, le réordonnancent des portions génomiques (réarrangements), ou l’acquisition de matériel génétique extérieur. En conséquence, les solutions pour l’alignement de génomes sont des heuristiques, dont la plus commune est la stratégie basée sur des ancres, qui comporte quatre phases. Malgré des améliorations significatives durant les dernières années, des outils performants pour cette approche ainsi que des méthodes pour l’estimation de la qualité des résultats qu’elle produit, en particulier sur les génomes bactériens, restent encore à développer.
Le travail que je vais présenter traite plusieurs problèmes liés à l’alignement de génomes complets dont: l’évaluation de la qualité des résultats produits par les outils d’alignement et l’amélioration de la stratégie basée sur des ancres. Premièrement, je vais analyser les alignements produits par deux des principaux outils existants sur des paires de génomes bactériens intra-espèces, et révéler leurs limitations. En partant de ces résultats, qui suggèrent un manque de sensibilité et de spécificité, je propose un nouvel outil pour l’alignement deux à deux de génomes complets colinéaires, YOC, qui implémente une version simplifiée de la stratégie basée sur des ancres, contenant seulement deux phases. Dans la première phase, YOC améliore la sensibilité en utilisant, pour la première fois dans cette stratégie, des similarités locales basées sur des graines espacées. Cette phase est suivie par une méthode de chainage adaptée aux similarités locales, un nouveau type de chaînage colinéaire, permettant des chevauchements proportionnels. En dernière partie de mon exposé, je présente les résultats obtenus avec YOC sur un ensemble de données composé de 694 couples de génomes bactériens intra-espèces. Ces résultats montrent que YOC améliore les cas divergents en détectant des similarités plus distantes et en évitant les régions mal alignées.

 Plus d'infos  


2012-03-29Modèles de réconciliation d’un arbre de gènes et d’un arbre d’espèces.
11:00-12:00
178
La réconciliation d’arbres phylogénétiques est un modèle mathématique pour l’évolution d’une famille de gènes selon l’évolution des espèces. Des modèles de parcimonie et probabilistes ont été proposés pour les scénarios d’évolution (1) avec Duplications et Pertes de gènes (modèle DP) et (2) avec Duplications, Pertes et Transferts de gènes (modèle DPT).

Nous avons développé un modèle DP qui a permis d’étudier la forme de l’espace combinatoire des réconciliations selon leur vraisemblance. Nos résultats montrent que la Réconciliation de Maximum de Parcimonie (MPR) est aussi celle de maximum de probabilité postérieure.

Calculer une MPR est un problème NP-complet pour les modèles DPT. Ceci est dû aux contraintes temporelles induites par les transferts de gènes. Une datation de l’arbre des espèces permet de résoudre ce problème en temps O(n^4 m), où n (resp. m) est la taille de l’arbre des gènes (resp. espèces). Nous avons développé un algorithme qui résout ce problème en temps O(m^2 n).

Pour les systèmes de coévolution d’une espèce parasite et d’une espèce hôte, notre algorithme calcule une MPR qui respecte les contraintes géographiques des deux espèces.

Nous avons obtenus des résultats chez les eucaryotes et procaryotes (gènes / espèces) et pour le système pollinisateur / ficus (parasite / hôte).
 Plus d'infos  


2012-01-26Etudiants M2
11:00-12:00
178 (LaBRI)
A venir
 Plus d'infos  


2012-01-26
11:00-12:30
178
 Plus d'infos  


2012-01-19
10:30-12:30
178 (LaBRI)
Attention deux exposés sont prévus : début à 10h30.

---
Exposé de Nicolas Goffard (10h30)
----
Titre : An Integrative knowledge-based approach to biomarker discovery
Résumé : The effectiveness of biomarker discovery can be advanced by
integrating statistical and knowledge-based approaches. Here a
functional mining will be presented as a precursor to biomarker
discovery and as an integrative tool to inform signature model
selection.

---
Exposé de Carito Guziolowski (11h30)
---
Titre : CONSTRAINT-BASED MODELING OF COMPLEX BIOLOGICAL NETWORKS
Orateur : CARITO GUZIOLOWSKI, TIGA Center - Medical Systems Biology Group,
Institute of Medical Informatics and Biometry, University Hospital Heidelberg,
Im Neuenheimer Feld 267, 69120 Heidelberg, Germany.
Résumé : An influence graph is an abstraction of a biological network that represents the interactions among the molecules of a system as discrete influences: signed and oriented edges. High-throughput measurements of the molecules in this system can also be discretized into natural up- or down-regulations. The Sign Consistency Model (Siegel et al., 2006) confronts an influence graph with the discretized measures of its molecules, by representing both information as a system of qualitative constraints. Thus, the combinatorial complexity of reasoning over a large-scale regulatory network can be approached by using efficient solvers over such a system of constraints. Currently, two computational frameworks, based on the Sign Consistency Model, exist: BioQuali (Guziolowski et al., 2009) and BioASP (Gebser et al., 2010). Both address and implement computationally complex queries confronting discrete regulatory networks with experimental data. In this talk I will present this modeling approach and its practical application to understand skin wound healing based on the automatical reconstruction of signaling pathways of the Hepatocyte Growth Factor (HGF).
References
Gebser, M., Ko andnig, A., Schaub, T., Thiele, S., and Veber, P. (2010). The bioasp library: Asp solutions for systems biology. In
Tools with Arificial Intelligence (ICTAI), 2010 22nd IEEE International Conference on, volume 1, pages 383-389.
Guziolowski, C., Bourde, A., Moreews, F., and Siegel, A. (2009). BioQuali Cytoscape plugin: analysing the global consistency of
regulatory networks. BMC Genomics, 10, 244.
Siegel, A., Radulescu, O., Le Borgne, M., Veber, P., Ouy, J., and Lagarrigue, S. (2006). Qualitative analysis of the relation between
DNA microarray data and behavioral models of regulation
 Plus d'infos  


2011-12-08PORGY : Un environement interactif et visuel pour la réécriture de graphes adapté aux systèmes complexes
11:00-12:30
178 (LaBRI)
Les systèmes de réécriture de graphes sont simples à expliquer :
ils réalisent des modifications sur un graphe en remplaçant des sous-graphes
sélectionnés au préalable sur la base de règles de transformations. Néanmoins,
la combinaison des règles pour leur application transforme l'étude de ces
systèmes en un problème complexe. A cause de cela, les experts de ces systèmes
se satisfont bien souvent de représentations textuelles ou alors de dessins
fait à la main pour représenter les règles de transformations. Au cours de cet
exposé, je présenterai PORGY qui est un environnement visuel et interactif
pour la réécriture de graphe. Cet environnement conçu avec des experts de
réécritures de graphes qui avaient envie d'un véritable système interactif et
visuel permet de construire, simuler et raisonner de façon visuelle et
interactive sur le système complexe à étudier.
 Plus d'infos  


2011-11-17Discovering molecular mechanisms from sRNA-seq data analyses: a new step in transcriptome exploration.
11:00-12:30
178
Les nouvelles techniques de séquençage ("Next Generation Sequencing" ou "NGS") permettent de caractériser le contenu en ARNs des cellules avec une précision et une amplitude jusque la inaccessibles. Dans cet expose nous verrons comment l'analyse bioinformatique de données "NGS" de type transcriptome peut également révéler des nouveaux mécanismes moléculaires opérant dans les cellules humaines a travers deux exemples issus de projets de séquençage de petits ARNs: un processus de clivage des ARN messagers suivi de "re-capping", identifie à partir de séquences obtenues sur une plateforme Illumina/Solexa, et un mécanisme de copie d'ARN à partir de transcripts, découvert en analysant des séquences produite par la technologie "tSMS" ("true Single Molecule Sequencing") de Helicos Bioscience.

Références:
Post-transcriptional processing generates a diversity of 5'-modified long and short RNAs.
Affymetrix ENCODE Transcriptome Project; Cold Spring Harbor Laboratory ENCODE Transcriptome Project.
Nature. 2009 Feb 19;457(7232):1028-32.

New class of gene-termini-associated human RNAs suggests a novel RNA copying mechanism.
Kapranov P, Ozsolak F, Kim SW, Foissac S, Lipson D, Hart C, Roels S, Borel C, Antonarakis SE, Monaghan AP, John B, Milos PM.
Nature. 2010 Jul 29;466(7306):642-6.
 Plus d'infos  


2011-11-10High quality pathway construction from the literature and protein-protein interaction networks using latent semantic indexing
11:00-12:30
178
Background: Many key cellular processes, like cell proliferation or differentiation, involve responses to changes in the cell micro-environment mediated by signals from the cell surface to the nucleus. Such signals are transmitted by sequential protein interactions, represented as an interaction network. These networks are decomposed into signaling pathways, representing a consensus, expert, description of the function of a set of interactions. Interactions in these curated pathways are described in published articles. However, defining and identifying signaling pathways from experimental data is difficult, due to the large number of potential interactions between proteins and due to the large number of published studies that need to be surveyed, in order find support for interactions detected in the data. For that reason, reliable (semi-) automated pathway reconstructions from literature evi- dence are indispensable.

Method: We propose a novel approach to characterize, compare and build signaling pathways by combining the interactome with literature evidence. Our approach is based on Latent Semantic Indexing, a method combining text mining and dimensionality reduction to identify key concepts in published abstracts. Latent Semantic Indexing produces a factor space, which is a vector space of manageable dimensionality, in which we can represent both individual articles and signaling pathways.

Results: We used this factor space to identify pathways by measuring textual similarities between articles describing individual interactions. More specifically, we showed that 1) we are able to distinguish, with high precision, expert-curated signaling pathways from randomly connected compo- nents; 2) in this space, articles can be clustered by pathways, and that 3) complete pathways can be recovered from the interactome by expanding small set of articles describing a subset of the interactions constituting a pathway. Our approach is a very useful tool for experimentalists, since it allows reliable checking and expansion of existing pathway hypotheses and also adds value to experimental results by providing a knowledge-based context.
 Plus d'infos  


2011-09-29Tri parfait par renversements : analyse de complexité en moyenne
11:00-12:30
178 (LaBRI)
Le problème du tri parfait par renversements est motivé par l'étude des réarrangements de génomes. Il s'agit de trier une permutation signée vers la permutation identité (ou son miroir), par une séquence de renversements qui ne cassent aucun intervalle commun. Dans les travaux de Bérard et al. (2007), un algorithme résolvant le problème du tri parfait par renversements d'une permutation signée est proposé, qui repose de manière cruciale sur les arbres des intervalles forts associés aux permutations. Les propriétés combinatoires de cette famille d'arbres sont essentielles à l'analyse de l'algorithme.
Dans l'exposé, je présenterai l'algorithme de Bérard et al., et montrerai comment une étude combinatoire de ces arbres permet de démontrer que la complexité moyenne de l'algorithme est polynomiale. Plus précisément, je montrerai aussi que cet algorithme de tri est de complexité polynomiale avec probabilité 1, asymptotiquement en la taille des permutations en entrée.
Nous nous intéresserons ensuite à la classe des permutations séparables, pour laquelle la combinatoire analytique permet d'obtenir des résultats précis sur certains paramètres des scénarios calculés par l'algorithme : longueur moyenne d'un renversement et nombre moyen de renversements.
Enfin, nous discuterons de la pertinence des résultats en moyenne obtenus pour la distribution uniforme, et des ouvertures possibles vers des distributions non-uniformes.

Il s'agit de travaux en commun avec Cédric Chauve, Marni Mishna et Dominique Rossin, puis avec Marni Mishna et Cyril Nicaud.
 Plus d'infos  


2011-09-15Pathway Preserving Representation of Metabolic Networks
11:00-12:30
Amphi LaBRI (salle 50)
Improvements in biological data acquisition and genomes sequencing now allow to reconstruct entire metabolic networks of many living organisms. The size and complexity of these networks prohibit manual drawing and thereby urge the need of dedicated visualization techniques. An efficient representation of such a network should preserve the topological information of metabolic pathways while respecting biological drawing conventions. These constraints complicate the automatic generation of such visualization as it raises graph drawing issues.
In this paper we propose a method to lay out the entire metabolic network while preserving the pathway information as much as possible. That method is flexible as it enables the user to define whether or not node duplication should be performed, to preserve or not the network topology. Our technique combines partitioning, node placement and edge bundling to provide a pseudo-orthogonal visualization of the metabolic network. To ease pathway information retrieval, we also provide complementary interaction tools that emphasize relevant pathways in the entire metabolic context.

Informations complémentaires : cette présentation reprend les travaux présentés à Eurovis cette année (liste d'auteurs : Antoine Lambert, Jonathan Dubois et Romain Bourqui). Les transparents seront en anglais, la présentation en français.
 Plus d'infos  


2011-06-30Pathway Preserving Representation of Metabolic Networks
11:00-12:30
Amphi LaBRI (salle 50)
*** Dernier GT MaBioVis avant la pause estivale ***

Improvements in biological data acquisition and genomes sequencing now allow to reconstruct entire metabolic
networks of many living organisms. The size and complexity of these networks prohibit manual drawing and
thereby urge the need of dedicated visualization techniques. An efficient representation of such a network should
preserve the topological information of metabolic pathways while respecting biological drawing conventions.
These constraints complicate the automatic generation of such visualization as it raises graph drawing issues.
In this paper we propose a method to lay out the entire metabolic network while preserving the pathway informa-
tion as much as possible. That method is flexible as it enables the user to define whether or not node duplication
should be performed, to preserve or not the network topology. Our technique combines partitioning, node place-
ment and edge bundling to provide a pseudo-orthogonal visualization of the metabolic network. To ease pathway
information retrieval, we also provide complementary interaction tools that emphasize relevant pathways in the
entire metabolic context.

Informations complémentaires : cette présentation reprend les travaux présentés à Eurovis cette année (liste d'auteurs : Antoine Lambert, Jonathan Dubois et Romain Bourqui). Les transparents seront en anglais, la présentation en français.
 Plus d'infos  


2011-05-19Storage and large-scale analysis of genome sequence features using Cassandra data store
11:00-12:30
178 (LaBRI)
I will talk about state of the art for storing multi-terabyte datasets and for performing large-scale global analyses on them. I will explain what is Cassandra nosql datastore, why it is an appropriate choice of technology to support fast growing amount of genomic data. I will present our data model to store annotated genome features in Cassandra datastore and preliminary performance results using this data model.
 Plus d'infos  


2011-05-05Results in complex networks
11:00-12:30
178 (LaBRI)
I will present two results in complex networks.
The first one is a generic active learning method, applicable to networks
arising in various fields. In many networks, vertices have hidden attributes
that are correlated with the network’s topology. For instance, in social
networks, people are more likely to be friends if they are demographically
similar. In food webs, predators typically eat prey of lower body mass.
We explore a setting in which the network’s topology is known, but these
attributes are not. If each vertex can be queried, learning the value of its
hidden attributes —but only at some cost— then we need an algorithm which
chooses which vertex to query next, in order to learn as much as possible about
the attributes of the remaining vertices. We present two heuristics and assess
their results.

The second one is an application of complex network methods to epistemology.
Thanks to a large database of 200K articles, we empirically study the “complex
systems” field and its claims to find universal principles applying to systems
in general. Study of the references shared by the papers allows us to obtain a
global point of view on the structure of this highly interdisciplinary field. We
show that its overall coherence does not arise from a universal theory but
instead from computational techniques and fruitful adaptations of the idea of
self-organization to specific systems. At a more local level, specifically
interdisciplinary, we find that understanding between vastly different
scientific cultures is possible thanks to “trading zones”, i.e. sub-communities
that manage to work at the interface around specific tools (e.g. a DNA
microchip) or concepts (a network).
 Plus d'infos  


2011-04-07Réseaux phylogénétiques pour la visualisation de données biologiques et textuelles
11:00-12:30
Amphi (LaBRI)
Les réseaux phylogénétiques généralisent le modèle de l'arbre pour décrire
l'évolution, en permettant à des arêtes entre les branches de l'arbre
d'exprimer des transferts de matériel génétique entre espèces
coexistantes. Ces réseaux sont reconstruits à partir de différents types
de données : séquences, distances, ou données combinatoires (arbres,
triplets, quadruplets, clades, bipartitions). On peut les classer en deux
types : réseaux abstraits qui permettent de visualiser les données en
faisant apparaître des zones conflictuelles qui traduisent une évolution
non arborée, et les réseaux explicites qui modélisent l'évolution des
espèces, où tout sommet représente une espèce ancestrale ou actuelle.

Je présenterai plusieurs approches pratiques de reconstruction de réseaux
phylogénétiques, explicites et abstraits, en précisant les précautions
d'emploi des méthodes combinatoires. Je montrerai également comment les
réseaux phylogénétiques peuvent être utilisés comme moyen de visualisation
de données textuelles, en généralisant la visualisation en nuage arboré.
 Plus d'infos  


2011-03-31Inférence de réseau basée sur la théorie de l'information et appliquée à l'analyse de régulations transcriptionnelles
11:00-12:30
178 (LaBRI)
Un des problèmes typiques en bioinformatique consiste à extraire de l'information structurée des données issues de biopuces.
Les jeux de données issus de biopuces sont souvent constitués de très nombreuses variables, très peu d'échantillons et beaucoup de bruit. L'analyse de ces données représente donc un des grands défis actuels pour les méthodes d'apprentissage automatique. L'inférence de réseau est une technique d'apprentissage automatique qui vise à déterminer les dépendances entre variables d'un jeu de données et à les représenter à l'aide d'un graphe. Appliquée aux données issues de biopuces, cette technique permet de retrouver le réseau de régulations transcriptionnelles d'une cellule et d'identifier des gènes spécifiques impliqués dans diverses maladies.
Cette présentation se focalise sur les méthodes d'inférence de réseau qui utilisent la théorie de l'information pour inférer les dépendances entre variables. En particulier, je vais présenter MRNET, une méthode d'inférence à base de sélection de variables, ainsi que le package R et Bioconductor qui l'implémente.
 Plus d'infos  


2011-03-17BioRica : Une plateforme pour décrire et simuler les systèmes multi-modèles en biologie.
11:00-12:30
178 (LaBRI)
BioRica sert à décrire mathématiquement le comportement de systèmes biologiques complexes.
C’est une plateforme logicielle permettant la simulation de systèmes en biologie à partir de leur description. Il permet de réutiliser des modèles biologiques existants et de les combiner en modèles plus complexes.
Son originalité est de proposer la composition hiérarchique de modèles existants validés et d’y associer une sémantique rigoureuse.
Les modèles BioRica sont hybrides : composés d’éléments continus (décrits par des systèmes d’équations différentielles), ou discrets (décrits par des automates temporisés).
 Plus d'infos  


2011-03-10Exposé de Frédéric Guyon
11:00-12:30
Salle 178
Nous aurons le plasir d'écouter Frédéric Guyon nous parler d'un sujet qui lui tient à coeur et dont nous aurons le titre que demain matin.

Il sera aussi tout disposé à jouer avec vous au jeu des questions-réponses.

Venez nombreux assiter à ce lever de voile.
 Plus d'infos  


2011-03-03Petite école de Visu 2
11:00-12:30
Salle 178
Nous aurons le plaisir d'écouter Guy Melançon pour la seconde petite école de visualisation. Il nous parlera de:

Structural Analysis of Networks: a Comparative Survey of Useful Metrics
 Plus d'infos  


2011-02-17Petite leçon de MaBioVis : Comparaison de séquences biologiques
11:00-12:30
178 (LaBRI)
Lors de cette session des petites leçons de MaBioVis je présenterai la comparaison de séquences biologiques.
 Plus d'infos  


2011-02-03Evaluer la qualité d'une fragmentation de graphe multi-niveaux
11:00-12:30
178 (LaBRI)
La présentation portera sur une mesure permettant d'évaluer quantitativement la qualité d'une fragmentation de graphe sur plusieurs niveaux.
L'utilisation de telles structures permet notamment la visualisation interactive du réseau sur plusieurs échelles. De nombreux travaux portent également à croire que ce type d'organisation est très courant dans les réseaux sociaux ou biologiques.
Le critère que nous définissons généralise une mesure introduite par Mancoridis. Il traverse récursivement la hiérarchie des fragments et aboutit à un polynôme à une variable qui reflète la qualité de l'ajustement entre le graphe et la hiérarchie proposée.
 Plus d'infos  


2011-01-20Algorithmes pour la bio-informatique et visualisation
11:00-12:30
178 (LaBRI)
Les étudiants de Master 2 Algorithmes et Méthodes Formelles qui suivent l'option "Algorithmes pour la bio-informatique
et visualisation" nous présenteront leur travail de mini-projet.
 Plus d'infos  


2011-01-06Cooperative genome annotation
11:00-12:30
178 (LaBRI)
When we identify a gene and describe its function, we are making a shot in the dark, an informed guess about the relations between the gene and various biological processes, that is always incomplete and too often simply wrong. Applying human judgment to the question is time-consuming and error-prone. And it is biased, since we are naturally more inclined to spend time looking for the strange cases, or the odd mistake, than we are to carefully and systematically describe the "ordinary" cases. Manual genome curation, to paraphrase Churchill, is the worst form of genome annotation, except for all the others. What can we do?

The focus on our work to improve the speed and the quality of genome annotation is to understand that it is a dialogue, and that the goal in the asymptote is to reach a consensus. I will describe how we build web-based software tools to help scientists cooperate in finding, refining, and questioning this consensus. I will also show that we can see this incremental refinement as a smooth transition from unsupervised to supervised classification, that works hand in hand with comparative genomics.
 Plus d'infos  




Liste des événements répétitifs du groupe BioInformatique et Visualisation




Retour
Retour à l'index