Spelling suggestions: "subject:"échantillonage"" "subject:"echantillonage""
1 |
Acceleration for statistical model checking / Accélérations pour le model checking statistiqueBarbot, Benoît 20 November 2014 (has links)
Ces dernières années, l'analyse de systèmes complexes critiques est devenue de plus en plus importante. En particulier, l'analyse quantitative de tels systèmes est nécessaire afin de pouvoir garantir que leur probabilité d'échec est très faible. La difficulté de l'analyse de ces systèmes réside dans le fait que leur espace d’état est très grand et que la probabilité recherchée est extrêmement petite, de l'ordre d'une chance sur un milliard, ce qui rend les méthodes usuelles inopérantes. Les algorithmes de Model Checking quantitatif sont les algorithmes classiques pour l'analyse de systèmes probabilistes. Ils prennent en entrée le système et son comportement attendu et calculent la probabilité avec laquelle les trajectoires du système correspondent à ce comportement. Ces algorithmes de Model Checking ont été largement étudié depuis leurs créations. Deux familles d'algorithme existent : - le Model Checking numérique qui réduit le problème à la résolution d'un système d'équations. Il permet de calculer précisément des petites probabilités mais soufre du problème d'explosion combinatoire- - le Model Checking statistique basé sur la méthode de Monte-Carlo qui se prête bien à l'analyse de très gros systèmes mais qui ne permet pas de calculer de petite probabilités. La contribution principale de cette thèse est le développement d'une méthode combinant les avantages des deux approches et qui renvoie un résultat sous forme d'intervalles de confiance. Cette méthode s'applique à la fois aux systèmes discrets et continus pour des propriétés bornées ou non bornées temporellement. Cette méthode est basée sur une abstraction du modèle qui est analysée à l'aide de méthodes numériques, puis le résultat de cette analyse est utilisé pour guider une simulation du modèle initial. Ce modèle abstrait doit à la fois être suffisamment petit pour être analysé par des méthodes numériques et suffisamment précis pour guider efficacement la simulation. Dans le cas général, cette abstraction doit être construite par le modélisateur. Cependant, une classe de systèmes probabilistes a été identifiée dans laquelle le modèle abstrait peut être calculé automatiquement. Cette approche a été implémentée dans l'outil Cosmos et des expériences sur des modèles de référence ainsi que sur une étude de cas ont été effectuées, qui montrent l'efficacité de la méthode. Cette approche à été implanté dans l'outils Cosmos et des expériences sur des modèles de référence ainsi que sur une étude de cas on été effectué, qui montre l'efficacité de la méthode. / In the past decades, the analysis of complex critical systems subject to uncertainty has become more and more important. In particular the quantitative analysis of these systems is necessary to guarantee that their probability of failure is very small. As their state space is extremly large and the probability of interest is very small, typically less than one in a billion, classical methods do not apply for such systems. Model Checking algorithms are used for the analysis of probabilistic systems, they take as input the system and its expected behaviour, and compute the probability with which the system behaves as expected. These algorithms have been broadly studied. They can be divided into two main families: Numerical Model Checking and Statistical Model Checking. The former computes small probabilities accurately by solving linear equation systems, but does not scale to very large systems due to the space size explosion problem. The latter is based on Monte Carlo Simulation and scales well to big systems, but cannot deal with small probabilities. The main contribution of this thesis is the design and implementation of a method combining the two approaches and returning a confidence interval of the probability of interest. This method applies to systems with both continuous and discrete time settings for time-bounded and time-unbounded properties. All the variants of this method rely on an abstraction of the model, this abstraction is analysed by a numerical model checker and the result is used to steer Monte Carlo simulations on the initial model. This abstraction should be small enough to be analysed by numerical methods and precise enough to improve the simulation. This abstraction can be build by the modeller, or alternatively a class of systems can be identified in which an abstraction can be automatically computed. This approach has been implemented in the tool Cosmos, and this method was successfully applied on classical benchmarks and a case study.
|
2 |
Relais coopératifs dans un réseau de capteurs : performances limites et stratégies / Cooperative Relaying in sensor network : performances, limits and startegiesBen Nacef, Ahmed 24 November 2011 (has links)
Les réseaux de capteurs ont connu un grand essor ces dix dernières années. Ils interviennent dans tous les domaines de notre vie quotidienne et la rendent plus aisée. Malgré ce grand succès des réseaux de capteurs, plusieurs problèmes restent encore ouverts. La capacité énergétique et la fragilité du canal radio des réseaux de capteurs affectent gravement leurs performances. La communication coopérative représente une solution efficace pour lutter contre l'instabilité du canal radio et afin d'économiser plus d'énergie. Nous proposons dans ce manuscrit, d'utiliser la communication coopérative, en premier lieu, au niveau de la couche MAC afin de mettre en place un accès au canal coopératif et non égoïste. En second lieu, nous utilisons la communication coopérative au niveau de la couche réseau dans le but d'établir des chemins de routage plus stables et plus robustes. / Wireless sensor networks (WSN) have known a great development during the last decade. They intervene in all the domain of our everyday life to make it easier. Despite the success of WSN several problems have to be solved. The restricted energy capacity and the randomness of the wireless channel seriously affect the performances of the WSN. Cooperative communication represents an efficient solution to reduce the instability of the wireless channel and to optimize energy. In this thesis we propose to use cooperative communications at the MAC and network layer in order to set up a cooperative access to the channel and to establish more robust routing paths.
|
3 |
Echantillonnage aléatoire et estimation spectrale de processus et de champs stationnaires / Random sampling and spectral estimation of stationary processes and fieldsKouakou, Kouadio Simplice 14 June 2012 (has links)
Dans ce travail nous nous intéressons à l'estimation de la densité spectrale par la méthode du noyau pour des processus à temps continu et des champs aléatoires observés selon des schémas d'échantillonnage (ou plan d'expériences) discrets aléatoires. Deux types d'échantillonnage aléatoire sont ici considérés : schémas aléatoires dilatés, et schémas aléatoires poissonniens. Aucune condition de gaussiannité n'est imposée aux processus et champs étudiés, les hypothèses concerneront leurs cumulants.En premier nous examinons un échantillonnage aléatoire dilaté utilisé par Hall et Patil (1994) et plus récemment par Matsuda et Yajima (2009) pour l'estimation de la densité spectrale d'un champ gaussien. Nous établissons la convergence en moyenne quadratique dans un cadre plus large, ainsi que la vitesse de convergence de l'estimateur.Ensuite nous appliquons l'échantillonnage aléatoire poissonnien dans deux situations différentes : estimation spectrale d'un processus soumis à un changement de temps aléatoire (variation d'horloge ou gigue), et estimation spectrale d'un champ aléatoire sur R2. Le problème de l'estimation de la densité spectrale d'un processus soumis à un changement de temps est résolu par projection sur la base des vecteurs propres d'opérateurs intégraux définis à partir de la fonction caractéristique de l'accroissement du changement de temps aléatoire. Nous établissons la convergence en moyenne quadratique et le normalité asymptotique de deux estimateurs construits l'un à partir d'une observation continue, et l'autre à partir d'un échantillonnage poissonnien du processus résultant du changement de temps.La dernière partie de ce travail est consacrée au cas d'un champ aléatoire sur R2 observé selon un schéma basé sur deux processus de Poissons indépendants, un pour chaque axe de R2. Les résultats de convergence sont illustrés par des simulations / In this work, we are dealing in the kernel estimation of the spectral density for a continuous time process or random eld observed along random discrete sampling schemes. Here we consider two kind of sampling schemes : random dilated sampling schemes, and Poissonian sampling schemes. There is no gaussian condition for the process or the random eld, the hypotheses apply to their cumulants.First, we consider a dilated sampling scheme introduced by Hall and Patil (1994) and used more recently by Matsuda and Yajima (2009) for the estimation of the spectral density of a Gaussian random eld.We establish the quadratic mean convergence in our more general context, as well as the rate of convergence of the estimator.Next we apply the Poissonian sampling scheme to two different frameworks : to the spectral estimation for a process disturbed by a random clock change (or time jitter), and to the spectral estimation of a random field on R2.The problem of the estimatin of the spectral density of a process disturbed by a clock change is solved with projection on the basis of eigen-vectors of kernel integral operators defined from the characteristic function of the increment of the random clock change. We establish the convergence and the asymptotic normality of two estimators contructed, from a continuous time observation, and the other from a Poissonian sampling scheme observation of the clock changed process.The last part of this work is devoted to random fields on R2 observed along a sampling scheme based on two Poisson processes (one for each axis of R2). The convergence results are illustrated by some simulations
|
4 |
Formes d’onde à saut de fréquences et Compressed Sensing : Application à la détection et à la reconnaissance aéroportées / Step frequency waveforms and compressed sensing : Application to airborne detection and recognitionMesnard, Philippe 28 June 2019 (has links)
Les changements dans le contexte du traitement radar aéroporté impliquent de plus en plus d'améliorations qui justifient la recherche d'une alternative au filtrage adapté, qui est le processus utilisé classiquement pour estimer les paramètres des cibles détectées. Le Compressed Sensing ouvre la perspective d'un nouveau traitement, également efficace dans les configurations de cibles multiples, avec de meilleures performances de suivi et de reconnaissance que l'approche classique. Nous cherchons à appliquer ce traitement aux formes d'onde dites à évasion de fréquence. Le choix intégral des paramètres de définition du signal transmis déterminee entièrement la matrice de mesure de la procédure du Compressed Sensing, laquelle solution fournit toutes les informations recherchées sur la scène observée. Pour chaque signal à évasion de fréquence, et d'amplitude constante, la matrice de mesure correspondante est obtenue en extrayant certaines lignes d'une matrice de Fourier étendue particulière, la matrice de Fourier 2D. La construction de la génération de la matrice de mesure est importante car le succès de la reconstruction dépend des propriétés algébriques de cette matrice. / Changes in the context of airborne radar processing implie more and more improvements that justify to look for an alternative to Matched Filtering, the process conventionally used to estimate the parameters of detected targets. Compressed Sensing suggests a new treatment, also performing in multi-target cases, with better tracking and recognition performances than classical approach. We seek to apply this treatment to step frequency waveforms. The whole choice of definition parameters for the transmitted signal entirely builds the measurement matrix of the Compressed Sensing procedure which solution gives all the sought information of the observed scene. For each step frequency signal with constant amplitude, the resulting measurement matrix is obtained by extracting some lines from a particular extended Fourier matrix, the 2D Fourier matrix. The construction of the measurement matrix generation is important since the success of the reconstruction depends on the algebraic properties of this matrix.
|
5 |
Modélisation d'un bassin d'orage en vue de l'amélioration de la qualité des rivières par la gestion en temps réelVallet, Bertrand Sébastien 18 April 2018 (has links)
Pour permettre l’amélioration de l’écohydraulique des rivières en temps de pluie, le développement de règles de contrôle en temps réel de vannes placées à la sortie de bassins d’orage demande une analyse à long terme de différentes options, intégrant la prévision météorologique, la qualité de l’eau de la rivière à l’amont du rejet, le débit de la rivière et la qualité de l’eau dans le bassin d’orage, pour permettre l’amélioration de l’écohydraulique des rivières. Pour cela, l’idéal est de tester ces règles à l’aide d’un modèle intégré du système « bassin versant – bassin d’orage – rivière ». Pour pouvoir faire des simulations à long terme, il faut un modèle de bassin d’orage rapide, qui permette de simuler la qualité de l’eau dans le bassin de façon précise quelles que soient les conditions d’exploitation. L’objet de cette thèse de doctorat a été de développer ce modèle de bassin d’orage. Ce modèle se base sur le principe de couches complètement mélangées superposées permettant de créer un gradient de concentrations pour représenter des phénomènes locaux tel que la pénétration de la lumière influençant la mortalité des pathogènes. Il se base également sur la définition de plusieurs classes de particules caractérisées par leurs vitesses de sédimentation, ces dernières étant déterminées expérimentalement à l’aide de tests ViCAs. Il incorpore également des polluants associés aux particules. L’élément de base, nommé cellule, est défini par une surface et une hauteur maximale au-delà de laquelle il y a débordement. Chaque cellule possède un volume d’eau variable dans le temps, divisé en plusieurs couches superposées, et d’une couche de sédiment de volume constant dans le temps. Pour reproduire le volume d’un bassin d’étude, il est nécessaire de connecter plusieurs cellules les unes avec les autres. Ces connexions se font alors couche à couche ayant comme conditions que les niveaux d’eau de toutes les cellules soient à la même hauteur. Un modèle théorique d’évolution des concentrations en pathogènes incluant des processus complexes comme la croissance, l’adsorption sur les particules et la désinfection par la lumière a également été développé. Le calage du modèle a nécessité la collecte de données expérimentales; des campagnes de mesure ont été effectuées lors des étés 2008, 2009 et 2010 sur le bassin Chauveau de l’arrondissement des Rivières de la ville de Québec. Dans un premier temps, l’efficacité du bassin dans son fonctionnement actuel a été déterminée. Une efficacité moyenne d’épuration de 39% sur les matières en suspension (MeS), de 10% sur l’azote ammoniacal et de 20 % sur le zinc a été mise en évidence. Dans un deuxième temps, la sortie du bassin a été fermée à l’aide d’une structure de bois avec une porte guillotine permettant la rétention de l’eau pendant des durées variables. Cette deuxième configuration du bassin a permis d’améliorer l’efficacité du bassin de façon très importante pour les MeS (90%), l’azote ammoniacal (84%) et le zinc (42%). Des prélèvements ponctuels ont également été faits à l’intérieur du bassin, révélant une hétérogénéité des mesures en MeS entre la zone proche de l’entrée et la zone proche de la sortie, durant les 20 premières heures d’emmagasinement. Le modèle a montré sa capacité à reproduire le comportement de la concentration en matières en suspension à l’aide de 3 classes de particules associées à des vitesses de sédimentation de 80, 2 et 0.1 m/d. La représentation hydraulique du modèle a nécessité l’emploi de 5 cellules pour recréer l’hétérogénéité spatiale révélée par les campagnes d’échantillonnage. Finalement, une fonction de débit de resuspension a permis de modéliser les concentrations à la sortie du bassin d’orage. La validation a confirmé les bonnes performances du modèle pour l’hydraulique et la prédiction des matières en suspension en sortie de bassin. Elle a néanmoins révélé plusieurs points qui nécessiteraient des recherches plus approfondies : la définition du débit de resuspension des sédiments, la détermination de la masse initiale de sédiments dans le bassin, la possibilité d’utiliser plus de cellules pour mieux représenter le comportement hydraulique et l’intérêt de collecter des analyses ViCAs associés à chaque phase du pollutogramme de la pluie (début, pic de débit et fin). Avec ce modèle, les stratégies de gestion en temps réel de la vanne de sortie des bassins d’orage peuvent maintenant être déterminées. / The development of real-time control rules of sluice gates located at a stormwater basin outlet requires testing various options, taking in account weather forecasts, water quality of the upstream river, river flow and water quality in the stormwater basin, by using long-term simulations to allow improved ecohydraulics of rivers. To do so, these rules have to be tested by using an integrated “watershed - storm basin – river” system. In order to perform long-term simulations, a stormwater basin model with small computation time is needed, which simulates the water quality in the basin accurately in function of imposed operating conditions. The purpose of this thesis was to develop such stormwater basin model. The developed model is based on superimposed homogeneous layers creating a concentration gradient to represent local phenomena such as light penetration affecting the mortality of pathogens. It is also based on the definition of several particle classes characterized by their settling velocities; the latter being determined experimentally using ViCAs tests. It also includes pollutants associated with particles. The basic unit, called cell, is defined by a surface and a maximum height above which water overflows. Each cell has a time-variable water volume, divided into several layers and a constant volume sediment layer. To reproduce spatial heterogeneity of an experimental stormwater basin, it is necessary to connect several cells. Connections are then done layer by layer with the condition that the water levels of all cells are at the same water height. A theoretical model describing the concentrations of pathogens, including complex processes such as growth, adsorption on particles and light disinfection has also been developed The calibration of the model required experimental data which were collected by sampling in the summers of 2008, 2009 and 2010 on the basin Chauveau in the “des Rivières” district of Quebec City. First, the efficiency of the basin in its current operation was determined. An average removal efficiency of 39% for total suspended solids (TSS), 10% for ammonia and 20% for zinc was revealed. In a second step, the stormwater basin outlet was closed with a wooden structure equipped with a guillotine door to retain the water for varying periods of time. The second configuration of the basin significantly improved the efficiency of the basin for TSS (90%), ammonia (84%) and zinc (42%). Samples were also collected within the basin, revealing heterogeneity in TSS measurements between the area near the inlet and the area near the outlet for the first 20 hours of storage. The model showed its ability to adequately reproduce the behavior of the TSS concentrations using three particle classes defined by settling velocities of 80, 2 and 0.1 m/d. For the hydraulics, five cells were required to recreate the spatial heterogeneity revealed by the sampling campaigns. Finally, the addition of a resuspension flowrate was needed to model the increased outlet TSS concentrations at the end of emptying. The validation confirmed the good performance of the model for the hydraulics and the prediction of outlet TSS concentration. It has also revealed several points that require further research: the definition of the sediment resuspension flowrate, determination of the initial mass of sediments in the stormwater basin, the possibility of using more cells to better represent the hydraulics and the interest of running ViCAs tests associated with each phase of the runoff (the beginning, the flow peak and the end). With this model, real-time control strategies for the outlet valve can now be tested.
|
6 |
BetaSAC et OABSAC, deux nouveaux 'echantillonnages conditionnels pour RANSACMéler, Antoine 31 January 2013 (has links) (PDF)
L'algorithme RANSAC est l'approche la plus commune pour l'estimation robuste des paramètres d'un modèle en vision par ordinateur. C'est principalement sa capacité à traiter des données contenant potentiellement plus d'erreurs que d'information utile qui fait son succès dans ce domaine où les capteurs fournissent une information très riche mais très difficilement exploitable. Depuis sa création, il y a trente ans, de nombreuses modifications ont été proposées pour améliorer sa vitesse, sa précision ou sa robustesse. Dans ce travail, nous proposons d'accélérer la résolution d'un problème par RANSAC en utilisant plus d'information que les approches habituelles. Cette information, calculée à partir des données elles-même ou provenant de sources complémentaires de tous types, nous permet d'aider RANSAC à générer des hypothèses plus pertinentes. Pour ce faire, nous proposons de distinguer quatre degrés de qualité d'une hypothèse: la "non contamination", la "cohésion", la "cohérence" et enfin la "pertinence". Puis nous montrons à quel point une hypothèse non contaminée par des données erronées est loin d'être pertinente dans le cas général. Dès lors, nous nous attachons à concevoir un algorithme original qui, contrairement aux méthodes de l'état de l'art, se focalise sur la génération d'échantillons "pertinents" plutôt que simplement "non contaminés". Notre approche consiste à commencer par proposer un modèle probabiliste unifiant l'ensemble des méthodes de réordonnancement de l'échantillonnage de RANSAC. Ces méthodes assurent un guidage du tirage aléatoire des données tout en se prémunissant d'une mise en échec de RANSAC. Puis, nous proposons notre propre algorithme d'ordonnancement, BetaSAC, basé sur des tris conditionnels partiels. Nous montrons que la conditionnalité du tri permet de satisfaire des contraintes de cohérence des échantillons formés, menant à une génération d'échantillons pertinents dans les premières itérations de RANSAC, et donc à une résolution rapide du problème. L'utilisation de tris partiels plutôt qu'exhaustifs, quant à lui, assure la rapidité et la randomisation, indispensable à ce type de méthodes. Dans un second temps, nous proposons une version optimale de notre méthode, que l'on appelle OABSAC (pour Optimal and Adaptative BetaSAC), faisant intervenir une phase d'apprentissage hors ligne. Cet apprentissage a pour but de mesurer les propriétés caractéristiques du problème spécifique que l'on souhaite résoudre, de façon à établir automatiquement le paramétrage optimal de notre algorithme. Ce paramétrage est celui qui doit mener à une estimation suffisamment précise des paramètres du modèle recherché en un temps (en secondes) le plus court. Les deux méthodes proposées sont des solutions très générales qui permettent d'intégrer dans RANSAC tout type d'information complémentaire utile à la résolution du problème. Nous montrons l'avantage de ces méthodes pour le problème de l'estimation d'homographies et de géométries épipolaires entre deux photographies d'une même scène. Les gains en vitesse de résolution du problème peuvent atteindre un facteur cent par rapport à l'algorithme RANSAC classique.
|
7 |
Développement d'un modèle particulaire pour la régression indirecte non paramétrique / Development of a particle-based model for nonparametric inverse regressionNaulet, Zacharie 08 November 2016 (has links)
Cette thèse porte sur les statistiques bayésiennes non paramétriques. La thèse est divisée en une introduction générale et trois parties traitant des aspects relativement différents des approches par mélanges (échantillonage, asymptotique, problème inverse). Dans les modèles de mélanges, le paramètre à inférer depuis les données est une fonction. On définit une distribution a priori sur un espace fonctionnel abstrait au travers d'une intégrale stochastique d'un noyau par rapport à une mesure aléatoire. Habituellement, les modèles de mélanges sont surtout utilisés dans les problèmes d'estimation de densités de probabilité. Une des contributions de ce manuscrit est d'élargir leur usage aux problèmes de régressions.Dans ce contexte, on est essentiellement concernés par les problèmes suivants:- Echantillonage de la distribution a posteriori- Propriétés asymptotiques de la distribution a posteriori- Problèmes inverses, et particulièrement l'estimation de la distribution de Wigner à partir de mesures de Tomographie Quantique Homodyne. / This dissertation deals with Bayesian nonparametric statistics, in particular nonparametric mixture models. The manuscript is divided into a general introduction and three parts on rather different aspects of mixtures approaches (sampling, asymptotic, inverse problem). In mixture models, the parameter to infer from the data is a function. We set a prior distribution on an abstract space of functions through a stochastic integral of a kernel with respect to a random measure. Usually, mixture models were used primilary in probability density function estimation problems. One of the contributions of the present manuscript is to use them in regression problems.In this context, we are essentially concerned with the following problems :- Sampling of the posterior distribution- Asymptotic properties of the posterior distribution- Inverse problems, in particular the estimation of the Wigner distribution from Quantum Homodyne Tomography measurements.
|
8 |
Non-redundant sampling in RNA Bioinformatics / Echantillonage sans remise en Bioinformatique des Acides RiboNucléiquesMichalik, Juraj 29 March 2019 (has links)
Un échantillonnage statistique est central à de nombreuses méthodes algorithmiques pour la bioinformatique structurale des ARNs, où ils sont couramment utilisés pour identifier des modèles structuraux importants, fournir des résumés des espaces de repliement ou approcher des quantités d'intérêt dans l'équilibre thermodynamique. Dans tous ces exemples, la redondance dans l'ensemble échantillonné est non-informative et inefficace, limitant la portée des applications des méthodes existantes. Dans cette thèse, nous introduisons le concept de l'échantillonnage non-redondante et nous explorons ses applications et conséquences en bioinformatique des ARN.Nous commençons par introduire formellement le concept d'échantillonnage non-redondante et nous démontrons que tout algorithme échantillonnant dans la distribution de Boltzmann peut être modifié en une version non-redondante. Son implémentation repose sur une structure de données spécifique et la modification d'une remontée stochastique pour fournir l'ensemble des structures uniques, avec la même complexité.Nous montrons alors une exemple pratique en implémentant le principe d'échantillonnage non-redondant au sein d'un algorithme combinatoire qui échantillonne des structures localement optimales. Nous exploitons cet outil pour étudier la cinétique des ARN, modélisant des espaces de repliement générés à partir des structures localement optimales. Ces structures agissent comme des pièges cinétiques, rendant leur prise en compte essentielle pour analyser la dynamique des ARN. Des résultats empirique montrent que des espaces de repliement générés à partir des échantillons non-redondants sont plus proches de la réalité que ceux obtenus par un échantillonnage classique.Nous considérons ensuite le problème du calcul efficace d'estimateurs statistiques à partir d'échantillons non redondants. L'absence de la redondance signifie que l'estimateur naïf, obtenu en moyennant des quantités observés dans l'échantillon, est erroné. Par contre, nous établissons un estimateur non-trivial non-biaisé spécifique aux échantillons non-redondants suivant la distribution de Boltzmann. Nous montrons que l'estimateur des échantillons non-redondants est plus efficace que l'estimateur naïf, notamment dans les cas où la majorité des l'espace de recherche est échantillonné.Finalement, nous introduisons l'algorithme d'échantillonnage, avec sa contre-partie non-redondante, pour des structures secondaires présentant des pseudonoeuds de type simple. Des pseudonoeuds sont typiquement omis pour des raisons d'efficacité, bien que beaucoup d'entre eux possèdent une grande importance biologique. Nos commençons par proposer une schéma de programmation dynamique qui permet d'énumérer tous les pseudonoeuds composés de deux hélices pouvant contenir des bases non-appariés qui s'entrecroisent. Ce schéma généralise la proposition de Reeders et Giegerich, choisi pour sa base complexité temporelle et spatiale. Par la suite, nous expliquons comment adapter cette décomposition à un algorithme d'échantillonnage statistique pour des pseudonoeuds simples. Finalement, nous présentons des résultats préliminaires et nous discutons sur l'extension de principe non-redondant dnas ce contexte.Le travail présenté dans cette thèse ouvre non seulement la porte à l'analyse cinétique des séquences d'ARN plus longues, mais aussi l'analyse structurale plus détaillée des séquences d'ARN en général. L'échantillonnage non-redondant peut être employé pour analyser des espaces de recherche pour des problèmes combinatoires susceptibles à l'échantillonnage statistique, y inclus virtuellement tous problèmes solvables par la programmation dynamique. Les principes d'échantillonnage non-redondant sont robustes et typiquement faciles à implémenter, comme démontré par l'inclusion d'échantillonnage non-redondant dans les versions récentes de Vienna package populaire. / Sampling methods are central to many algorithmic methods in structural RNA bioinformatics, where they are routinely used to identify important structural models, provide summarized pictures of the folding landscapes, or approximate quantities of interest at the thermodynamic equilibrium.In all of these examples, redundancy within sampled sets is uninformative and computationally wasteful, limiting the scope of application of existing methods.In this thesis, we introduce the concept of non-redundant sampling, and explore its applications and consequences in RNA bioinformatics.We begin by formally introducing the concept of non-redundant sampling and demonstrate that any algorithm sampling in Boltzmann distribution can be modified into non-redundant variant. Its implementation relies on a specific data structure and a modification of the stochastic backtrack to return the set of unique structures, with the same complexity.We then show a practical example by implementing the non-redundant principle into a combinatorial algorithm that samples locally optimal structures. We use this tool to study the RNA kinetics by modeling the folding landscapes generated from sets of locally optimal structures. These structures act as kinetic traps, influencing the outcome of the RNA kinetics, thus making their presence crucial. Empirical results show that the landscapes generated from the non-redundant samples are closer to the reality than those obtained by classic approaches.We follow by addressing the problem of the efficient computation of the statistical estimates from non-redundant sampling sets. The absence of redundancy means that the naive estimator, obtained by averaging quantities observed in a sample, is erroneous. However we establish a non-trivial unbiased estimator specific to a set of unique Boltzmann distributed secondary structures. We show that the non-redundant sampling estimator performs better than the naive counterpart in most cases, specifically where most of the search space is covered by the sampling.Finally, we introduce a sampling algorithm, along with its non-redundant counterpart, for secondary structures featuring simple-type pseudoknots. Pseudoknots are typically omitted due to complexity reasons, yet many of them have biological relevance. We begin by proposing a dynamic programming scheme that allows to enumerate all recursive pseudoknots consisting of two crossing helices, possibly containing unpaired bases. This scheme generalizes the one proposed by Reeders and Giegerich, chosen for its low time and space complexities. We then explain how to adapt this decomposition into a statistical sampling algorithm for simple pseudoknots. We then present preliminary results, and discuss about extensions of the non-redundant principle in this context.The work presented in this thesis not only opens the door towards kinetics analysis for longer RNA sequences, but also more detailed structural analysis of RNAs in general. Non-redundant sampling can be applied to analyze search spaces for combinatorial problems amenable to statistical sampling, including virtually any problem solved by dynamic programming. Non-redundant sampling principles are robust and typically easy to implement, as demonstrated by the inclusion of non-redundant sampling in recent versions of the popular Vienna package.
|
9 |
Modélisation de la contamination par Listeria monocytogenes pour l'amélioration de la surveillance dans les industries agro-alimentaires / Contamination modeling of Listeria monocytogenes to improve surveillance in food industryCommeau, Natalie 04 June 2012 (has links)
Les industriels du secteur agro-alimentaire sont responsables de la qualité des produits mis sur le marché. Un moyen de vérifier cette qualité consiste à déterminer la distribution de la contamination. Dans cette thèse, nous avons utilisé des données portant sur L. monocytogenes durant le procédé de fabrication de lardons et du saumon fumé. Nous avons ensuite élaboré des modèles hiérarchiques pour décrire la concentration en prenant ou non en compte diverses variabilités, nous avons estimé les paramètres par inférence bayésienne, puis comparé leur capacité à simuler des données proches des observations. Nous avons également comparé l'estimation de paramètres par inférence fréquentiste sur deux modèles en utilisant les données brutes issues des analyses microbiologiques et ces mêmes données converties en concentration. Par ailleurs, nous avons amélioré un modèle décrivant le devenir de L. monocytogenes au cours de la fabrication des lardons. Le plan d'échantillonnage permettant d'estimer la qualité des produits, nous avons appliqué la théorie de la décision aux couples L. monocytogenes/lardons et L. monocytogenes/saumon fumé en sortie usine pour déterminer la taille optimale de l'échantillon à prélever par lot de manière à minimiser les coûts moyens supportés par le fabricant. Enfin, nous avons comparé plusieurs plans d'échantillonnage de mesure de la température d'un plat en sauce fabriqué dans une cuisine centrale et placé dans une cellule de refroidissement rapide. L'objectif était de sélectionner le meilleur plan d'échantillonnage en fonction du risque admissible pour le gestionnaire quant à la croissance de C. perfringens. / Food business operators are responsible for the quality of the products they sell. A way to assess the safety of food is to determine the contamination distribution. During my PhD thesis, we used data about L. monocytogenes during the process of diced bacon and of cold smoked salmon. Then, we constructed several hierarchical models to describe contamination taking or not into account several kinds of variability such as between batches variability. We compared the capacity of each model to simulate data close to the observed ones. We also compared the parameters assessment by frequentist inference using raw data (the results of the microbiological analyses) and concentration-like data. In addition to the models describing the contamination at one step of the process, we improved an existing model describing the fate of L. monocytogenes throughout the diced bacon process. A tool to assess the quality of a product is the sampling plan. We applied the Bayesian theory of decision to the pairs L. monocytogenes/diced bacon and L. monocytogenes/cold smoked salmon at the end of the process to determine the optimal size of a sample analysed per batch so that the average cost for the manufacturer is as los as possible. We also compared several sampling plans of temperature measurement of a meal cooked in an institutional food service facility and put in a blast-chiller just after cooking. The aim was to select the best sampling plan regarding the risk of C. perfringens growth that the manager is ready to take.
|
10 |
Modélisation de la contamination par Listeria monocytogenes pour l'amélioration de la surveillance dans les industries agro-alimentairesCommeau, Natalie 04 June 2012 (has links) (PDF)
Les industriels du secteur agro-alimentaire sont responsables de la qualité des produits mis sur le marché. Un moyen de vérifier cette qualité consiste à déterminer la distribution de la contamination. Dans cette thèse, nous avons utilisé des données portant sur L. monocytogenes durant le procédé de fabrication de lardons et du saumon fumé. Nous avons ensuite élaboré des modèles hiérarchiques pour décrire la concentration en prenant ou non en compte diverses variabilités, nous avons estimé les paramètres par inférence bayésienne, puis comparé leur capacité à simuler des données proches des observations. Nous avons également comparé l'estimation de paramètres par inférence fréquentiste sur deux modèles en utilisant les données brutes issues des analyses microbiologiques et ces mêmes données converties en concentration. Par ailleurs, nous avons amélioré un modèle décrivant le devenir de L. monocytogenes au cours de la fabrication des lardons. Le plan d'échantillonnage permettant d'estimer la qualité des produits, nous avons appliqué la théorie de la décision aux couples L. monocytogenes/lardons et L. monocytogenes/saumon fumé en sortie usine pour déterminer la taille optimale de l'échantillon à prélever par lot de manière à minimiser les coûts moyens supportés par le fabricant. Enfin, nous avons comparé plusieurs plans d'échantillonnage de mesure de la température d'un plat en sauce fabriqué dans une cuisine centrale et placé dans une cellule de refroidissement rapide. L'objectif était de sélectionner le meilleur plan d'échantillonnage en fonction du risque admissible pour le gestionnaire quant à la croissance de C. perfringens.
|
Page generated in 0.5858 seconds