Complex systems are neither perfectly regular nor completely random. They consist of a multitude of players who, in many cases, playtogether in a way that makes their combined strength greater than the sum of their individual achievements. It is often very effective to represent these systems as networks where the actual connections between the players take on a crucial role.Networks exist all around us and are an important part of our world, from the protein machinery inside our cells to social interactions and man-madecommunication systems. Many of these systems have developed over a long period of time and are constantly undergoing changes driven by complicated microscopic events. These events are often too complicated for us to accurately resolve, making the world seem random and unpredictable. There are however ways of using this unpredictability in our favor by replacing the true events by much simpler stochastic rules giving effectively the same outcome. This allows us to capture the macroscopic behavior of the system, to extract important information about the dynamics of the system and learn about the reason for what we observe. Statistical mechanics gives the tools to deal with such large systems driven by underlying random processes under various external constraints, much like how intracellular networks are driven by random mutations under the constraint of natural selection.This similarity makes it interesting to combine the two and to apply some of the tools provided by statistical mechanics on biological systems.In this thesis, several null models are presented, with this view point in mind, to capture and explain different types of structural properties of real biological networks. The most recent major transition in evolution is the development of language, both spoken and written. This thesis also brings up the subject of quantitative linguistics from the eyes of a physicist, here called linguaphysics. Also in this case the data is analyzed with an assumption of an underlying randomness. It is shown that some statistical properties of books, previously thought to be universal, turn out to exhibit author specific size dependencies. A meta book theory is put forward which explains this dependency by describing the writing of a text as pulling a section out of a huge, individual, abstract mother book. / Komplexa system är varken perfekt ordnade eller helt slumpmässiga. De består av en mängd aktörer, som i många fall agerar tillsammans på ett sådant sätt att deras kombinerade styrka är större än deras individuella prestationer. Det är ofta effektivt att representera dessa system som nätverk där de faktiska kopplingarna mellan aktörerna spelar en avgörande roll. Nätverk finns överallt omkring oss och är en viktig del av vår värld , från proteinmaskineriet inne i våra celler till sociala samspel och människotillverkade kommunikationssystem.Många av dessa system har utvecklats under lång tid och genomgår hela tiden förändringar som drivs på av komplicerade småskaliga händelser.Dessa händelser är ofta för komplicerade för oss att noggrant kunna analysera, vilket får vår värld att verka slumpmässig och oförutsägbar. Det finns dock sätt att använda denna oförutsägbarhet till vår fördel genom att byta ut de verkliga händelserna mot mycket enklare regler baserade på sannolikheter, som ger effektivt sett samma utfall. Detta tillåter oss att fånga systemets övergripande uppförande, att utvinna viktig information om systemets dynamik och att få kunskap om anledningen till vad vi observerar. Statistisk mekanik hanterar stora system pådrivna av sådana underliggande slumpmässiga processer under olika restriktioner, på liknande sätt som nätverk inne i celler drivs av slumpmässiga mutationer under restriktionerna från naturligt urval. Denna likhet gör det intressant att kombinera de två och att applicera de verktyg som ges av statistisk mekanik på biologiska system. I denna avhandling presenteras flera nollmodeller som, baserat på detta synsätt, fångar och förklarar olika typer av strukturella egenskaper hos verkliga biologiska nätverk. Den senaste stora evolutionära övergången är utvecklandet av språk, både talat och skrivet. Denna avhandling tar också upp ämnet om kvantitativ linguistik genom en fysikers ögon, här kallat linguafysik. även i detta fall så analyseras data med ett antagande om en underliggande slumpmässighet. Det demonstreras att vissa statistiska egenskaper av böcker, som man tidigare trott vara universella, egentligen beror på bokens längd och på författaren. En metaboksteori ställs fram vilken förklarar detta beroende genom att beskriva författandet av en text som att rycka ut en sektion ur en stor, individuell, abstrakt moderbok.

No description available.

La biologie des systèmes s’est beaucoup développée ces dix dernières années, confrontant plusieurs niveaux biologiques (molécule, réseau, tissu, organisme, écosystème…). Du point de vue de l’étude de l’évolution, elle offre de nombreuses possibilités. Cette thèse porte sur le développement de nouvelles méthodologies et de nouveaux outils pour étudier l’évolution des systèmes biologiques tout en considérant l’aspect multidimensionnel des données biologiques. Ce travail tente de palier un manque méthodologique évidant pour réaliser des études haut-débit dans le récent domaine de la biologie évolutionnaire des systèmes. De nouveaux messages évolutifs liés aux contraintes intra et inter processus ont été décrites. En particulier, mon travail a permis (i) la création d’un algorithme et un outil bioinformatique dédié à l’étude des relations évolutives d’orthologie existant entre les gènes de centaines d’espèces, (ii) le développement d’un formalisme original pour l’intégration de variables biologiques multidimensionnelles permettant la représentation synthétique de l’ histoire évolutive d’un gène donné, (iii) le couplage de cet outil intégratif avec des approches mathématiques d’extraction de connaissances pour étudier les perturbations évolutives existant au sein des processus biologiques humains actuellement documentés (voies métaboliques, voies de signalisations…). / Systems biology has developed enormously over the 10 last years, with studies covering diverse biological levels (molecule, network, tissue, organism, ecology…). From an evolutionary point of view, systems biology provides unequalled opportunities. This thesis describes new methodologies and tools to study the evolution of biological systems, taking into account the multidimensional properties of biological parameters associated with multiple levels. Thus it addresses the clear need for novel methodologies specifically adapted to high-throughput evolutionary systems biology studies. By taking account the multi-level aspects of biological systems, this work highlight new evolutionary trends associated with both intra and inter-process constraints. In particular, this thesis includes (i) the development of an algorithm and a bioinformatics tool dedicated to comprehensive orthology inference and analysis for hundreds of species, (ii) the development of an original formalism for the integration of multi-scale variables allowing the synthetic representation of the evolutionary history of a given gene, (iii) the combination of this integrative tool with mathematical knowledge discovery approaches in order to highlight evolutionary perturbations in documented human biological systems (metabolic and signalling pathways...).

Developmental disorders including: autism, intellectual disability, and congenital abnormalities are present in 3-8% of live births and display a huge amount of phenotypic and genetic heterogeneity. Traditionally, geneticists have identified individual monogenic diseases among these patients but a majority of patients fail to receive a clinical diagnosis. However, the genomes of these patients frequently harbour large copynumber variants (CNVs) but their interpretation remains challenging. Using pathway analysis I found significant functional associations for 329 individual phenotypes and show that 39% of these could explain the patients’ multiple co-morbid phenotypes; and multiple associated genes clustered within individual CNVs. I showed there was significantly more such clustering than expected by chance. In addition, the presence of a multiple functionally-related genes is a significant predictor of CNV pathogenicity beyond the presence of known disease genes and size of the CNV. This clustering of functionally-related genes was part of a broader pattern of functional clusters across the human genome. These genome-wide functional clusters showed tissuespecific expression and some evidence of chromatin-domain level regulation. Furthermore, many genome-wide functional clusters were enriched in segmental duplications making them prone to CNV-causing mutations and were frequently seen disrupted in healthy individuals. However, the majority of the time a pathogenic CNV affected the entire functional cluster, where as benign CNVs tended to affect only one or two genes. I also showed that patients with CNVs affecting the same functional cluster are significantly more phenotypically similar to each other than expected even if their CNVs do not affect any of the same genes. Lastly, I considered one of the major limitations in pathway analysis, namely ascertainment biases in functional information due to the prioritization of genes linked to human disease, and show how the modular nature of gene-networks can be used to identify and prioritize understudied genes.

Investigating mechanisms that regulate genes and the genes' functions are essential to understand a biological system. This dissertation is consists of two specific research projects under these aims, which are for understanding piRNA's regulation mechanism and predicting genes' function computationally. The first project shows a piRNA regulation landscape in C. elegans. piRNAs (Piwi-interacting small RNAs) form a complex with Piwi Argonautes to maintain fertility and silence transposons in animal germlines. In C. elegans, previous studies have suggested that piRNAs tolerate mismatched pairing and in principle could target all transcripts. In this project, by computationally analyzing the chimeric reads directly captured by cross-linking piRNA and their targets in vivo, piRNAs are found to target all germline mRNAs with microRNA-like pairing rules. The number of targeting chimeric reads correlates better with binding energy than with piRNA abundance, suggesting that piRNA concentration does not limit targeting. Further more, in mRNAs silenced by piRNAs, secondary small RNAs are found to be accumulating at the center and ends of piRNA binding sites. Whereas in germline-expressed mRNAs, reduced piRNA binding density and suppression of piRNA-associated secondary small RNAs targeting correlate with the CSR-1 Argonaute presence. These findings reveal physiologically important and nuanced regulation of piRNA targets and provide evidence for a comprehensive post-transcriptional regulatory step in germline gene expression. The second project elaborates a computational model to predict gene function. Predicting genes involved in a biological function facilitates many kinds of research, such as prioritizing candidates in a screening project. Following the “Guilt By Association” principle, multiple datasets are considered as biological networks and integrated together under a multi-label learning framework for predicting gene functions. Specifically, the functional labels are propagated and smoothed using a label propagation method on the networks and then integrated using an “Error correction of code” multi-label learning framework, where a “codeword” defines all the labels annotated to a specific gene. The model is then trained by finding the optimal projections between the code matrix and the biological datasets using canonical correlation analysis. Its performance is benchmarked by comparing to a state-of-art algorithm and a large scale screen results for piRNA pathway genes in D.melanogaster. Finally, piRNA targeting's roles in epigenetics and physiology and its cross-talk with CSR-1 pathway are discussed, together with a survey of additional biological datasets and a discussion of benchmarking methods for the gene function prediction.

A primary challenge in the analysis of high-throughput biological data is the abundance of correlated variables. A small change to a gene's expression or a protein's binding availability can cause significant downstream effects. The existence of such chain reactions presents challenges in numerous areas of analysis. By leveraging knowledge of the network interactions that underlie this type of data, we can often enable better understanding of biological phenomena. This dissertation will examine network-based statistical approaches to the problems of mechanism-of-action inference, characterization of gene expression changes, and prediction of drug response. First, we develop a method for multi-target perturbation detection in multi-omics biological data. We estimate a joint Gaussian graphical model across multiple data types using penalized regression, and filter for network effects. Next, we apply a set of likelihood ratio tests to identify the most likely site of the original perturbation. We also present a conditional testing procedure to allow for detection of secondary perturbations. Second, we address the problem of characterization of cellular phenotypes via Bayesian regression in the Gene Ontology (GO). In our model, we use the structure of the GO to assign changes in gene expression to functional groups, and to model the covariance between these groups. In addition to describing changes in expression, we use these functional activity estimates to predict the expression of unobserved genes. We further determine when such predictions are likely to be inaccurate by identifying GO terms with poor agreement to gene-level estimates. In a case study, we identify GO terms relevant to changes in the growth rate of S. cerevisiae. Lastly, we consider the prediction of drug sensitivity in cancer cell lines based on pathway-level activity estimates from ASSIGN, a Bayesian factor analysis model. We use penalized regression to predict response to various cancer treatments based on cancer subtype, pathway activity, and 2-way interactions thereof. We also present network representations of these interaction models and examine common patterns in their structure across treatments.

In this dissertation, we show two significant applications of combinatorial branch-and-bound as an exact solution methodology in combinatorial optimization problems. In the first problem, we propose a set of new group centrality metrics and show their performance in estimating protein importance in protein-protein interaction networks. The centrality metrics introduced here are extensions of well-known nodal metrics (degree, betweenness, and closeness) for a set of nodes which is required to induce a specific pattern. The structures investigated range from the ``stricter'' induced stars and cliques, to a ``looser'' definition of a representative structure. We derive the computational complexity for each of the newly proposed metrics. Then, we provide mixed integer programming formulations to solve the problems exactly; due to the computational complexity of the problem and the sheer size of protein-protein interaction networks, using a commercial solver with the formulations is not always a viable option. Hence, we also propose a combinatorial branch-and-bound approach to solve the problems introduced. Finally, we conclude this work with a presentation of the performance of the proposed centrality metrics in identifying essential proteins in helicobacter pylori. In the second problem, we introduce the asymmetric probabilistic minimum-cost Hamiltonian cycle problem (APMCHCP) where arcs and vertices in the graph are possible to fail. APMCHCP has applications in many emerging areas, such as post-disaster recovery, electronic circuit design, and security maintenance of wireless sensor networks. For each vertex, we define a chance-constraint to guarantee that the probability of arriving at the vertex must be greater than or equal to a given threshold. Four mixed-integer programming (MIP) formulations are proposed for modeling the problem, including two direct formulations and two recursive formulations. A combinatorial branch-and-bound (CBB) algorithm is proposed for solving the APMCHCP, where data preprocessing steps, feasibility rules, and approaches of finding upper and lower bounds are developed. In the numerical experiments, the CBB algorithm is compared with formulations on a test-bed of two popular benchmark instance sets. The results show that the proposed CBB algorithm significantly outperforms Gurobi solver in terms of both the size of optimally solved instances and the computing time.

No description available.

Biological systems constantly evolve and adapt in response to changed environment and external stimuli at the molecular and genomic levels. Building statistical models that characterize such dynamic changes in biological systems is one of the key objectives in bioinformatics and computational biology. Recent advances in high-throughput genomic and molecular profiling technologies such as gene expression and and copy number microarrays provide ample opportunities to study cellular activities at the individual gene and network levels. The aim of this dissertation is to formulate mathematically dynamic changes in biological networks and DNA copy numbers, to develop machine learning algorithms to learn these statistical models from high-throughput biological data, and to demonstrate their applications in systems biological studies. The first part (Chapters 2-4) of the dissertation focuses on the dynamic changes taking placing at the biological network level. Biological networks are context-specific and dynamic in nature. Under different conditions, different regulatory components and mechanisms are activated and the topology of the underlying gene regulatory network changes. We report a differential dependency network (DDN) analysis to detect statistically significant topological changes in the transcriptional networks between two biological conditions. Further, we formalize and extend the DDN approach to an effective learning strategy to extract structural changes in graphical models using l1-regularization based convex optimization. We discuss the key properties of this formulation and introduce an efficient implementation by the block coordinate descent algorithm. Another type of dynamic changes in biological networks is the observation that a group of genes involved in certain biological functions or processes coordinate to response to outside stimuli, producing distinct time course patterns. We apply the echo stat network, a new architecture of recurrent neural networks, to model temporal gene expression patterns and analyze the theoretical properties of echo state networks with random matrix theory. The second part (Chapter 5) of the dissertation focuses on the changes at the DNA copy number level, especially in cancer cells. Somatic DNA copy number alterations (CNAs) are key genetic events in the development and progression of human cancers, and frequently contribute to tumorigenesis. We propose a statistically-principled in silico approach, Bayesian Analysis of COpy number Mixtures (BACOM), to accurately detect genomic deletion type, estimate normal tissue contamination, and accordingly recover the true copy number profile in cancer cells. / Ph. D.

Pour mieux saisir les liens complexes entre génotype et phénotype, une méthode utilisée consiste à étudier les relations entre différents éléments biologiques (entre les protéines, entre les métabolites...). Celles-ci forment ce qui est appelé un réseau biologique, que l'on représente algorithmiquement par un graphe. Nous nous intéressons principalement dans cette thèse au problème de la recherche d'un motif (multi-ensemble de couleurs) dans un graphe coloré, représentant un réseau biologique. De tels motifs correspondent généralement à un ensemble d'éléments conservés au cours de l'évolution et participant à une même fonction biologique. Nous continuons l'étude algorithmique de ce problème et de ses variantes (qui admettent plus de souplesse biologique), en distinguant les instances difficiles algorithmiquement et en étudiant différentes possibilités pour contourner cette difficulté (complexité paramétrée, réduction d'instance, approximation...). Nous proposons également un greffon intégré au logiciel Cytoscape pour résoudre efficacement ce problème, que nous testons sur des données réelles.Nous nous intéressons également à différents problèmes de génomique comparative. La démarche scientifique adoptée reste la même: depuis une formalisation d'un problème biologique, déterminer ses instances difficiles algorithmiquement et proposer des solutions pour contourner cette difficulté (ou prouver que de telles solutions sont impossibles à trouver sous des hypothèses fortes) / To investigate the complex links between genotype and phenotype, one can study the relations between different biological entities. It forms a biological network, represented by a graph. In this thesis, we are interested in the occurrence of a motif (a multi-set of colors) in a vertex-colored graph, representing a biological network. Such motifs usually correspond to a set of elements realizing a same function, and which may have been evolutionarily preserved. We follow the algorithmic study of this problem, by establishing hard instances and studying possibilities to cope with the hardness (parameterized complexity, preprocessing, approximation...). We also develop a plugin for Cytoscape, in order to solve efficiently this problem and to test it on real data.We are also interested in different problems related to comparative genomics. The scientific method is the same: studying problems arising from biology, specifying the hard instances and giving solutions to cope with the hardness (or proving such solutions are unlikely)