One of the most fundamental and least understood elements of evolution is the mapping between genotype and phenotype. Recent work on genotype-phenotype (GP) maps suggests that these maps show properties which may have important evolutionary implications. These properties include a skewed distribution of genotypes over phenotypes, linear scaling between phenotype robustness and the logarithm of phenotype frequency, and a positive correlation between phenotype robustness and evolvability. However, most of these properties have only been studied for self-assembling systems, such as protein complexes or RNA folding. In this thesis, we ask ourselves if these properties are more general. First, we apply tools from algorithmic information theory to a wide class of inputoutput maps, of which GP maps are a subset. We find that these maps show a strong bias towards simple phenotypes, a pattern known as simplicity bias. We also define a matrix map of tunable complexity, with which we can study the conditions under which simplicity bias is present. Next, we investigate multiple models of GP maps for gene regulatory networks (GRNs). These include Boolean threshold networks, where we fix the strength of gene interactions, while varying the network topology, as well as systems of differential equations, where we fix the network topology while varying interaction strengths. For both modelling frameworks, the GRN GP maps exhibit all the structural properties found in the literature, as well as simplicity bias. We also find that the number of genotypes mapping to the wild-type phenotypes for various GRNs is unusually large, and argue that this is evidence that the structure of the GP map plays an important role in determining evolutionary outcomes. Finally, we return to more general input-output maps, and show that in addition to simplicity bias these maps also present randomness deficiency, that is, their output spectrum is less complex than expected. We argue that this additional property combines with simplicity bias in GP maps, and more generally, in input-output maps, and suggest a general trend towards simplicity in nature.

Algorithmic Information Theory (AIT), also known as Kolmogorov complexity, is a quantitative approach to defining information. AIT is mainly used to measure the amount of information present in the observations of a given phenomenon. In this dissertation we explore the applications of AIT in two case studies. The first examines bright field cell image segmentation and the second examines the information complexity of multicellular patterns. In the first study we demonstrate that our proposed AIT-based algorithm provides an accurate and robust bright field cell segmentation. Cell segmentation is the process of detecting cells in microscopy images, which is usually a challenging task for bright field microscopy due to the low contrast of the images. In the second study, which is the primary contribution of this dissertation, we employ an AIT-based algorithm to quantify the complexity of information content that arises during the development of multicellular organisms. We simulate multicellular organism development by coupling the Gene Regulatory Networks (GRN) within an epithelial field. Our results show that the configuration of GRNs influences the information complexity in the resultant multicellular patterns.

This paper aims to apply the Kolmogorov algorithmic complexity theory using the measure proposed by Lempel and Ziv (1976) to analyze its behavior due to changes in parameters such as window size, jumps and the region of stability of high frequency financial series returns of assets traded on the BM&F BOVESPA, as well as to assess the evolution of such a measure when the intervals between the negotiations are extended and to verify the possible evidence of a relationship between the value of the complexity measure and the behavior of autocorrelation curves presented for each trading interval specified. We also discuss the criterion used to measure the relative efficiency of the market proposed by Giglio (2008). / Fundação de Amparo a Pesquisa do Estado de Alagoas / O presente trabalho tem por objetivos: 1) aplicar a teoria da complexidade de Kolmogorov utilizando a medida proposta por Lempel e Ziv (1976) para analisar o comportamento desta diante de alterações em parâmetros como tamanho de janela, salto e de região de estabilidade em séries financeiras de retornos de alta freqüência de ativos negociados na BM&F BOVESPA; 2) avaliar a evolução da medida ao se ampliarem os intervalos entre as negociações; e finalmente, 3) verificar a possibilidade de existir algum indício de relação entre o valor daquela medida e o comportamento das curvas de autocorrelação apresentadas para cada intervalo de negociação especificado. Foi também discutido o critério utilizado para a medida de eficiência relativa de mercado proposto por Giglio (2008).

Les données sous forme de chaîne de symboles sont très variées (ADN, texte, EEG quantifié,…) et ne sont pas toujours modélisables. Une description universelle des chaînes de symboles indépendante des probabilités est donc nécessaire. La complexité de Kolmogorov a été introduite en 1960 pour répondre à cette problématique. Le concept est simple : une chaîne de symboles est complexe quand il n'en existe pas une description courte. La complexité de Kolmogorov est le pendant algorithmique de l’entropie de Shannon et permet de définir la théorie algorithmique de l’information. Cependant, la complexité de Kolmogorov n’est pas calculable en un temps fini ce qui la rend inutilisable en pratique.Les premiers à rendre opérationnelle la complexité de Kolmogorov sont Lempel et Ziv en 1976 qui proposent de restreindre les opérations de la description. Une autre approche est d’utiliser la taille de la chaîne compressée par un compresseur sans perte. Cependant ces deux estimateurs sont mal définis pour le cas conditionnel et le cas joint, il est donc difficile d'étendre la complexité de Lempel-Ziv ou les compresseurs à la théorie algorithmique de l’information.Partant de ce constat, nous introduisons une nouvelle mesure d’information universelle basée sur la complexité de Lempel-Ziv appelée SALZA. L’implémentation et la bonne définition de notre mesure permettent un calcul efficace des grandeurs de la théorie algorithmique de l’information.Les compresseurs sans perte usuels ont été utilisés par Cilibrasi et Vitányi pour former un classifieur universel très populaire : la distance de compression normalisée [NCD]. Dans le cadre de cette application, nous proposons notre propre estimateur, la NSD, et montrons qu’il s’agit d’une semi-distance universelle sur les chaînes de symboles. La NSD surclasse la NCD en s’adaptant naturellement à davantage de diversité des données et en définissant le conditionnement adapté grâce à SALZA.En utilisant les qualités de prédiction universelle de la complexité de Lempel-Ziv, nous explorons ensuite les questions d’inférence de causalité. Dans un premier temps, les conditions algorithmiques de Markov sont rendues calculables grâce à SALZA. Puis en définissant pour la première l’information dirigée algorithmique, nous proposons une interprétation algorithmique de la causalité de Granger algorithmique. Nous montrons, sur des données synthétiques et réelles, la pertinence de notre approche. / Data in the form of strings are varied (DNA, text, quantify EEG) and cannot always be modeled. A universal description of strings, independent of probabilities, is thus necessary. The Kolmogorov complexity was introduced in 1960 to address the issue. The principle is simple: a string is complex if a short description of it does not exist. The Kolmogorov complexity is the counterpart of the Shannon entropy and defines the algorithmic information theory. Yet, the Kolmogorov complexity is not computable in finit time making it unusable in practice.The first ones to make operational the Kolmogorov complexity are Lempel and Ziv in 1976 who proposed to restrain the operations of the description. Another approach uses the size of the compressed string by a lossless data compression algorithm. Yet these two estimators are not well-defined regarding the joint and conditional complexity cases. So, compressors and Lempel-Ziv complexity are not valuable to estimate algorithmic information theory.In the light of this observation, we introduce a new universal information measure based on the Lempel-Ziv complexity called SALZA. The implementation and the good definition of our measure allow computing efficiently values of the algorithmic information theory.Usual lossless compressors have been used by Cilibrasi and Vitányi to define a very popular universal classifier: the normalized compression distance [NCD]. As part of this application, we introduce our own estimator, called the NSD, and we show that the NSD is a universal semi-distance between strings. NSD surpasses NCD because it gets used to a large data set and uses the adapted conditioning with SALZA.Using the accurate universal prediction quality of the Lempel-Ziv complexity, we explore the question of causality inference. At first, we compute the algorithmic causal Markov condition thanks to SALZA. Then we define, for the first time, the algorithmic directed information and based on it we introduce the algorithmic Granger causality. The relevance of our approach is demonstrated on real and synthetic data.

No description available.