Constraint satisfaction problems (CSPs) provide a unified framework for studying a wide variety of computational problems naturally arising in combinatorics, artificial intelligence and database theory. To any finite domain D and any constraint language Γ (a finite set of relations over D), we associate the constraint satisfaction problem CSP(Γ): an instance of CSP(Γ) consists of a list of variables x1,x2,...,xn and a list of constraints of the form "(x7,x2,...,x5) ∈ R" for some relation R in Γ. The goal is to determine whether the variables can be assigned values in D such that all constraints are simultaneously satisfied. The computational complexity of CSP(Γ) is entirely determined by the structure of the constraint language Γ and, thus, one wishes to identify classes of Γ such that CSP(Γ) belongs to a particular complexity class. In recent years, combined logical and algebraic approaches to understand the complexity of CSPs within the complexity class P have been especially fruitful. In particular, precise algebraic conditions on Γ have been conjectured to be sufficient and necessary for the membership of CSP(Γ) in the complexity classes L and NL (under standard complexity theoretic assumptions, e.g. L different from NL). These algebraic conditions are known to be necessary, and from the algorithmic side, a promising body of evidence is fast-growing. The main tools to establish membership of CSPs in L and NL are the logic programming fragments symmetric and linear Datalog, respectively. This thesis is centered around the above algebraic conjecture for CSPs in L, and most of the technical work is devoted to establishing the membership of several large classes of CSPs in L. Among other results, we characterize all graphs for which the list homomorphism problem is in L, a well-studied and natural class of CSPs. We also extend this result to obtain a complete characterization of the complexity of the list homomorphism for graphs. We develop new tool (dualities for symmetric Datalog) to show membership of CSPs in L, prove an L − NL dichotomy for the list homomorphism problem for oriented paths, provide results about the structure and polymorphisms of Maltsev digraphs, and also contribute to the conjecture of Dalmau that every CSP in NL is in fact in linear Datalog. / Les problèmes de satisfaction de contraintes (ou CSP) forment un cadre particulièrement riche permettant de formaliser de façon uniforme un grand nombre de problèmes algorithmiques tirés de l'optimisation combinatoire, de l'intelligence artificielle et de la théorie des bases de données. À chaque domaine D et chaque langage de contraintes Γ (i.e. un ensemble de relations sur D), on associe le problème CSP(Γ) suivant. Une instance du problème est constituée d'une liste de variables x1,...,xn et d'une liste de contraintes de la forme (x7,x2,...,x5) ∈ R, où R ∈ Γ. On cherche à déterminer si des valeurs de D peuvent être assignées aux variables de telle sorte que les contraintes soient toutes satisfaites simultanément. La complexité algorithmique de CSP(Γ) est entièrement fonction de la structure du langage de contraintes Γ et on cherche alors à identifier des classes de contraintes pour lesquelles CSP(Γ) appartient à une classe de complexité spécifique. Récemment, la combinaison des approches logique et algébrique a porté fruits dans la compréhension de la complexité des CSP à l'intérieur de la classe P. En particulier, on a conjecturé des conditions algébriques nécessaires et suffisantes précises pour l'appartenance de CSP(Γ) dans les classes L et NL (sous les hypothèses habituelles en théorie de la complexité, e.g. L est différent de NL). Ces conditions algébriques sont sues être nécessaires, et d'un point de vue algorithmique, les indications en faveur du résultat s'accumulent rapidement. Les outils principaux pour établir l'appartenance d'un CSP à L ou NL sont respectivement les fragments "symmetric Datalog" et "linear Datalog" en programmation logique. Notre thèse est centrée sur la conjecture algébrique ci-haut mentionnée pour les CSP dans L, et la majeure partie du travail technique est dédiée à montrer l'appartenance de plusieurs grandes familles de CSP dans L. Entre autres résultats, nous caractérisons tous les graphes pour lesquels le problème de "list homomorphism" est dans L, une famille naturelle et bien étudiée de CSP. Nous étendons aussi ce résultat pour obtenir une caractérisation complète de la question pour les graphes. Nous développons de nouveaux outils (les dualités pour "symmetric Datalog") pour montrer l'appartenance de CSP dans L, nous prouvons une dichotomie L-NL pour les problèmes de "list homomorphism" pour les chemins orientés, nous donnons des résultats sur la structure et les polymorphismes des digraphes de Maltsev, et nous contribuons à la conjecture de Dalmau à l'effet que chaque CSP dans NL est en fait dans "linear Datalog".

The majority of touch-enabled musical production software tend to use metaphors from professional musical studio environments in their interface (e.g., a rackmount, turntables plus a crossfader, or a keyboard) or simply use single-finger input as a computer mouse. We identify a need for musical software that benefits from novel graphical user interface elements and innovative metaphors to provide control over pre-recorded music. We hypothesize that a software design approach using conceptual integration, or blending, will lead to new ludic interfaces for musical expression with the potential to facilitate DJ tasks. Multi-touch technology offers the promise of going beyond traditional mouse-based user interfaces, and is especially pertinent in that it provides full embodiment: the user interacts directly with the visual feedback of the system. This change in paradigm has implications in software design, not yet fully understood in tools for musical expression.This thesis first documents the existing methods of implementing multi-touch technology, before suggesting a taxonomy of multi-touch devices. A literature review of multi-touch systems for musical applications is also presented, after which metaphor and blending (also known as conceptual integration) are discussed. We apply blending to software design for multi-touch musical software and introduce our programming framework, TactoSonix. / Dans leur interface utilisateur, la plupart des logiciels de production musicale pour écrans tactiles multipoints emploient des métaphores issues des studios de musique professionnels dans leur interface utilisateur (châssis à effets de guitare, tourne-disques, potentiomètres rectilignes, clavier), ou utilisent un doigt qui joue le rôle de souris. Cela nous a amenés à constater que ces logiciels gagneraient à inclure des éléments innovateurs au niveau de l'interface utilisateur et à employer des métaphores inexplorées dans un contexte de contrôle de morceaux de musique pré-enregistrée. Nous partons de l'hypothèse que la conception de logiciel assistée par l'intégration conceptuelle (blending) permettra le développement d'interfaces ludiques pour l'expression musicale et facilitera certaines tâches des DJs. La technologie tactile multipoints nous permet d'imaginer des interfaces de logiciels non-traditionnelles, car elle combiner les interfaces de rétroaction visuelle et de contrôle du systême. Ce changement de paradigme nous oblige à réévaluer la conception des logiciels de production musicale, et à étudier ses applications dans le domaine de l'expression musicale. Ce mémoire répertorie les méthodes qui permettent actuellement de concevoir des dispositifs tactiles multipoints dont il propose une taxonomie. Il présente une analyse de la littérature des systèmes tactiles multipoints dans des contextes musicaux. Les concepts de métaphore et d'intégration conceptuelle (blending) sont étudiés puis appliqués à la conception de notre plate-forme de programmation musicale tactile multi-points, TactoSonix.

Nowadays Kademlia is one of the most widely used DHTs (Distributed Hash Table) in P2P (peer-to-peer) networks. This work studies one essential question about Kademlia overlay networks from a mathematical perspective: how long does it take to locate a node? To answer it, we introduce a random graph K to model a Kademlia overlay and study how long it takes to locate a given vertex in K by using Kademlia's routing algorithm. / Aujourd'hui Kademlia est l'un des les plus utilisés DHTs (Distributed Hash Tableau) dans les réseaux P2P (peer-to-peer). Cet article étudie une question essentielle des réseaux "overlay" de Kademlia d'un point de vue mathématique: combien de temps faut-il pour localiser un noeud? Pour y répondre, nous introduisons un graphe aléatoire K pour modéliser un réseau de Kademlia et étudier la complexité d'un algorithme de routage de Kademlia.

Smartphones and similar mobile devices present an unprecedented opportunity to collect data about human behaviour. Integrated into daily life, devices are privy to information about who we communicate with, where we are, and how we spend our time. However, without the proper tools for analysis and the ability to scale up to large amounts of data and large numbers of users, this data is of limited value. This thesis presents tools for extracting information about activities and location from sensor data available on commodity smartphones. We present an algorithm for comparing time series and demonstrate on a large number of benchmark problems that it is competitive with, and often exceeds, the performance of existing algorithms, while being efficient enough to run in real time on a standard smartphone. Activity and gait recognition are presented as applications of our approach, and the performance on these tasks is shown to exceed that of state-of-the-art approaches. For location detection, we present a thorough study of wifi signals in dynamic, nonstationary environments, and conclude that a new multinomial model is preferable to the standard Gaussian model used to model wifi measurements on a mobile terminal. We present a clustering algorithm for wifi signals that uses an underlying multinomial model, and demonstrate on a large dataset that this approach performs favourably on the task of identifying physical locations from wifi data. By basing our approach on the hierarchical Dirichlet process, the number of identifiable locations scales based on the data, and does not need to be prespecified. This allows for accurate, real-time localization of a mobile device both indoors and outdoors, in a manner that, contrary to existing approaches, protects the privacy of the user. Even detailed information is of limited value without the ability to convey it to the user in a meaningful way. We present a framework for translating from sensor data into human-readable descriptions of the events taking place. This framework is evaluated on a corpora of 150 GB of sensor data recorded from 38 users over 14 months, and provides for convenient visualization of large amounts of data and accurate reporting, in natural language, of events transpiring in the data. / Les téléphones intelligents et les appareils mobiles semblables nous fournissent une occasion sans précédent de recueillir des données à propos du comportement humain. Puisqu'ils font partie intégrante de notre vie quotidienne, ces appareils ont accès à des informations privilégiées concernant les personnes avec qui nous communiquons, les endroits où nous nous trouvons, et les façons dont nous passons notre temps. Cependant, sans outils d'analyse adéquats et la capacité de traiter de grandes quantités de données et de grands nombres d'usagers, ces données ont une valeur limitée. Cette thèse présente des outils capables d'extraire des informations concernant les activités et l'emplacement d'une personne à partir des données amassées par les capteurs intégrés dans les téléphones intelligents de consommation courante. Nous présentons un algorithme de comparaison de séries temporelles et nous démontrons que sur un grand nombre de problèmes de référence, la performance de cet algorithme est comparable, et souvent supérieure, à celle des approches de pointe alors que l'algorithme est suffisamment efficace pour être éxécuté en temps réel sur un téléphone intelligent moyen. Nous présentons la reconnaissance des activités et de la démarche en tant qu'applications de cet algorithme, et démontrons que sa performance sur ces tâches dépasse celle des approches de pointe. Concernant la détection de l'emplacement, nous présentons une étude approfondie des signaux wifi dans des environnements dynamiques non-stationnaires, et concluons qu'un nouveau modèle multinomial est préférable au modèle gaussien standard utilisé pour modéliser les mesures de la force des signaux wifi sur un terminal mobile. Nous présentons un algorithme de groupement pour signaux wifi qui utilise un modèle multinomial sous-jacent, et démontrons que sur un ensemble de données de grande taille, la performance de cette approche se compare favorablement à celle du modèle Gaussien standard lorsque qu'elle est confrontée à la tâche d'identifier des emplacements physiques à partir de données wifi. En basant notre approche sur le processus hiérarchique de Dirichlet, le nombre d'emplacements identifiables varie en se basant sur les données, et n'a pas besoin d'être spécifié au préalable. Ceci permet de localiser un appareil mobile en temps réel de façon précise, à l'intérieur comme à l'extérieur, d'une façon qui, contrairement aux approches existantes, protège la vie privée de l'usager. Même les informations détaillées ont une valeur limitée si on ne dispose pas de la capacité de les communiquer à l'usager de façon significative. Nous présentons donc un cadre pour traduire les données amassées par les capteurs en descriptions des évènements qui se produisent lisibles par les êtres humains. Ce cadre est évalué sur des corpora d'une taille combinée de 150 Go composé de données amassées par les capteurs de 38 usagers sur une période de 14 mois, et il permet de visualiser de larges quantités de données ainsi que de produire des rapports exacts, en langage naturel, des évènements dont la trace est extraite des données.

Modern information systems, consisting of an application server tier and a database tier, offer several consistency guarantees for accessing data where strong consistency is traded for better performance or higher availability. However, it is often not clear how an application is affected when it runs under a low level of consistency. In fact, current application designers have basically no tools that would help them to get a feeling of which and how many inconsistencies actually occur during run-time of their particular application. In this thesis, we present new approaches to detect and quantify consistency anomalies for arbitrary multi-tier or cloud applications accessing various types of data stores in transactional or non-transactional contexts. We do not require any knowledge on the business logic of the studied application nor on its selected consistency guarantees. Our detection approaches can be off-line or on-line and for each detected anomaly, we identify exactly the requests and data items involved. Furthermore, we classify the detected anomalies into patterns showing the business methods involved as well as their occurrence frequency. Our approaches can help designers to either choose consistency guarantees where the anomalies do not occur or to change the application design to avoid the anomalies. Furthermore, we provide an option in which future anomalies are dynamically prevented should a certain threshold of anomalies occur. To test the effectiveness of our approaches, we have conducted a set of experiments analyzing the occurrence of anomalies in the benchmarks RUBiS and SPECj Enterprise 2010 under the multi-tier platform JavaEE and the benchmarks JMeter andYahoo! YCSB under the cloud platforms Google App Engine and Cassandra, respectively. / Les systèmes d'information modernes, consistant d'un niveau de serveur d'applications et d'un niveau de base de données, offrent plusieurs guaranties de consistance pour accéder à des données où la consistance est compromise pour une meilleure performance ou pour une haute disponibilité. Cependant, il n'est souvent pas claire comment une application est affectée lorsqu'elle s'exécute sous un bas niveau de consistance. En effet, les concepteurs d'applications actuelles ne disposent pas d'outils qui leur permettent d'avoir un de idée sur quelles inconsistances ainsi que sur leur nombre d'occurence during l'execution de leur application particulière. Dans cette thèse, nous présentons de nouvelles approches pour détecter et quantifier les anomalies de consistance pour des applications arbitraires multi-niveaux ou cloud accédant différent types de bases de données sous des contextes transactionels ou non-transactionels. Nous ne nécessitons aucune connaissance sur la logique de l'application étudiée ni sur ses guaranties de consistance. Notre approche de détection peut êetre hors ligne ou en ligne et pour chaque anomalie détectée, nous identifions exactement les requêetes et les éléments de données impliquées. En outre, nous classons les anomalies détectées en des patrons d'anomalies montrant les méthodes impliquées ainsi que leur fréquence d'occurrence. Notre approche peut aider les concepteurs à choisir soit des garanties de consistance sous lesquelles les anomalies ne se produisent pas ou modifier la conception de leur applications afin d'éviter les anomalies. En outre, nous fournissons une option sous laquelle les futures anomalies sont dynamiquement évitées si un certain seuil d'anomalies est dépassé. Pour tester l'efficacité de nos approches, nous avons mené une série d'expériences analysant l'occurrence d'anomalies pour les bancs d'essai RUBiS et SPECj Enterprise 2010 sous la plate-forme multi-niveaux JavaEE ainsi que pour les bancs d'essai JMeter etYahoo! YCSB respectivement sous les plates-formes cloud Google App Engine et Cassandra.

Reference documentation is an important source of information on API usage. Programmers, however, can easily overlook reference information because of its tedious nature, and because the information they seek can be buried among irrelevant or boiler-plate text. We propose to detect and recommend fragments of API documentation relevant and important to a task. We categorize pieces of information in API documentation based on the type of knowledge they contain. From the pieces that contain knowledge worthy of recommendation, we extract the composition and the pattern of words, and use the patterns to automatically find new pieces that contain similar knowledge. In an evaluation study, with a training set of manually-classified reference documentation of about 1 000 API elements, we could issue recommendations with about, on average, 90% precision and 69% recall. / La documentation de référence est une source importante d'information sur l'usage d'une API. Cependant, les programmeurs peuvent négliger cette information que l'information recherchée se trouve enfouie au milieu de texte passe-partout et sans pertinence. Nous proposons de détecter et recommender les fragments de documentation d'API pertinents à une tâche donnée de façon automatique. Nous catégorisons les morceaux d'information dans la documentation d'API en fonction du type de savoir qu'ils renferment. À partir des morceaux de savoir digne de recommendation, nous extrayons des patrons de mots, puis utilisons ces patrons pour trouver automatiquement de nouveaux morceaux qui renferment un savoir similaire. Nous présentons les résultats d'une évaluation expérimentale de notre système effectuée à partir de plus de 1 000 morceaux d'API, où nous trouvons que notre système offre de recommendations adéquates 90% du temps avec un taux de rappel de 69%.

Internet applications have recently witnessed tremendous growth in terms of both size and complexity. Cloud computing is one of the several distributed technologies that have emerged to help meeting the objectives of these applications in terms of achieving high availability, performance and scalability.Platform as a Service (PaaS) is one kind of services provided by cloud solutions. These systems often follow a multi-tier architecture consisting mainly of a presentation tier, an application tier and a database tier. The volumes of data exchanged between the application tier and the database tier become huge, especially for enterprise level applications. As a result, the design of the database tier in cloud systems has to carefully address the scalability challenges rising from the huge data volumes. In this thesis, we propose a data distribution approach to improve the scalability of the database tier. Our approach is applied to a traditional single database server. It works by replacing the traditionally used single machine storage paradigm with a distributed storage paradigm. The suggested approach maintains the features that originally exists in the database system, and additionally provides the features of distribution and replication. Distributing the data storage helps improving the system fault-tolerance as it decreases the possibility of having a failure at the database server. It also helps resolve specific performance issues such as reducing the I/O usage and consecutively decreasing the possibility of an I/O bottleneck. Yet, it produces other performance challenges that need to be addressed. To prove the feasibility of our proposed approach, we use it to implement two extensions to the storage manager module of the PostgreSQL database system, using the HDFS distributed file system, and the HBase distributed key-value store. / Les applications Internet ont récemment connu une croissance considérable en termes de taille et de complexité. Afin de satisfaire la forte demande pour les ressources informatiques et les espaces de stockage, les technologies en distribution ont commencé à devenir plus impliquées dans les applications à grande échelle. Le Cloud Computing est l'une de ces nombreuses technologies qui ont émergé pour aider à atteindre les objectifs de ces applications, telles que la haute disponibilité, les performances et l'évolutivité.Platform as a Service (PaaS) est un type de service qui peut être fourni par les solutions de Cloud Computing. Ces systèmes suivent souvent une architecture multi-niveaux qui se compose principalement d'un niveau de présentation, un niveau d'application et d'un niveau de base de données. Les volumes de données échangées entre l'application et la base de données deviennent énormes en particulier pour les applications de niveau entreprise. En conséquence, la conception de la base de données dans les systèmes de Cloud Computing doit prendre en compte le challenge de l'évolution des quantités énormes de données. Dans cette mémoire, nous proposons une approche de distribution des données qui peuvent être utilisées pour améliorer l'évolutivité des bases de données. Nous proposons deux techniques qui peuvent être appliquées à un serveur de base de données unique traditionnelle.Ces techniques fonctionnent en remplaçant le paradigme traditionnel utilisant une seule machine de stockage avec un paradigme de stockage distribué. Les techniques proposées maintiennent les caractéristiques qui existaient à l'origine dans le système de base de données, et en plus fournissent les caractéristiques de la distribution et de la réplication. Ces deux fonctionnalités supplémentaires aident à améliorer le système de tolérance aux pannes, car ils diminuent la possibilité d'avoir une défaillance au niveau du serveur de base de données. La distribution du stockage permet de résoudre les problèmes de performances spécifiques, tels que la réduction de l'utilisation des entrées/sorties et consécutivement de diminuer la possibilité de saturation des entrées/sorties.Par ailleurs, cela produit d'autres défis de performances qui doivent être pris en compte. Pour prouver la faisabilité de nos techniques, nous les avons implémentées comme des extensions du module de gestion de stockage de la base de données PostgreSQL.

Social network analysis is an important cross-disciplinary area of research, with applications in fields such as biology, epidemiology, marketing and even politics. Influence maximization is the problem of finding the set of seed nodes in an information diffusion process that guarantees maximum spread of influence in a social network, given its structure. Most approaches to this problem make two assumptions. First, the global structure of the network is known. Second, influence probabilities between any two nodes are known beforehand, which is rarely the case in practical settings. In this thesis we propose a different approach to the problem of learning those influence probabilities from past data, using only the local structure of the social network. The method is grounded in unsupervised machine learning techniques and is based on a form of hierarchical clustering, allowing us to distinguish between influential and the influenceable nodes. Finally, we provide empirical results using real data extracted from Facebook. / L'analyse des réseaux sociaux est un domaine d'études interdisciplinaires qui comprend des applications en biologie, épidémiologie, marketing et même politique. La maximisation de l'influence représente un problème où l'on doit trouver l'ensemble des noeuds de semence dans un processus de diffusion de l'information qui en même temps garantit le maximum de propagation de son influence dans un réseau social avec une structure connue. La plupart des approches à ce genre de problème font appel à deux hypothèses. Premièrement, la structure générale du réseau social est connue. Deuxièmement, les probabilités des influences entre deux noeuds sont connues à l'avance, fait qui n'est d'ailleurs pas valide dans des circonstances pratiques. Dans cette thèse, on propose un procédé différent visant la problème de l'apprentissage de ces probabilités d'influence à partir des données passées, en utilisant seulement la structure locale du réseau social. Le procédé se base sur l'apprentissage automatique sans surveillance et il est relié à une forme de regroupement hiérarchique, ce qui nous permet de faire la distinction entre les noeuds influenceurs et les noeuds influencés. Finalement, on fournit des résultats empiriques en utilisant des données réelles extraites du réseau social Facebook.

Networked real-time systems (NRSs) are pervasive in the real world, and many of them work in an open environment with varying workload. Quality of service (QoS) of NRSs is closely related to the provision of the system resources for servingthe real-time tasks. To provide guarantees of QoS in NRSs, the system resources should be allocated to the real-time tasks in adaptation to the workload variations so that the desired system performance is obtained, referred to as QoS control.This thesis is concerned with the design of dynamic resource allocation schemes for QoS control in three typical NRSs. In the first part, we propose dynamic computing capacity planning schemes for processor utilization control in the distributed real-time systems, and for energy minimization with request response time guarantees in the server clusters. To handle the workload variations, we model the workload uncertainties as the parameters in the system models and use the system performance as online feedback to predict these parameters as precise as possible. Then the optimal computing capacities are provided to serve the real-time tasks in these systems online. Experimental/simulation results demonstrate effectiveness of the proposed schemes for QoS control in comparisons with the existing approaches. In the second part, we propose a dynamic network scheduling scheme for networked control systems (NCSs), typical NRSs with network bandwidth as a critical system resource. The proposed scheduling scheme can properly allocate the network bandwidth to the applications in NCSs so that the good real-time performance can be achieved. / Les systèmes temps-réel en réseau (NRSs) sont de plus en plus utilisés, et beaucoup d'entre eux fonctionnent dans un environnement ouvert aux charges variables. La Qualité de Service (QoS) des NRSs dépend des ressources systèmes pour répondre aux taches en temps-réel. Pour garantir la QoS, les ressources système doivent être allouées dynamiquement, en s'adaptant aux variations de charge, ceci dans le but d'atteindre les performances désirées.Cette thèse traite de la conceptions de méthodes d'allocation dynamique des ressources dans le but d'assurer la QoS dans le cas de 3 NRSs représentatifs. Nous commencerons pas proposer des méthodes de plannification de capacités pour le contrôle de l'utilisation du processeur dans les systèmes distribués, à coup énergétique minimal, avec temps de réponse garanti. Pour supporter les variations de charge, nous utilisons les performances du système pour prédire l'évolution de la charge à venir aussi précisement que possible. Ensuite, les ressources optimales sont libéréespour répondre aux besoins en temp-réel. Les resultats des expérimentations / simulations démontrent l'efficacité de ces méthodes sur le contrôle de la QoS, en comparaison à d'autres approches existantes. Dans un second temps, nous proposerons une méthodologie de séquençage réseau dynamique pour les systèmes controlés en réseau (NCSs), un NRS commun dépendant fortement de la bande passante du réseau. La méthodologie proposée peut correctement allouer la bande passante aux applications du NCS de sorte que de bonnesperformances soient atteintes.

The organization of DNA in the nucleus of a cell has long been known to play an important role in processes such as DNA replication and repair, and the regulation of gene expression. Recent advances in microarray and high-throughput sequencing technologies have enabled the creation of novel techniques for measuring certain aspects of the three-dimensional conformation of chromatin in vivo. The data generated by these methods contain both structural information and noise from the experimental procedures. Methods for modeling and analyzing these data to infer three-dimensional chromatin structure will constitute invaluable tools in the discovery of the mechanism by which chromatin structure is mediated. The overall objective of my thesis is to develop robust three-dimensional computational models of DNA and to analyze these data to gain biological insight into the role of chromatin structure on cellular processes. This thesis presents three main results, firstly, a novel computational modeling and analysis approach for the inference of three-dimensional structure from chromatin conformation capture carbon copy (5C) and Hi-C data. Our method named MCMC5C is based on Markov chain Monte Carlo sampling and can generate representative ensembles of three-dimensional models from noisy experimental data. Secondly, our investigation of the relationship between chromatin structure and gene expression during cellular differentiation shows that chromatin architecture is a dynamic structure which adopts an open conformation for actively transcribed genes and a condensed conformation for repressed genes. And thirdly, we developed a support vector machine classifier from 5C data and demonstrate a proof-of-concept that chromatin conformation signatures could be used to discriminate between human acute lymphoid and myeloid leukemias. / L'organisation de l'ADN à l'intérieur du noyau d'une cellule est connue pour jouer un rôle important pour des processus tels que la réplication et la réparation de l'ADN et la régulation de l'expression de gènes. Des avancées technologiques récentes concernant les puces à ADN et le séquençage à haut débit ont permis la création de nouvelles techniques mesurant la conformation de la chromatine in vivo. Les données générées par ces méthodes constituent une mesure approximative de la structure de la chromatine. Des méthodes modélisant et analysant ces données afin de déduire la structure tridimensionnelle de la chromatine constitueront des outils précieux pour la découverte du mécanisme gouvernant la structure de la chromatine. L'objectif global de ma thèse est de développer des modèles computationnels analysant la structure tridimensionnelle de l'ADN et d'effectuer l'analyse de données afin de mieux comprendre le rôle de la structure de la chromatine dans divers processus cellulaires. Cette thèse présente trois résultats principaux. Premièrement, un nouvel ensemble d'outils pour la modélisation computationnelle et l'analyse des données provenant de la capture copie conforme de la conformation de la chromatine (5C) et Hi-C. Notre méthode nommée MCMC5C se base sur une méthode de Monte Carlo par chaînes de Markov et peut générer des ensembles de modèles tridimensionnels représentatifs à partir de données expérimentales contenant du bruit. Deuxièmement, notre enquête sur la relation entre la structure de la chromatine et l'expression de gènes durant la différenciation cellulaire démontre que l'architecture de la chromatine est une structure dynamique qui adopte une conformation ouverte pour les gènes activement transcrits et une conformation condensée pour les gènes non-transcrits. Troisièmement, nous avons développé un classifieur basé sur une machine à vecteur de support à partir de nos données 5C et nous avons montré que les signatures de la conformation de la chromatine pourraient être utilisées pour différencier entre la leucémie lymphoïde et myéloïde.