Hard instances of algorithms and proof systems

"Vegeu el resum a l'inici del document del fitxer adjunt."

THE USE OF SIMULATIONS IN EVOLUTIONARY POPULATION GENETICS: APPLICATIONS ON HUMANS, OWLS AND VIRTUAL ORGANISMS

Summary (in English) Computer simulations provide a practical way to address scientific questions that would be otherwise intractable. In evolutionary biology, and in population genetics in particular, the investigation of evolutionary processes frequently involves the implementation of complex models, making simulations a particularly valuable tool in the area. In this thesis work, I explored three questions involving the geographical range expansion of populations, taking advantage of spatially explicit simulations coupled with approximate Bayesian computation. First, the neutral evolutionary history of the human spread around the world was investigated, leading to a surprisingly simple model: A straightforward diffusion process of migrations from east Africa throughout a world map with homogeneous landmasses replicated to very large extent the complex patterns observed in real human populations, suggesting a more continuous (as opposed to structured) view of the distribution of modern human genetic diversity, which may play a better role as a base model for further studies. Second, the postglacial evolution of the European barn owl, with the formation of a remarkable coat-color cline, was inspected with two rounds of simulations: (i) determine the demographic background history and (ii) test the probability of a phenotypic cline, like the one observed in the natural populations, to appear without natural selection. We verified that the modern barn owl population originated from a single Iberian refugium and that they formed their color cline, not due to neutral evolution, but with the necessary participation of selection. The third and last part of this thesis refers to a simulation-only study inspired by the barn owl case above. In this chapter, we showed that selection is, indeed, effective during range expansions and that it leaves a distinguished signature, which can then be used to detect and measure natural selection in range-expanding populations. Résumé (en français) Les simulations fournissent un moyen pratique pour répondre à des questions scientifiques qui seraient inabordable autrement. En génétique des populations, l'étude des processus évolutifs implique souvent la mise en oeuvre de modèles complexes, et les simulations sont un outil particulièrement précieux dans ce domaine. Dans cette thèse, j'ai exploré trois questions en utilisant des simulations spatialement explicites dans un cadre de calculs Bayésiens approximés (approximate Bayesian computation : ABC). Tout d'abord, l'histoire de la colonisation humaine mondiale et de l'évolution de parties neutres du génome a été étudiée grâce à un modèle étonnement simple. Un processus de diffusion des migrants de l'Afrique orientale à travers un monde avec des masses terrestres homogènes a reproduit, dans une très large mesure, les signatures génétiques complexes observées dans les populations humaines réelles. Un tel modèle continu (opposé à un modèle structuré en populations) pourrait être très utile comme modèle de base dans l'étude de génétique humaine à l'avenir. Deuxièmement, l'évolution postglaciaire d'un gradient de couleur chez l'Effraie des clocher (Tyto alba) Européenne, a été examiné avec deux séries de simulations pour : (i) déterminer l'histoire démographique de base et (ii) tester la probabilité qu'un gradient phénotypique, tel qu'observé dans les populations naturelles puisse apparaître sans sélection naturelle. Nous avons montré que la population actuelle des chouettes est sortie d'un unique refuge ibérique et que le gradient de couleur ne peux pas s'être formé de manière neutre (sans l'action de la sélection naturelle). La troisième partie de cette thèse se réfère à une étude par simulations inspirée par l'étude de l'Effraie. Dans ce dernier chapitre, nous avons montré que la sélection est, en effet, aussi efficace dans les cas d'expansion d'aire de distribution et qu'elle laisse une signature unique, qui peut être utilisée pour la détecter et estimer sa force.

Approximation algorithms for two-state anti-ferromagnetic spin systems on bounded degree graphs

In a seminal paper [10], Weitz gave a deterministic fully polynomial approximation scheme for counting exponentially weighted independent sets (which is the same as approximating the partition function of the hard-core model from statistical physics) in graphs of degree at most d, up to the critical activity for the uniqueness of the Gibbs measure on the innite d-regular tree. ore recently Sly [8] (see also [1]) showed that this is optimal in the sense that if here is an FPRAS for the hard-core partition function on graphs of maximum egree d for activities larger than the critical activity on the innite d-regular ree then NP = RP. In this paper we extend Weitz's approach to derive a deterministic fully polynomial approximation scheme for the partition function of general two-state anti-ferromagnetic spin systems on graphs of maximum degree d, up to the corresponding critical point on the d-regular tree. The main ingredient of our result is a proof that for two-state anti-ferromagnetic spin systems on the d-regular tree, weak spatial mixing implies strong spatial mixing. his in turn uses a message-decay argument which extends a similar approach proposed recently for the hard-core model by Restrepo et al [7] to the case of general two-state anti-ferromagnetic spin systems.

Molecular genetics of "PRPF31" dominant mutations linked to retinitis pigmentosa

ABSTRACT : The retina is one of the most important human sensory tissues since it detects and transmits all visual information from the outside world to the brain. Retinitis pigmentosa (RP) is the name given to a group of inherited diseases that affect specifically the photoreceptors present in the retina and in many instances lead to blindness. Dominant mutations in PRPF31, a gene that encodes for a pre-mRNA splicing factor, cause retinitis pigmentosa with reduced penetrance. We functionally investigated a novel mutation, identified in a large family with autosomal dominant RP, and 7 other mutations, substitutions and microdeletions, in 12 patients from 7 families with PRPF31-linked RP. Seven mutations lead to PRPF31 mRNA with premature stop codons and one to mRNA lacking the exon containing the initiation codon. Quantification of PRPF31 mRNA and protein levels revealed a significant reduction in cell lines derived from patients, compared to non carriers of mutations in PRPF31. Allelic quantification of PRPF31 mRNA indicated that the level of mutated mRNA is very low compared to wild-type mRNA. No mutant protein was detected and the subnuclear localization of wild-type PRPF31 remains the same in cell lines from patients and controls. Blocking nonsense-mediated mRNA decay in cell lines derived from patients partially restored PRPF31 mutated mRNA but derived proteins were still undetectable, even when protein degradation pathways were inhibited. Our results demonstrated that the vast majority of PRPF31 mutations result in null alleles, since they are subject to surveillance mechanisms that degrade mutated mRNA and possibly block its translation. Altogether, these data indicate that the likely cause of PRPF31-linked RP is haploinsufficiency, rather than a dominant negative effect. Penetrance of PRPF31 mutations has been previously demonstrated to be inversely correlated with the level of PRPF31 mRNA, since high expression of wild-type PRPF31 mRNA protects from the disease. Consequently, we have investigated the genetic modifiers that control the expression of PRPF31 by quantifying PRPF31 mRNA levels in cell lines derived from 200 individuals from 15 families representative of the general population. By linkage analyses we identified a 8.2Mb-region on chromosome 14q21-23 that contains a gene involved in the modulation of PRPF31 expression. We also assessed apreviously-mapped penetrance factor invariably located on the wild-type allele and linked to the PRPF31 locus in asymptomatic patients from different families with RP. We demonstrated that this modifier increases the expression of both PRPF31 alleles already at the pre-mRNA level. Finally, our data suggest that PRPF31 mRNA expression and consequently the penetrance of PRPF31 mutations is modulated by at least 2 diffusible compounds, which act on both PRPF31 alleles during their transcription.

Synchronous versus asynchronous modeling of gene regulatory networks.

MOTIVATION: In silico modeling of gene regulatory networks has gained some momentum recently due to increased interest in analyzing the dynamics of biological systems. This has been further facilitated by the increasing availability of experimental data on gene-gene, protein-protein and gene-protein interactions. The two dynamical properties that are often experimentally testable are perturbations and stable steady states. Although a lot of work has been done on the identification of steady states, not much work has been reported on in silico modeling of cellular differentiation processes. RESULTS: In this manuscript, we provide algorithms based on reduced ordered binary decision diagrams (ROBDDs) for Boolean modeling of gene regulatory networks. Algorithms for synchronous and asynchronous transition models have been proposed and their corresponding computational properties have been analyzed. These algorithms allow users to compute cyclic attractors of large networks that are currently not feasible using existing software. Hereby we provide a framework to analyze the effect of multiple gene perturbation protocols, and their effect on cell differentiation processes. These algorithms were validated on the T-helper model showing the correct steady state identification and Th1-Th2 cellular differentiation process. AVAILABILITY: The software binaries for Windows and Linux platforms can be downloaded from http://si2.epfl.ch/~garg/genysis.html.

Narcolepsy and familial advanced sleep-phase syndrome: molecular genetics of sleep disorders.

Sleep disorders are very prevalent and represent an emerging worldwide epidemic. However, research into the molecular genetics of sleep disorders remains surprisingly one of the least active fields. Nevertheless, rapid progress is being made in several prototypical disorders, leading recently to the identification of the molecular pathways underlying narcolepsy and familial advanced sleep-phase syndrome. Since the first reports of spontaneous and induced loss-of-function mutations leading to hypocretin deficiency in human and animal models of narcolepsy, the role of this novel neurotransmission pathway in sleep and several other behaviors has gained extensive interest. Also, very recent studies using an animal model of familial advanced sleep-phase syndrome shed new light on the regulation of circadian rhythms.

A modular approach for integrative analysis of large-scale gene-expression and drug-response data

High-throughput technologies are now used to generate more than one type of data from the same biological samples. To properly integrate such data, we propose using co-modules, which describe coherent patterns across paired data sets, and conceive several modular methods for their identification. We first test these methods using in silico data, demonstrating that the integrative scheme of our Ping-Pong Algorithm uncovers drug-gene associations more accurately when considering noisy or complex data. Second, we provide an extensive comparative study using the gene-expression and drug-response data from the NCI-60 cell lines. Using information from the DrugBank and the Connectivity Map databases we show that the Ping-Pong Algorithm predicts drug-gene associations significantly better than other methods. Co-modules provide insights into possible mechanisms of action for a wide range of drugs and suggest new targets for therapy

Extreme Precipitation Modelling Using Geostatistics and Machine Learning Algorithms

The paper presents an approach for mapping of precipitation data. The main goal is to perform spatial predictions and simulations of precipitation fields using geostatistical methods (ordinary kriging, kriging with external drift) as well as machine learning algorithms (neural networks). More practically, the objective is to reproduce simultaneously both the spatial patterns and the extreme values. This objective is best reached by models integrating geostatistics and machine learning algorithms. To demonstrate how such models work, two case studies have been considered: first, a 2-day accumulation of heavy precipitation and second, a 6-day accumulation of extreme orographic precipitation. The first example is used to compare the performance of two optimization algorithms (conjugate gradients and Levenberg-Marquardt) of a neural network for the reproduction of extreme values. Hybrid models, which combine geostatistical and machine learning algorithms, are also treated in this context. The second dataset is used to analyze the contribution of radar Doppler imagery when used as external drift or as input in the models (kriging with external drift and neural networks). Model assessment is carried out by comparing independent validation errors as well as analyzing data patterns.

Directory of Familial Cancer Genetics Specialist Teams

The Directory of Familial Cancer Genetics Specialist Teams has been produced under the auspices of the Northern Ireland Regional Advisory Committee on Cancer. It contains details of the full membership of the clinical teams providing care in each of Health and Social Services Board Area. Lead Clinicians for Familial Cancer Genetics Service (PDF 58 KB) Eastern (PDF 68 KB) Northern (PDF 61 KB) Southern (PDF 62 KB) Western (PDF 11 KB) The Directory will be updated on an annual basis. Please e-mail amendments to:- irene.wilkinson@dhsspsni.gov.uk

Genetics of sleep.

Molecular and genetic approaches in several species have provided new insights into the mechanisms of rest-activity and sleep-wake regulation. Many of these discoveries are believed to support hypotheses about sleep functions, which nevertheless remain elusive. In this review we discuss the specific contribution of both mammalian and invertebrate models to our understanding of the molecular basis of sleep.

Optimització d'una aplicacio bioinformàtica d'alineament de seqüències executada en processadors multi-core i many-core (GPUs)

Las aplicaciones de alineamiento de secuencias son una herramienta importante para la comunidad científica. Estas aplicaciones bioinformáticas son usadas en muchos campos distintos como pueden ser la medicina, la biología, la farmacología, la genética, etc. A día de hoy los algoritmos de alineamiento de secuencias tienen una complejidad elevada y cada día tienen que manejar un volumen de datos más grande. Por esta razón se deben buscar alternativas para que estas aplicaciones sean capaces de manejar el aumento de tamaño que los bancos de secuencias están sufriendo día a día. En este proyecto se estudian y se investigan mejoras en este tipo de aplicaciones como puede ser el uso de sistemas paralelos que pueden mejorar el rendimiento notablemente.

Machine learning algorithms for spatial data. Case studies: Environmental pollution, natural hazards, renewable resources

This paper presents general problems and approaches for the spatial data analysis using machine learning algorithms. Machine learning is a very powerful approach to adaptive data analysis, modelling and visualisation. The key feature of the machine learning algorithms is that they learn from empirical data and can be used in cases when the modelled environmental phenomena are hidden, nonlinear, noisy and highly variable in space and in time. Most of the machines learning algorithms are universal and adaptive modelling tools developed to solve basic problems of learning from data: classification/pattern recognition, regression/mapping and probability density modelling. In the present report some of the widely used machine learning algorithms, namely artificial neural networks (ANN) of different architectures and Support Vector Machines (SVM), are adapted to the problems of the analysis and modelling of geo-spatial data. Machine learning algorithms have an important advantage over traditional models of spatial statistics when problems are considered in a high dimensional geo-feature spaces, when the dimension of space exceeds 5. Such features are usually generated, for example, from digital elevation models, remote sensing images, etc. An important extension of models concerns considering of real space constrains like geomorphology, networks, and other natural structures. Recent developments in semi-supervised learning can improve modelling of environmental phenomena taking into account on geo-manifolds. An important part of the study deals with the analysis of relevant variables and models' inputs. This problem is approached by using different feature selection/feature extraction nonlinear tools. To demonstrate the application of machine learning algorithms several interesting case studies are considered: digital soil mapping using SVM, automatic mapping of soil and water system pollution using ANN; natural hazards risk analysis (avalanches, landslides), assessments of renewable resources (wind fields) with SVM and ANN models, etc. The dimensionality of spaces considered varies from 2 to more than 30. Figures 1, 2, 3 demonstrate some results of the studies and their outputs. Finally, the results of environmental mapping are discussed and compared with traditional models of geostatistics.