No description available.

No description available.

No description available.

Digital photo technology is developing rapidly and is motivating more people to have large personal collections of digital photos. However, effective and fast retrieval of digital photos is not always easy, especially when the collections grow into thousands. World Wide Web (WWW) is one of the platforms that allows digital photo users to publish a collection of photos in a centralised and organised way. Users typically find their photos by searching or browsing uSing a keyboard and mouse. Also in development at the moment are alternative user interfaces such as graphical user interfaces with speech (S/GUI) and other multimodal user interfaces which offer more flexibility to users. The aim of this research was to design and evaluate a flexible user interface for a web based personal digital photo retrieval system. A model of a flexible photo retrieval system (FlexPhoReS) was developed based on a review of the literature and a small-scale user study. A prototype, based on the model, was built using MATLAB and WWW technology. FlexPhoReS is a web based personal digital photo retrieval prototype that enables digital photo users to . accomplish photo retrieval tasks (browsing, keyword and visual example searching (CBI)) using either mouse and keyboard input modalities or mouse and speech input modalities. An evaluation with 20 digital photo users was conducted using usability testing methods. The result showed that there was a significant difference in search performance between using mouse and keyboard input modalities and using mouse and speech input modalities. On average, the reduction in search performance time due to using mouse and speech input modalities was 37.31%. Participants were also significantly more satisfied with mouse and speech input modalities than with mouse and keyboard input modalities although they felt that both were complementary. This research demonstrated that the prototype was successful in providing a flexible model of the photo retrieval process by offering alternative input modalities through a multimodal user interface in the World Wide Web environment.

Le stockage et la gestion de données sont des questions centrales en informatique. La structuration sous forme d'arbres est devenue la norme (XML, JSON). Pour en assurer la pérennité et l'échange efficace des données, il est nécessaire d'identifier de nouveaux mécanismes de transformations automatisables. Nous nous concentrons sur l'étude de transformations d'arbres en mots représentées par des machines à états finies. Nous définissons les transducteurs séquentiels d'arbres en mots ne pouvant utiliser qu'une et unique fois chaque nœud de l'arbre d'entrée pour décider de la production. En réduisant le problème d'équivalence des transducteurs séquentiels à celui des morphismes appliqués à des grammaires algébriques (Plandowski, 95), nous prouvons qu'il est décidable en temps polynomial. Cette thèse introduit la notion de transducteur travailleur, forme normalisée de transducteurs séquentiels, cherchant à produire la sortie le «plus tôt possible» dans la transduction. A l'aide d'un algorithme de normalisation et de minimisation, nous prouvons qu'il existe un représentant canonique, unique transducteur travailleur minimal, pour chaque transduction de notre classe. La décision de l’existence d’un transducteur séquentiel représentant un échantillon, i.e. paires d'entrées et sorties d'une transformation, est prouvée NP-difficile. Nous proposons un algorithme d'apprentissage produisant à partir d'un échantillon le transducteur canonique le représentant, ou échouant, le tout en restant polynomial. Cet algorithme se base sur des techniques d'inférence grammaticales et sur l'adaptation du théorème de Myhill-Nerode. / Storage, management and sharing of data are central issues in computer science. Structuring data in trees has become a standard (XML, JSON). To ensure preservation and quick exchange of data, one must identify new mechanisms to automatize such transformations. We focus on the study of tree to words transformations represented by finite state machines. We define sequential tree to words transducers, that use each node of the input tree exactly once to produce an output. Using reduction to the equivalence problem of morphisms applied to context-free grammars (Plandowski, 95), we prove that equivalence of sequential transducers is decidable in polynomial time. We introduce the concept of earliest transducer, sequential transducers normal form, which aim to produce output "as soon as possible" during the transduction. Using normalization and minimization algorithms, we prove the existence of a canonical transducer, unique, minimal and earliest, for each transduction of our class. Deciding the existence of a transducer representing a sample, i.e. pairs of input and output of a transformation, is proved NP-hard. Thus, we propose a learning algorithm that generate a canonical transducer from a sample, or fail, while remaining polynomial. This algorithm is based on grammatical inference techniques and the adaptation of a Myhill-Nerode theorem.

La recherche de motifs approchée consiste à identifier les occurrences d’un motif modulo une certaine distance au sein d’un texte. Ce problème trouve de nombreuses applications en bio-informatique pour l’analyse de séquences biologiques. Par exemple, les microARN sont des petits ARN qui régulent l’expression des gènes par reconnaissance d’un motif similaire. Comprendre le mode d’action des microARN demande de pouvoir localiser de courts motifs, environ 21 nucléotides, comprenant jusqu’à 3 ou 4 erreurs dans un texte de l’ordre de 108 à 109 nucléotides, représentant un génome. Dans cette thèse, nous proposons un algorithme efficace pour la recherche de motifs approchée, qui se base sur la définition d’un nouveau type de graines avec erreurs, les graines 01*0, et qui exploite une structure d’index compressée, le FM-index. Cet algorithme a été mis en œuvre dans un logiciel librement disponible, appelé Bwolo. Nous démontrons expérimentalement l’avantage de cette approche en nous comparant à l’état de l’art des outils existants. Nous montrons également comment utiliser Bwolo pour mettre en place une analyse originale sur l’étude de la distribution des cibles potentielles de miARN dans deux génomes de plantes, Arabidopsis thaliana et Arabidopsis lyrata. / Approximate string matching consists in identifying the occurrences of a motif within a text, modulo a given distance. This problem has many applications in bioinformatics for the analysis of biological sequences. For instance, microRNAs are short RNA molecules regulating the expression of genes by specific recognition of their sequence motif on the target gene. Understanding the mode of action of microRNAs requires the ability to identify short motifs, around 21 nucleotides in size, comprising up to 3-4 errors in a text whose size is in the order of 108-109 , representing a genome. In this thesis, I have proposed an efficient algorithm for the approximate search of short motifs. This algorithm is based on a new type of seeds containing errors, the 01*0 seeds, and uses a compressed index structure, the FM-index. I have implemented this algorithm in a freely available software, Bwolo. I demonstrate experimentally the advantage of this approach and compare it to the state of the art of existing tools. I also show how Bwolo can be used and have set up an original study on the distribution of potential miRNA target sites in two plant genomes, Arabidopsis thaliana and Arabidopsis lyrata.

Les progrès récents en termes de séquençage d’ADN permettent maintenant d’accéder au matériel génétique de communautés microbiennes extraites directement d’échantillons environnementaux naturels. Ce nouveau domaine de recherche, appelé métagénomique, a de nombreuses applications en santé, en agro-alimentaire, en écologie, par exemple. Analyser de tels échantillons demande toutefois de développer de nouvelles méthodes bio-informatiques pour déterminer la composition taxonomique de la communauté étudiée. L’identification précise des organismes présents est en effet une étape essentielle à la compréhension des écosystèmes même les plus simples. Cependant, les technologies de séquençage actuelles produisent des fragments d’ADN courts et bruités, qui ne couvrent que partiellement les séquences complètes des gènes, ce qui pose un véritable défi pour l’analyse taxonomique à haute résolution. Nous avons développé MATAM, une nouvelle méthode bio-informatique dédiée à la reconstruction rapide et sans erreurs de séquences complètes de marqueurs phylogénétiques conservés, à partir de données brutes de séquençage. Cette méthode est composée d’une succession d’étapes qui réalisent la construction et l’analyse d’un graphe de chevauchement de lectures. Nous l’avons appliquée à l’assemblage de la petite sous-unité de l’ARN ribosomique sur des métagénomes simulés, synthétiques et réels. Les résultats obtenus sont de très bonne qualité et améliorent l’état de l’art. / Recent advances in DNA sequencing now allow studying the genetic material from microbial communities extracted from natural environmental samples. This new research field, called metagenomics, is leading innovation in many areas such as human health, agriculture, and ecology. To analyse such samples, new bioinformatics methods are still needed to ascertain the studied community taxonomic composition because accurate organisms identification is a necessary step to understand even the simplest ecosystems. However, current sequencing technologies are generating short and noisy DNA fragments, which only partially cover the complete genes sequences, giving rise to a major challenge for high resolution taxonomic analysis. We developped MATAM, a new bioinformatic methods dedicated to fast reconstruction of low-error complete sequences from conserved phylogenetic markers, starting from raw sequencing data. This methods is a multi-step process that builds and analyses a read overlap graph. We applied MATAM to the reconstruction of the small sub unit ribosomal ARN in simulated, synthetic and genuine metagenomes. We obtained high quality results, improving the state of the art.

No description available.

Les évolutions technologiques ont consacré l'émergence des services web et du stockage des données en ligne, en complément des bases de données traditionnelles. Ces évolutions facilitent l'accès aux données, mais en contrepartie soulèvent de nouvelles problématiques de sécurité. La mise en œuvre de politiques de contrôle d'accès appropriées est une des approches permettant de réduire ces risques. Nous étudions ici les politiques de contrôle d'accès au niveau d'un document XML, politiques que nous modélisons par des vues de sécurité XML (non matérialisées) à l'instar de Fan et al. Ces vues peuvent être représentées facilement par des alignements d'arbres grâce à l'absence d'opérateurs arithmétiques ou de restructuration. Notre objectif est par conséquent d'examiner comment manipuler efficacement ce type de vues, à l'aide des méthodes formelles, et plus particulièrement des techniques de réécriture de requêtes et la théorie des automates d'arbres. Trois directions principales ont orienté nos recherches: nous avons tout d'abord élaboré des algorithmes pour évaluer l'expressivité d'une vue, en fonction des requêtes qui peuvent être exprimées à travers cette vue. Il s'avère que l'on ne peut décider en général si une vue permet d'exprimer une requête particulière, mais cela devient possible lorsque la vue satisfait des hypothèses générales. En second lieu, nous avons considéré les problèmes soulevés par la mises à jour du document à travers une vue. Enfin, nous proposons des solutions pour construire automatiquement un schéma de la vue. En particulier, nous présentons différentes techniques pour représenter de façon approchée l'ensemble des documents au moyen d'une DTD. / The evolution of web technologies and social trends fostered a shift from traditional enterprise databases to web services and online data. While making data more readily available to users, this evolution also raises additional security concerns regarding the privacy of users and more generally the disclosure of sensitive information. The implementation of appropriate access control models is one of the approaches to mitigate the threat. We investigate an access control model based on (non-materialized) XML views, as presented among others by Fan et al. The simplicity of such views, and in particular the absence of arithmetic features and restructuring, facilitates their modelization with tree alignments. Our objective is therefore to investigate how to manipulate efficiently such views, using formal methods, and especially query rewriting and tree automata. Our research follows essentially three directions: we first develop new algorithms to assess the expressivity of views, in terms of determinacy, query rewriting and certain answers. We show that those problems, although undecidable in our most general setting, can be decided under reasonable restrictions. Then we address the problem of handling updates in the security view framework. And last, we investigate the classical issues raised by schemata, focusing on the specific "determinism'' requirements of DTDs and XML Schemata. In particular, we survey some techniques to approximate the set of all possible view documents with a DTD, and we provide new algorithms to check if the content models of a DTD are deterministic.

L’objectif de cette thèse est d’obtenir des algorithmes sous linéaire permettant de répondre à des problèmes de décision dans les bases de données XML. Plus précisément, on s’inspire du property testing, pour décider approximativement si un arbre d’arité non bornée est valide par rapport à une DTD ; ou plus généralement si un tel arbre est reconnu par un automate d’arbre.Nous avons d’abord étudié le cas simple des mots, c’est-à-dire l’appartenance approchée d’un mot à un langage régulier défini par un automate non-déterministe. Sous la distance d’édition entres les mots, nous proposons un algorithme (ou tester) résolvant l’appartenance approchée en un temps polynomial : en la taille de l’automate aussi bien qu’en la précision (où le paramètre d’erreur). Nous avons aussi amélioré le précédent algorithme d’Alon, Krivelevich, Newman, et Szegedy, (2000) pour l’approximation de l’appartenance à un langage régulier modulo la distance de Hamming. Notre amélioration consiste à rendre cet algorithme polynomial en la taille de l’automate non-déterministe. Ensuite nous avons considéré l’appartenance approchée d’un arbre à un automate d’arbre sous la distance d’édition standard. Notre algorithme résout ce problème avec une complexité en temps exponentielle en la hauteur de l’arbre. Enfin nous avons considéré la validation approchée de DTD par rapport à la « strong edit distance » ; et nous obtenons dans ce cas un algorithme polynomial en la hauteur de l’arbre. Nous complétons nos résultats en prouvant une borne inférieure linéaire en la taille de l’arbre, pour la complexité de tout algorithme décidant l’appartenance approchée d’un arbre à une DTD, sous la strong edit distance. / Inspired by property testing, our objective is to obtain sublinear algorithms for deciding properties of XML databases approximatively. More precisely, we investigate the properties of whether an unranked tree is valid for a DTD, or more generally, whether it is recognized by a tree automaton. We start our studies by the simpler case of words and we considered the approximate membership problem for word non-deterministic automata. For this problem, we provide an efficient tester that runs in polynomial time in the size of the input automata and the error precision. We also improve the previous [Alon, Krivelevich, Newman, and Szegedy, 2000b] approximate membership tester for regular languages modulo the Hamming distance, so that it runs in polynomial time in the size of the input automata. Secondly, we study approximate membership testing for tree automata modulo the standard edit distance, and obtain a tester with run time exponential in the input tree depth. Next we consider approximate DTD validity modulo the strong edit distance. We then provide a tester that depends polynomially on the height of the tree. Finally, modulo the strong edit distance, we prove a linear lower bound on the depth of the input tree.