Genome-wide DNA polymorphism analyses using VariScan

BACKGROUND: DNA sequence polymorphisms analysis can provide valuable information on the evolutionary forces shaping nucleotide variation, and provides an insight into the functional significance of genomic regions. The recent ongoing genome projects will radically improve our capabilities to detect specific genomic regions shaped by natural selection. Current available methods and software, however, are unsatisfactory for such genome-wide analysis. RESULTS: We have developed methods for the analysis of DNA sequence polymorphisms at the genome-wide scale. These methods, which have been tested on a coalescent-simulated and actual data files from mouse and human, have been implemented in the VariScan software package version 2.0. Additionally, we have also incorporated a graphical-user interface. The main features of this software are: i) exhaustive population-genetic analyses including those based on the coalescent theory; ii) analysis adapted to the shallow data generated by the high-throughput genome projects; iii) use of genome annotations to conduct a comprehensive analyses separately for different functional regions; iv) identification of relevant genomic regions by the sliding-window and wavelet-multiresolution approaches; v) visualization of the results integrated with current genome annotations in commonly available genome browsers. CONCLUSION: VariScan is a powerful and flexible suite of software for the analysis of DNA polymorphisms. The current version implements new algorithms, methods, and capabilities, providing an important tool for an exhaustive exploratory analysis of genome-wide DNA polymorphism data.

On the convergence of EM-like algorithms for image segmentation using Markov random fields.

Inference of Markov random field images segmentation models is usually performed using iterative methods which adapt the well-known expectation-maximization (EM) algorithm for independent mixture models. However, some of these adaptations are ad hoc and may turn out numerically unstable. In this paper, we review three EM-like variants for Markov random field segmentation and compare their convergence properties both at the theoretical and practical levels. We specifically advocate a numerical scheme involving asynchronous voxel updating, for which general convergence results can be established. Our experiments on brain tissue classification in magnetic resonance images provide evidence that this algorithm may achieve significantly faster convergence than its competitors while yielding at least as good segmentation results.

La spéciation écologique racontée au travers de l'étude de l'évolution des poissons-clowns et de quelques autres

Ecological speciation and its hallmark, adaptive radiation is a process from which most of the current biodiversity derives. As ecological opportunity allows species to colonise unoccupied niches, natural selection drives adaptive phenotypical change. In this thesis, I begin by describing how this evolutionary process acted on the evolution of the clownfishes. During its infancy, this iconic group of coral reef fishes developed a mutualism with sea anemone species. I show how this event triggered the evolutionary radiation of the group, generating species that now inhabit diverse habitats of the coral reefs. Following the appearance of the mutualism, the diversification of the clownfish was catalysed by hybridisation events which shuffled genes, allowing hybrids to reach new fitness optima. While the clownfishes appeared in the region of the coral triangle, a lineage colonised the eastern shores of Africa. I reconstructed the geographic history of the group and showed that this event lead to the rapid appearance of new species, replicating the evolutionary patterns of the original radiation. To better grasp the mechanisms of ecological speciation, I conducted analyses at the population level and identified similar evolutionary patterns than found at the clade level. I discuss how such result suggests a continuity bridging micro- and macroevolution, which so far only been theorised. In parallel to this study case, I question whether biotic and abiotic interactions can promote or restrain ecological speciation. Indeed, I show how the ecological setting of species can drastically impact on their diversification dynamics. Moreover, tradeoffs can occur between specialisation made on different ecological axes allowing species cohabitation. Overall, I show in this work that regardless of the few simple rules that explain the mechanism of ecological speciation, the unavoidable interactions with the ever changing ecological context lead diversification events to give always a different outcome. It is thus primordial to account for the ecological settings of species when discussing their evolutionary dynamics. LA SPÉCIATION ÉCOLOGIQUE RACONTÉE AU TRAVERS DE L'ÉTUDE DE L'ÉVOLUTION DES POISSONS-CLOWNS ET DE QUELQUES AUTRES Le phénomène de spéciation écologique est à l'origine de la majeure partie de la biodiversité que l'on rencontre aujourd'hui. Au fil des opportunités qu'elles rencontrent, les espèces colonisent l'espace écologique laissant la sélection naturelle forger leur phénotype moyen. Malgré l'omniprésence de ce phénomène dans la nature, beaucoup de questions qui lui sont relatives restent à élucider. C'est afin de mieux comprendre ce mécanisme que j'étudie les poissons-clowns, célèbres habitants des récifs coralliens. Dans ce travail, je démontré que le développement du comportement mutualiste liant les poissons-clowns aux anémones de mer fut l'événement qui déclencha leur diversification. Suite à ce premier événement, j'illustre comment l'hybridation entre lignées primordiales a remodelé la diversité génétique du groupe et catalysé leur radiation évolutive. Je poursuis en reconstruisant l'expansion géographique des poissons-clowns au cours du temps depuis le triangle de corail, leur lieu d'origine, jusqu'aux côtes d'Afrique de l'Ouest. Afin d'affiner ces analyses générales sur le groupe, je continue en étudiant plus finement des populations d'une seule espèce de poisson-clown. Cette fine résolution me permet de comprendre plus précisément quels sont les facteurs écologiques qui permettent aux poissons-clowns de se différencier. Les résultats de ces analyses suggèrent qu'il est important de comprendre les liens entre le contexte écologique et la diversification des espèces. J'étudie cette question dans la seconde partie de ce travail en montrant que l'hétérogénéité du paysage ou les liens entretenus avec un partenaire mutualiste influencent fortement la dynamique évolutive des espèces. Finalement, j'illustre les compromis que chaque espèce réalise en se spécialisant ou non dans ses interactions avec l'environnent. Plus généralement, je souligne dans ce travail l'influence du contexte écologique sur le résultat de la spéciation écologique. Ce sont ces interactions entre les organismes et leur environnent qui sont à l'origine de l'incroyable diversité de la vie. Il est donc primordial de les prendre en compte lors de l'étude de l'évolution des espèces.

Identification of cancer/testis-antigen genes by massively parallel signature sequencing.

Massively parallel signature sequencing (MPSS) generates millions of short sequence tags corresponding to transcripts from a single RNA preparation. Most MPSS tags can be unambiguously assigned to genes, thereby generating a comprehensive expression profile of the tissue of origin. From the comparison of MPSS data from 32 normal human tissues, we identified 1,056 genes that are predominantly expressed in the testis. Further evaluation by using MPSS tags from cancer cell lines and EST data from a wide variety of tumors identified 202 of these genes as candidates for encoding cancer/testis (CT) antigens. Of these genes, the expression in normal tissues was assessed by RT-PCR in a subset of 166 intron-containing genes, and those with confirmed testis-predominant expression were further evaluated for their expression in 21 cancer cell lines. Thus, 20 CT or CT-like genes were identified, with several exhibiting expression in five or more of the cancer cell lines examined. One of these genes is a member of a CT gene family that we designated as CT45. The CT45 family comprises six highly similar (>98% cDNA identity) genes that are clustered in tandem within a 125-kb region on Xq26.3. CT45 was found to be frequently expressed in both cancer cell lines and lung cancer specimens. Thus, MPSS analysis has resulted in a significant extension of our knowledge of CT antigens, leading to the discovery of a distinctive X-linked CT-antigen gene family.

Computational and Energy Costs of Cryptographic Algorithms on Handheld Devices

Networks are evolving toward a ubiquitous model in which heterogeneousdevices are interconnected. Cryptographic algorithms are required for developing securitysolutions that protect network activity. However, the computational and energy limitationsof network devices jeopardize the actual implementation of such mechanisms. In thispaper, we perform a wide analysis on the expenses of launching symmetric and asymmetriccryptographic algorithms, hash chain functions, elliptic curves cryptography and pairingbased cryptography on personal agendas, and compare them with the costs of basic operatingsystem functions. Results show that although cryptographic power costs are high and suchoperations shall be restricted in time, they are not the main limiting factor of the autonomyof a device.

Environmental data mining and modeling based on machine learning algorithms and geostatistics

The paper presents some contemporary approaches to spatial environmental data analysis. The main topics are concentrated on the decision-oriented problems of environmental spatial data mining and modeling: valorization and representativity of data with the help of exploratory data analysis, spatial predictions, probabilistic and risk mapping, development and application of conditional stochastic simulation models. The innovative part of the paper presents integrated/hybrid model-machine learning (ML) residuals sequential simulations-MLRSS. The models are based on multilayer perceptron and support vector regression ML algorithms used for modeling long-range spatial trends and sequential simulations of the residuals. NIL algorithms deliver non-linear solution for the spatial non-stationary problems, which are difficult for geostatistical approach. Geostatistical tools (variography) are used to characterize performance of ML algorithms, by analyzing quality and quantity of the spatially structured information extracted from data with ML algorithms. Sequential simulations provide efficient assessment of uncertainty and spatial variability. Case study from the Chernobyl fallouts illustrates the performance of the proposed model. It is shown that probability mapping, provided by the combination of ML data driven and geostatistical model based approaches, can be efficiently used in decision-making process. (C) 2003 Elsevier Ltd. All rights reserved.

Robust power allocation algorithms for MIMO OFDM systems with imperfect CSI

This paper presents a Bayesian approach to the design of transmit prefiltering matrices in closed-loop schemes robust to channel estimation errors. The algorithms are derived for a multiple-input multiple-output (MIMO) orthogonal frequency division multiplexing (OFDM) system. Two different optimizationcriteria are analyzed: the minimization of the mean square error and the minimization of the bit error rate. In both cases, the transmitter design is based on the singular value decomposition (SVD) of the conditional mean of the channel response, given the channel estimate. The performance of the proposed algorithms is analyzed,and their relationship with existing algorithms is indicated. As withother previously proposed solutions, the minimum bit error rate algorithmconverges to the open-loop transmission scheme for very poor CSI estimates.

Avian Evolutionary Genomics: Studies of Ficedula Flycatchers

In this thesis, different genetic tools are used to investigate both natural variation and speciation in the Ficedula flycatcher system: pied (Ficedula hypoleuca) and collared (F. albicollis) flycatchers. The molecular evolution of a gene involved in postnatal body growth, GH, has shown high degree of conservation at the mature protein between birds and mammals, whereas the variation observed in its signal peptide seems to be adaptive in pied flycatcher (I & II). Speciation is the process by which reproductive barriers to gene flow evolve between populations, and understanding the mechanisms involved in pre- and post-zygotic isolation have been investigated in Ficedula flycatchers. The Z chromosome have been suggested to be the hotspot for genes involved in speciation, thus sequencing of 13 Z-linked coding genes from the two species in allopatry and sympatry have been conducted (III). Surprisingly, the majority of Z-linked genes seemed to be highly conserved, suggesting instead a potential involvement of regulatory regions. Previous studies have shown that genes involved in hybrid fitness, female preferences and male plumage colouration are sex-linked. Hence, three pigmentation genes have been investigated: MC1R, AGRP, and TYRP1. Of these three genes, TYRP1 was identified as a strong candidate to be associated with black-brown plumage variation in sympatric populations, and hence is a strong candidate for a gene contributing to pre-zygotic isolation (IV). In sympatric areas, where pied and collared flycatchers have overlapping breeding areas, hybridization sometimes occurs leading to the production of unfit hybrids. By using a proteomic approach a novel expression pattern in hybrids was revealed compared to the parental species (V) and differentially expressed proteins subsequently identified by sequence similarity (VI). In conclusion, the Z chromosome appears to play an important role in flycatcher speciation, but probably not at the coding level. In addition the novel expression patterns might give new insights into the maladaptive hybrids.

Probabilistic algorithms for blind adaptive multiuser detection

In this paper, two probabilistic adaptive algorithmsfor jointly detecting active users in a DS-CDMA system arereported. The first one, which is based on the theory of hiddenMarkov models (HMM’s) and the Baum–Wech (BW) algorithm,is proposed within the CDMA scenario and compared withthe second one, which is a previously developed Viterbi-basedalgorithm. Both techniques are completely blind in the sense thatno knowledge of the signatures, channel state information, ortraining sequences is required for any user. Once convergencehas been achieved, an estimate of the signature of each userconvolved with its physical channel response (CR) and estimateddata sequences are provided. This CR estimate can be used toswitch to any decision-directed (DD) adaptation scheme. Performanceof the algorithms is verified via simulations as well as onexperimental data obtained in an underwater acoustics (UWA)environment. In both cases, performance is found to be highlysatisfactory, showing the near–far resistance of the analyzed algorithms.

Performance of noninvasive ventilation algorithms on ICU ventilators during pressure support: a clinical study.

To evaluate the impact of noninvasive ventilation (NIV) algorithms available on intensive care unit ventilators on the incidence of patient-ventilator asynchrony in patients receiving NIV for acute respiratory failure. Prospective multicenter randomized cross-over study. Intensive care units in three university hospitals. Patients consecutively admitted to the ICU and treated by NIV with an ICU ventilator were included. Airway pressure, flow and surface diaphragmatic electromyography were recorded continuously during two 30-min periods, with the NIV (NIV+) or without the NIV algorithm (NIV0). Asynchrony events, the asynchrony index (AI) and a specific asynchrony index influenced by leaks (AIleaks) were determined from tracing analysis. Sixty-five patients were included. With and without the NIV algorithm, respectively, auto-triggering was present in 14 (22%) and 10 (15%) patients, ineffective breaths in 15 (23%) and 5 (8%) (p = 0.004), late cycling in 11 (17%) and 5 (8%) (p = 0.003), premature cycling in 22 (34%) and 21 (32%), and double triggering in 3 (5%) and 6 (9%). The mean number of asynchronies influenced by leaks was significantly reduced by the NIV algorithm (p < 0.05). A significant correlation was found between the magnitude of leaks and AIleaks when the NIV algorithm was not activated (p = 0.03). The global AI remained unchanged, mainly because on some ventilators with the NIV algorithm premature cycling occurs. In acute respiratory failure, NIV algorithms provided by ICU ventilators can reduce the incidence of asynchronies because of leaks, thus confirming bench test results, but some of these algorithms can generate premature cycling.

PhylomeDB v4: zooming into the plurality of evolutionary histories of a genome

Phylogenetic trees representing the evolutionary relationships of homologous genes are the entry point for many evolutionary analyses. For instance, the use of a phylogenetic tree can aid in the inference of orthology and paralogy relationships, and in the detection of relevant evolutionary events such as gene family expansions and contractions, horizontal gene transfer, recombination or incomplete lineage sorting. Similarly, given the plurality of evolutionary histories among genes encoded in a given genome, there is a need for the combined analysis of genome-wide collections of phylogenetic trees (phylomes). Here, we introduce a new release of PhylomeDB (http://phylomedb.org), a public repository of phylomes. Currently, PhylomeDB hosts 120 public phylomes, comprising >1.5 million maximum likelihood trees and multiple sequence alignments. In the current release, phylogenetic trees are annotated with taxonomic, protein-domain arrangement, functional and evolutionary information. PhylomeDB is also a major source for phylogeny-based predictions of orthology and paralogy, covering >10 million proteins across 1059 sequenced species. Here we describe newly implemented PhylomeDB features, and discuss a benchmark of the orthology predictions provided by the database, the impact of proteome updates and the use of the phylome approach in the analysis of newly sequenced genomes and transcriptomes.

Evolutionary aspects of population structure for molecular and quantitative traits in the freshwater snail Radix balthica.

Detecting the action of selection in natural populations can be achieved using the QST-FST comparison that relies on the estimation of FST with neutral markers, and QST using quantitative traits potentially under selection. QST higher than FST suggests the action of directional selection and thus potential local adaptation. In this article, we apply the QST-FST comparison to four populations of the hermaphroditic freshwater snail Radix balthica located in a floodplain habitat. In contrast to most studies published so far, we did not detect evidence of directional selection for local optima for any of the traits we measured: QST calculated using three different methods was never higher than FST. A strong inbreeding depression was also detected, indicating that outcrossing is probably predominant over selfing in the studied populations. Our results suggest that in this floodplain habitat, local adaptation of R. balthica populations may be hindered by genetic drift, and possibly altered by uneven gene flow linked to flood frequency.

Linking genetic and species diversities in a community of freshwater gastropods

Summary Biodiversity is usually studied through species or genetic diversities. To date, these two levels of diversity have remained the independent .fields of investigations of community ecologists and population geneticists. However, recent joint analyses of species and genetic diversities have suggested that common processes may underlie the two levels. Positive correlations between species diversity and genetic diversity may arise when the effects of drift and migration overwhelm selective effects. The first goal of this thesis was to make a joint investigation of the patterns of species and genetic diversity in a community of freshwater gastropods living in a floodplain habitat. The second goal was to determine, as far as possible, the relative influences of the processes underlying the patterns observed at each level. In chapter 2 we investigate the relative influences of different evolutionary forces in shaping the genetic structure of Radix balthica populations. Results revealed that the structure inferred using quantitative traits was lower or equal to the one inferred using neutral molecular markers. Consequently, the pattern of structure observed could be only due to random drift, possibly to uniform selection, but definitely not to selection for local optima. In chapter 3, we analyze the temporal variation of species and genetic diversities in five localities. An extended period of drought occurred at the end of the study period leading to decay of both species and genetic diversities. This parallel loss of diversity following a natural perturbation highlighted the role sometimes predominant of random drift over selection on patterns of biodiversity in a floodplain habitat. In chapter 4, we compare the spatial genetic structures of two sympatric species: Radix balthica and Planorbis carinatus. We found that R. balthica populations are weakly structured and have moderate to high values of gene diversity. In contrast, P. carinatus populations are highly structured and poorly diverse. Then we measured correlations between various indices of species and genetic diversity using genetic data .from the two species. We found only one significant correlation: between species richness and gene diversity of P. carinatus. This result highlights the .need to use genetic date from more than one species to infer correlations between species and genetic diversities. Overall, this thesis provided new insights into the common processes underlying patterns of species and genetic diversity. Résumé La biodiversité est généralement étudiée au niveau de la diversité génétique ou spécifique. Ces deux niveaux sont restés jusqu'à maintenant les domaines d'investigation séparés des généticiens des populations et des écologistes des communautés. Cependant, des analyses conjointes des diversités génétique et spécifique ont récemment suggéré que des processus similaires pouvaient influencer ces deux niveaux. Des corrélations positives entre les diversités génétique et spécifique pourraient être dues aux effets de migration et de dérive qui dominent les effets sélectifs. Le premier but de cette thèse était de faire une étude conjointe des diversités génétique et spécifique dans une communauté de gastéropodes d'eau douce. Le second objectif était de déterminer les influences relatives des différents processus liés à chaque niveau de diversité. Dans le chapitre 2 nous cherchons à déterminer quelles forces évolutives influencent la structure génétique de quatre populations de Radix balthica. La structure mesurée sur des traits quantitatifs s'est révélée être plus faible ou égale à celle mesurée avec des marqueurs moléculaires neutres. La structure observée pourrait ainsi être due uniquement à la dérive génétique, potentiellement à la sélection uniforme, mais en aucun cas à la sélection locale pour différents optima. Dans le chapitre 3 nous analysons la variation temporelle des diversités génétique et spécifique dans cinq localités. Une récente période de sécheresse a causé une diminution parallèle des deux niveaux de diversité. Cette perturbation à mis en évidence le rôle parfois prépondérant de la dérive par rapport à celui de la sélection dans le déterminisme de la biodiversité dans un écosytème alluvial. Dans le chapitre 4, nous comparons la structure génétique spatiale de deux espèces vivant en sympatrie : Radix balthica et Planorbis carinatus. Les populations de R. balthica sont peu structurées et présentent un niveau de diversité relativement élevé alors que celles de P. carinatus sont fortement structurées et peu diversifiées. Nous avons ensuite mesuré différentes corrélations entre les diversités génétique et spécifique, mais la seule relation significative a été trouvée entre la richesse spécifique et la diversité génétique de P. carinatus. Ainsi, cette thèse a permis de découvrir de nouveaux aspects des processus qui influencent en parallèle la diversité aux niveaux génétique et spécifique.

Ranking-Dominance Relation for (Evolutionary) Multi-Objective Optimization

An alternative relation to Pareto-dominance relation is proposed. The new relation is based on ranking a set of solutions according to each separate objective and an aggregation function to calculate a scalar fitness value for each solution. The relation is called as ranking-dominance and it tries to tackle the curse of dimensionality commonly observedin evolutionary multi-objective optimization. Ranking-dominance can beused to sort a set of solutions even for a large number of objectives when Pareto-dominance relation cannot distinguish solutions from one another anymore. This permits search to advance even with a large number of objectives. It is also shown that ranking-dominance does not violate Pareto-dominance. Results indicate that selection based on ranking-dominance is able to advance search towards the Pareto-front in some cases, where selection based on Pareto-dominance stagnates. However, in some cases it is also possible that search does not proceed into direction of Pareto-front because the ranking-dominance relation permits deterioration of individual objectives. Results also show that when the number of objectives increases, selection based on just Pareto-dominance without diversity maintenance is able to advance search better than with diversity maintenance. Therefore, diversity maintenance is connive at the curse of dimensionality.