Éditeur(s) : HAL CCSD
Résumé : In this paper we introduce k-laminar graphs a new class of graphs which extends the idea of Asteroidal triple free graphs. Indeed a graph is k-laminar if it admits a diametral path that is k-dominating. This bio-inspired class of graphs was motivated by a biological application dealing with sequence similarity networks of reads (called hereafter read networks for short). We briefly develop the context of the biological application in which this graph class appeared and then we consider the relationships of this new graph class among known graph classes and then we study its recognition problem. For the recognition of k-laminar graphs, we develop polynomial algorithms when k is fixed. For k=1, our algorithm improves a Deogun and Krastch's algorithm (1999). We finish by an NP-completeness result when k is unbounded.
https://hal.inria.fr/hal-01282715

hal-01282715
https://hal.inria.fr/hal-01282715
ARXIV : 1603.01179

Éditeur(s) : HAL CCSD Elsevier
Résumé : International audience
Given a graph, its hyperbolicity is a measure of how close its distance distribution is to the one of a tree. This parameter has gained recent attention in the analysis of some graph algorithms and the classification of complex networks. We study on practical improvements for the computation of hyperbolicity in large graphs. Precisely, we investigate on relations between the hyperbolicity of a graph G and the hyperbolicity of its atoms, that are the subgraphs output by the clique-decomposition invented by Tarjan [51, 65]. We prove that the maximum hyperbolicity taken over the atoms is at most one unit off from the hyperbol-icity of G and the bound is sharp. We also give an algorithm to slightly modify the atoms, called the " substitution method " , which is at no extra cost than computing the clique-decomposition, and so that the maximum hyperbolicity taken over the resulting graphs is exactly the hyperbolicity of the input graph G. An experimental evaluation of our method for computing the hyperbolicity of a given graph from its atoms is provided for collaboration networks and biological networks. Finally, on a more theoretical side, we deduce from our results the first linear-time algorithm for computing the hyperbolicity of an outerplanar graph.
ISSN: 0304-3975

hal-01540756
https://hal.inria.fr/hal-01540756
https://hal.inria.fr/hal-01540756/document
https://hal.inria.fr/hal-01540756/file/CCDL-2017.pdf
DOI : 10.1016/j.tcs.2017.06.001

Éditeur(s) : HAL CCSD
Résumé : International audience
Extract the features for a multi-touch gesture is difficult due to the complex temporal and motion relations between multiple trajectories. In this paper we present a new generic graph model to quantify the shape, temporal and motion information from multi-touch gesture. To make a comparison between graph, we also propose a specific graph matching method based on graph edit distance. Results prove that our graph model can be fruitfully used for multi-touch gesture pattern recognition purpose with the classifier of graph embedding and SVM.
17th Biennial Conference of the International Graphonomics Society
Pointe-à-Pitre, Guadeloupe

hal-01165768
https://hal.univ-antilles.fr/hal-01165768
https://hal.univ-antilles.fr/hal-01165768/document
https://hal.univ-antilles.fr/hal-01165768/file/IGS_2015_submission_6.pdf

Éditeur(s) : HAL CCSD
Résumé : International audience
EmailPrintRequest PermissionsThe emergence of new communication means such as online newspapers and exchange and sharing websites allow us to go further in the understanding of diffusion phenomena. Indeed, these public discussion areas are now firmly established in our societies and are known to be strong sensors of both human behaviors and collective feelings. In this paper we focus on diffusion phenomena that occur on Twitter and we propose a set of measures that aims to characterize globally and locally the processes. Our objective is to identify what are the conditions in which a person decides to forward the information. Our measures have been used to study two events occurred in January 2015: the presentation of Microsoft HoloLens, a new augmented reality headset, and the political election in Greece. The results obtained show a strong heterogeneity in the individual behaviours involved in the diffusion process. Our approach has been implemented into a graphical tool which is able to conduct real time analysis on any kind of topics occurring on Twitter.
IEEE International Conference on Research Challenges in Information Science (RCIS)
Athens, Greece

hal-01312382
https://hal.univ-antilles.fr/hal-01312382
DOI : 10.1109/RCIS.2015.7128894

Éditeur(s) : HAL CCSD IOS Press
Résumé : International audience
Recent work has used graphs to modelize expression data from microarray experiments, in view of partitioning the genes into clusters. In this paper, we introduce the use of a decomposition by clique separators. Our aim is to improve the classical clustering methods in two ways: first we want to allow an overlap between clusters, as this seems biologically sound, and second we want to be guided by the structure of the graph to define the number of clusters. We test this approach with a well-known yeast database (Saccharomyces cerevisiae). Our results are good, as the expression profiles of the clusters we find are very coherent. Moreover, we are able to organize into another graph the clusters we find, and order them in a fashion which turns out to respect the chronological order defined by the the sporulation process.
ISSN: 1386-6338

hal-00521936
https://hal.archives-ouvertes.fr/hal-00521936

Éditeur(s) : HAL CCSD
Résumé : International audience
We propose in this paper a new online Multi-UserMulti-Touch handwritten diagram DataBase (MUMTDB) forevaluating recognition systems under the multi-user situation.The data is collected according to two predefined mind mapscenarios which contains 9 classes of graphical symbols. Eachscenario is completed by involving two users at the same time.Since the users are given freedom to draw the symbols asthey want, the dataset contains a diversity of multi-stroke andeven multi-touch symbols. It allows addressing new challengingproblems regarding the recognition of simultaneous composition of structured documents. The dataset is freely availableon-line.
International Conference on Frontiers in Handwriting Recognition (ICFHR)
Shenzhen, China

hal-01374376
https://hal.univ-antilles.fr/hal-01374376

Éditeur(s) : HAL CCSD Springer
Résumé : Third International Workshop, MLMI 2012, Held in Conjunction with MICCAI 2012
International audience
Universal Nearest Neighbours (unn) is a classifier recently proposed, which can also effectively estimates the posterior probability of each classification act. This algorithm, intrinsically binary, requires the use of a decomposition method to cope with multiclass problems, thus reducing their complexity in less complex binary subtasks. Then, a reconstruction rule provides the final classification. In this paper we show that the application of unn algorithm in conjunction with a reconstruction rule based on the posterior probabilities provides a classification scheme robust among different biomedical image datasets. To this aim, we compare unn performance with those achieved by Support Vector Machine with two different kernels and by a k Nearest Neighbours classifier, and applying two different reconstruction rules for each of the aforementioned classification paradigms. The results on one private and five public biomedical datasets show satisfactory performance.
Machine Learning in Medical Imaging
Nice, France

hal-00958909
https://hal.archives-ouvertes.fr/hal-00958909
https://hal.archives-ouvertes.fr/hal-00958909/document
https://hal.archives-ouvertes.fr/hal-00958909/file/Miccai.pdf
DOI : 10.1007/978-3-642-35428-1_15

Éditeur(s) : HAL CCSD Hermann-Éditions
Résumé : International audience
Dans le domaine des réseaux sociaux, la recherche de motifs fréquents correspond à l'extraction de sous-graphes retrouvés fréquemment dans un réseau ou un ensemble de réseaux. Contrairement aux approches classiques qui s'appuient uniquement sur des régularités structurelles, nous présentons dans ce travail l'outil GT-FLMin, capable d'exploiter les informations sur la structure pour extraire des régularités dans les liens qui connectent des noeuds similaires du point de vue de leurs caractéristiques. Nous appelons de tels motifs des liens fréquents.
Extraction et gestion des connaissances
Bordeaux, France

hal-00768426
https://hal.archives-ouvertes.fr/hal-00768426

Éditeur(s) : HAL CCSD
Résumé : International audience
More and more animal species are endangered. In order to study and protect them, several measures have been taken, which now seem to show their limit. This work focuses on the counting process, a key issue for any project that aims to protect animals. Indeed, this paper proposes an algorithm for automatic counting of singing birds in their habitat by using wireless sensors fitted with microphone. Sensors are used to record audio samples of bird songs. These samples are used to extract some kinds of song fingerprint that are thereafter used to recognize the bird species, through a classification process. Afterwards, by analyzing data which have been collected by a central base, the network structure derived from detection fields of sensors, allows our algorithm to propose an estimate of singing birds in the habitat. This paper details the counting algorithm which uses graph theory and audio inputs comparison. Finally, we demonstrate our scheme efficiency through experimentations.
Local Computer Networks (LCN)
Clearwater, United States

hal-00786165
https://hal.archives-ouvertes.fr/hal-00786165
DOI : 10.1109/LCNW.2012.6424060

Éditeur(s) : HAL CCSD ACM
Résumé : International audience
This study presents two algorithms that count birds with wireless sensors equipped with microphones. Audio inputs are parametrized to get some kind of fingerprints which are used to recognize the song of the birds in a classification process. Afterward, counting algorithms derive an estimate of the number of singing birds in the habitat. Unlike traditional approaches which leverage the audio waveform to get the location of the targets, we use a trilateration technique on graphs derived from the detection of the birds. These graphs exhibit nice properties which enable the finding of the estimate in polynomial time. Further, experiments are conducted and confirmm the efficiency of our counting algorithms even in the presence of noise.
Proceedings of the 6th ACM symposium on Performance evaluation of wireless ad hoc, sensor, and ubiquitous networks
New York, United States

hal-00602263
https://hal.archives-ouvertes.fr/hal-00602263
DOI : 10.1145/1641876.1641891

Éditeur(s) : HAL CCSD
Résumé : Many works deal with the subsequence matching problem using automata structures. It is to decide, given two sequences $s$ and $t$, whether $s$ is a subsequence of $t$. Automata like the Directed Acyclic Subsequence Graph (DASG) or the Subsequence Automaton (SA) accept all subsequences of a set of texts. We focus on this last structure and provide some useful results upon dynamically updates of the SA. Indeed, sequences are indexed as soon as they are processed, allowing to dynamically add or to remove sequences from the set of indexed texts. Moreover, the highlight of these properties also makes it possible to update this automaton whenever a sequence of the set is modified.
https://hal.inria.fr/inria-00257567

inria-00257567
https://hal.inria.fr/inria-00257567
https://hal.inria.fr/inria-00257567/document
https://hal.inria.fr/inria-00257567/file/iSA.pdf

Éditeur(s) : HAL CCSD
Résumé : International audience
A key issue for any project that aims to study endangered animals is the counting process. In this work, we propose an algorithm for automatic counting of singing birds in their habitat by using wireless sensors fitted with microphone. Sensors are used to record audio samples of bird songs and samples are analyzed to extract fingerprints that permit to recognize bird species. This paper details the counting algorithm that uses graph theory and audio inputs comparison. Finally, we demonstrate our scheme efficiency through experimentations.
International Symposium on a World of Wireless, Mobile and Multimedia Networks
Lucca, Italy

hal-00618563
https://hal.archives-ouvertes.fr/hal-00618563
DOI : 10.1109/WoWMoM.2011.5986215

Éditeur(s) : HAL CCSD
Résumé : Predicting, modelling and analysing the metabolism of xenobiotics, foreign substances to an organism, using computer methods, has been a major challenge for the scientific community for many years. This thesis aims to implement multiscale computing methods for predicting and analyzing the metabolism of xenobiotics. A first focus of this study was on the construction and de novo automatic annotation of metabolic graphs combining high sensitivity and precision. These graphs thus provide the prediction of the metabolism of xenobiotics in humans, as well as the genotoxicity of the molecules and atoms that make up xenobiotics. Then, the work focused on the implementation of a dynamic mathematical model modelling enzymatic competition effects through the development of a methodology allowing the exploitation of limited biological data while limiting inherent biases.
Prédire, modéliser et analyser le métabolisme de xénobiotiques, substances étrangères à un organisme, à l’aide de méthodes informatiques est un challenge majeur mobilisant la communauté scientifique depuis de nombreuses années. Cette thèse vise à implémenter des méthodes informatiques multi-échelles pour prédire et analyser le métabolisme des xénobiotiques. Un premier axe de cette étude portait sur la construction et l’annotation automatique de novo de graphes métaboliques combinant fortes sensibilités et précisions. Ces graphes fournissent ainsi la prédiction du métabolisme de xénobiotiques chez l’homme, ainsi que la génotoxicité des molécules et atomes qui le composent. Puis, le travail s’est orienté sur l’implémentation d’un modèle mathématique dynamique modélisant des effets de compétition enzymatique à travers le développement d’une méthodologie permettant l’exploitation de données biologiques restreintes tout en limitant les biais inhérents.
https://hal-univ-rennes1.archives-ouvertes.fr/tel-01659375

tel-01659375
https://hal-univ-rennes1.archives-ouvertes.fr/tel-01659375
https://hal-univ-rennes1.archives-ouvertes.fr/tel-01659375/document
https://hal-univ-rennes1.archives-ouvertes.fr/tel-01659375/file/these.pdf

Éditeur(s) : HAL CCSD
Résumé : International audience
BackgroundTree above ground biomass (AGB) is currently estimated by tree-level allometrical models that take into account, tree volume estimated from proxy variables of tree size (DBH) and species average wood specific gravity (WSG). These methods are common and realistic from a practical point of view. However, they do not take into account deviance from fixed allometrical trajectories and species or tree level WSG variations. Here, we present Xtrawood software that allows computation of tree AGB according to structure and WSG variations.MethodXtrawood reconstructs tree structure and integrates WSG variations by merging tree structure and WSG data measured at different position in trees, leading to the computation of global AGB and visualization of WSG variation along tree structure. Tree structure is measured according to stem dimensions (length, diameter) and positions within tree, and encoded in Multiscale Tree Graph format (MTG). WSG data is made of radial WSG profiles (1 measure each 0,5 cm from pith to bark) sampled at different heights within whole tree. Xtrawood output are illustrated using a dataset collected on an Amazonian forest ‘biomass dominant species’, Dicorynia guianensis Amsh., also known to exhibit substantial WSG gradients along both radial and vertical axis. 9 trees ranging from 15 to 60 cm DBH were measured by climbers. Each tree was felled and samples were collected at different positions (3 in trunk, 1 to 5 in crown) to record WSG radial profiles.ResultsXtrawood allows computation of tree volume, but also visualization of WSG variations in tree as well as inference of WSG radial profiles at different heights. Output variables are decomposed according to different tree scale and locations (axis, trunk/crown) and easy to extract. Xtrawood results will be compared to those of standard estimation method and can be used to identify positions in trees where WSG value leads to the better estimate of tree AGB.Conclusion/perspectiveXtrawood produces AGB estimate with data from intensive measurements practices. The sampling protocol, used here, remains destructive and time-consuming because Xtrawood is not directly dedicated to forest managers, but to help calibration of realistic sampling strategies. Moreover, Xtrawood offers a way to understand relationships between tree development, WSG variations within tree structure and biomass accumulation in the context of natural forests or plantations. A software demo is available at coffee break.
53rd Annual Meeting of the Association for Tropical Biology and Conservation (ATBC 2016)
Montpellier, France

Droits : http://creativecommons.org/licenses/by/
hal-01349613
https://hal.archives-ouvertes.fr/hal-01349613

Éditeur(s) : HAL CCSD Elsevier
Résumé : International audience
We present GravProcess, a set of MATLAB routines to process gravity data from complex campaign surveys and calculate the associated gravity field. Data reduction, analysis, and representation are done using the MATLAB Graphical User Interface Tool, which can be installed on most systems and platforms. Data processing is divided into several steps: (1) Integration of gravity data, station location, and gravity line connection input files; (2) Gravity data reduction applying solid-Earth tide and instrumental drift corrections and, depending on the required processing level, air pressure and oceanic tidal corrections; (3) Automatic network adjustment and alignment to absolute base stations; (4) Free air and terrain corrections to calculate gravity values and anomalies, and to estimate the associated errors. The final step is dedicated to post-processing and includes graphical representations of data and an output text file, which can be used by Geographic Information System software. An example of this processing chain applied to a recent survey in northern Morocco is given and compared with previous available results.
ISSN: 0098-3004

hal-01217120
https://hal.archives-ouvertes.fr/hal-01217120
DOI : 10.1016/j.cageo.2015.04.005

Éditeur(s) : HAL CCSD
Résumé : International audience
The study of complex biological processes requires to forgo simplified models for extensive ones. Yet, these models' size and complexity place them beyond understanding. Their analysis requires new methods for identifying general patterns. The Transforming Growth Factor TGF-β is a multifunctional cytokine that regulates mammalian cell development , differentiation, and homeostasis. Depending on the context, it can play the antagonistic roles of growth inhibitor or of tumor promoter. Its context-dependent pleiotropic nature is associated with complex sig-naling pathways. The most comprehensive model of TGF-β-dependent signaling is composed of 15,934 chains of reactions (trajectories) linking TGF-β to at least one of its 159 target genes. Identifying functional patterns in such a network requires new automated methods. This article presents a framework for identifying groups of similar trajec-tories composed of the same molecules using an exhaustive and without prior assumptions approach. First, the trajectories were clustered using the Relevant Set Correlation model, a shared nearest-neighbors clustering method. Five groups of trajectories were identified. Second, for each cluster the over-represented molecules were determined by scoring the frequency of each molecule implicated in trajectories. Third, Gene set enrichment analysis on the clusters of trajectories revealed some specific TGF-β-dependent biological processes, with different clusters associated to the antagonists roles of TGF-β. This confirms that our approach yields biologically-relevant results. We developed a web interface that facilitates graph visualization and analysis. Our clustering-based method is suitable for identifying families of functionally-similar trajectories in the TGF-β signaling network. It can be generalized to explore any large-scale biological pathways.
CMSB 2017 - 15th International Conference on Computational Methods in Systems Biology
Darmstadt, France

hal-01559249
https://hal.archives-ouvertes.fr/hal-01559249
https://hal.archives-ouvertes.fr/hal-01559249/document
https://hal.archives-ouvertes.fr/hal-01559249/file/JeanCoquet_CMSB.pdf

Éditeur(s) : HAL CCSD Elsevier
Résumé : International audience
We present a graphical user interface to facilitate the processing of teleseismic shear-wave splitting observations. In contrast to a fully automated technique, we present a manual, per-event approach that maintains user control during the sequence of processing. The SplitLab environment is intended to undertake the repetitive processing steps while enabling the user to focus on quality control and eventually the interpretation of the results. Pre-processing modules of SplitLab create a database of events and link the corresponding seismogram files. The seismogram viewer tool uses this database to perform the measurement interactively. Post-processing of the combined results of such a project includes a viewer and export option. Our emphasis lies in the application to teleseismic shear-wave splitting analysis, but our code can be extended easily for other purposes. SplitLab can be downloaded at http://www.gm.univ-montp2.fr/splitting/.
ISSN: 0098-3004

hal-00412372
https://hal.archives-ouvertes.fr/hal-00412372
https://hal.archives-ouvertes.fr/hal-00412372/document
https://hal.archives-ouvertes.fr/hal-00412372/file/Wuestefeld_Splitlab_CompGeosc2008_hal.pdf
DOI : 10.1016/j.cageo.2007.08.002

Éditeur(s) : HAL CCSD BioMed Central
Résumé : International audience
Background: Increasingly, similarity networks are being used for evolutionary analyses of molecular datasets. These networks are very useful, in particular for the analysis of gene sharing, lateral gene transfer and for the detection of distant homologs. Currently, such analyses require some computer programming skills due to the limited availability of user-friendly freely distributed software. Consequently, although appealing, the construction and analyses of these networks remain less familiar to biologists than do phylogenetic approaches. Results: In order to ease the use of similarity networks in the community of evolutionary biologists, we introduce a software program, EGN, that runs under Linux or MacOSX. EGN automates the reconstruction of gene and genome networks from nucleic and proteic sequences. EGN also implements statistics describing genetic diversity in these samples, for various user-defined thresholds of similarities. In the interest of studying the complexity of evolutionary processes affecting microbial evolution, we applied EGN to a dataset of 571,044 proteic sequences from the three domains of life and from mobile elements. We observed that, in Borrelia, plasmids play a different role than in most other eubacteria. Rather than being genetic couriers involved in lateral gene transfer, Borrelia's plasmids and their genes act as private genetic goods, that contribute to the creation of genetic diversity within their parasitic hosts. Conclusion: EGN can be used for constructing, analyzing, and mining molecular datasets in evolutionary studies. The program can help increase our knowledge of the processes through which genes from distinct sources and/or from multiple genomes co-evolve in lineages of cellular organisms.
ISSN: 1471-2148

hal-01544799
https://hal.archives-ouvertes.fr/hal-01544799
DOI : 10.1186/1471-2148-13-146

Éditeur(s) : HAL CCSD
Résumé : Given a set of strings, the Common Subsequence Automaton accepts all common subsequences of these strings. Such an automaton can be deduced from other automata like the Directed Acyclic Subsequence Graph or the Subsequence Automaton. In this paper, we introduce some new issues in text algorithm on the basis of Common Subsequences related problems. Firstly, we make an overview of different existing automata, focusing on their similarities and differences. Secondly, we present a new automaton, the Constrained Subsequence Automaton, which extends the Common Subsequence Automaton, by adding an integer $q$ denoted quorum.
https://hal.inria.fr/inria-00257561

inria-00257561
https://hal.inria.fr/inria-00257561
https://hal.inria.fr/inria-00257561/document
https://hal.inria.fr/inria-00257561/file/CSAq.pdf