Measuring complexity to infer changes in the dynamics of ecological systems under stress

Despite advances in our mechanistic understanding of ecological processes, the inherent complexity of real-world ecosystems still limits our ability in predicting ecological dynamics especially in the face of on-going environmental stress. Developing a model is frequently challenged by structure uncertainty, unknown parameters, and limited data for exploring out-of-sample predictions. One way to address this challenge is to look for patterns in the data themselves in order to infer the underlying processes of an ecological system rather than to build system-specific models. For example, it has been recently suggested that statistical changes in ecological dynamics can be used to infer changes in the stability of ecosystems as they approach tipping points. For computer scientists such inference is similar to the notion of a Turing machine: a computational device that could execute a program (the process) to produce the observed data (the pattern). Here, we make use of such basic computational ideas introduced by Alan Turing to recognize changing patterns in ecological dynamics in ecosystems under stress. To do this, we use the concept of Kolmogorov algorithmic complexity that is a measure of randomness. In particular, we estimate an approximation to Kolmogorov complexity based on the Block Decomposition Method (BDM). We apply BDM to identify changes in complexity in simulated time-series and spatial datasets from ecosystems that experience different types of ecological transitions. We find that in all cases, K_BDM complexity decreased before all ecological transitions both in time-series and spatial datasets. These trends indicate that loss of stability in the ecological models we explored is characterized by loss of complexity and the emergence of a regular and computable underlying structure. Our results suggest that Kolmogorov complexity may serve as tool for revealing changes in the dynamics of ecosystems close to ecological transitions.     

Temporal Structure of Human Gaze Dynamics Is Invariant During Free Viewing

We investigate the dynamic structure of human gaze and present an experimental study of the frequency components of the change in gaze position over time during free viewing of computer-generated fractal images. We show that changes in gaze position are scale-invariant in time with statistical properties that are characteristic of a random walk process. We quantify and track changes in the temporal structure using a well-defined scaling parameter called the Hurst exponent, H. We find H is robust regardless of the spatial complexity generated by the fractal images. In addition, we find the Hurst exponent is invariant across all participants, including those with distinct changes to higher order visual processes due to neural degeneration. The value we find for H of 0.57 shows that the gaze dynamics during free viewing of fractal images are consistent with a random walk process with persistent movements. Our research suggests the human visual system may have a common strategy that drives the dynamics of human gaze during exploration.     

On the Fractal Geometry of DNA by the Binary Image Analysis

The multifractal analysis of binary images of DNA is studied in order to define a methodological approach to the classification of DNA sequences. This method is based on the computation of some multifractality parameters on a suitable binary image of DNA, which takes into account the nucleotide distribution. The binary image of DNA is obtained by a dot-plot (recurrence plot) of the indicator matrix. The fractal geometry of these images is characterized by fractal dimension (FD), lacunarity, and succolarity. These parameters are compared with some other coefficients such as complexity and Shannon information entropy. It will be shown that the complexity parameters are more or less equivalent to FD, while the parameters of multifractality have different values in the sense that sequences with higher FD might have lower lacunarity and/or succolarity. In particular, the genome of Drosophila melanogaster has been considered by focusing on the chromosome 3r, which shows the highest fractality with a corresponding higher level of complexity. We will single out some results on the nucleotide distribution in 3r with respect to complexity and fractality. In particular, we will show that sequences with higher FD also have a higher frequency distribution of guanine, while low FD is characterized by the higher presence of adenine.     

Fractal landscapes and molecular evolution: modeling the myosin heavy chain gene family.

Mapping nucleotide sequences onto a "DNA walk" produces a novel representation of DNA that can then be studied quantitatively using techniques derived from fractal landscape analysis. We used this method to analyze 11 complete genomic and cDNA myosin heavy chain (MHC) sequences belonging to 8 different species. Our analysis suggests an increase in fractal complexity for MHC genes with evolution with vertebrate > invertebrate > yeast. The increase in complexity is measured by the presence of long-range power-law correlations, which are quantified by the scaling exponent alpha. We develop a simple iterative model, based on known properties of polymeric sequences, that generates long-range nucleotide correlations from an initially noncorrelated coding region. This new model-as well as the DNA walk analysis-both support the intron-late theory of gene evolution.     

不同状态下脑电图复杂性探索

Ｌｅｍｐｅｌ－Ｚｉｖ所定义的有限序列的复杂性反映了给定序列随其长度的增长出现新模式的速率,事实上它反映了序列接近随机的程度。将该复杂性度量运用于脑电分析,旨在克服分数维方法的缺陷。文中计算了八种实验条件下脑电图的复杂度,涉及看、听、休息和心算等基本的大脑功能状态,１３个被试的１６导数据被用于计算分析．结果显示了复杂度在不同电极位置及实验条件下都有变化,睁眼状态的复杂度高于闭眼,而施加任务时有额部大脑活动区域复杂度降低的现象。同时复杂度也提供了一些研究大脑高级认知活动的新思路。     

A general framework for biclustering gene expression data

A large number of biclustering methods have been proposed to detect patterns in gene expression data. All these methods try to find some type of biclusters but no one can discover all the types of patterns in the data. Furthermore, researchers have to design new algorithms in order to find new types of biclusters/patterns that interest biologists. In this paper, we propose a novel approach for biclustering that, in general, can be used to discover all computable patterns in gene expression data. The method is based on the theory of Kolmogorov complexity. More precisely, we use Kolmogorov complexity to measure the randomness of submatrices as the merit of biclusters because randomness naturally consists in a lack of regularity, which is a common property of all types of patterns. On the basis of algorithmic probability measure, we develop a Markov Chain Monte Carlo algorithm to search for biclusters. Our method can also be easily extended to solve the problems of conventional clustering and checkerboard type biclustering. The preliminary experiments on simulated as well as real data show that our approach is very versatile and promising.     

Determinants and interindividual variation of R-R interval dynamics in healthy middle-aged subjects

Determinants and intersubject variations of fractal and complexity measures of R-R interval variability were studied in a random population of 200 healthy middle-aged women (age 51 +/- 6 yr) and 189 men (age 50 +/- 6 yr) during controlled conditions in the supine and sitting positions. The short-term fractal exponent (alpha(1)) was lower in women than men in both the supine (1.18 +/- 0.20 vs. 1.12 +/- 0.17, P < 0.01) and sitting position (P < 0.001). Approximate entropy (ApEn), a measure of complexity, was higher in women in the sitting position (1.16 +/- 0.17 vs. 1.07 +/- 0.19, P < 0.001), but no gender-related differences were observed in ApEn in the supine position. Fractal and complexity measures were not related to any other demographic, laboratory, or lifestyle factors. Intersubject variations in a fractal measure, alpha(1) (e.g., 1.15 +/- 0.20 in the supine position, z value 1.24, not significant), and in a complexity measure, ApEn (e.g., 1.14 +/- 0.18 in the supine position, z value 1.44, not significant), were generally smaller and more normally distributed than the variations in the traditional measures of heart rate variability (e.g., standard deviation of R-R intervals 49 +/- 21 ms in the supine position, z value 2.53, P < 0.001). These results in a large random population sample show that healthy subjects express relatively little interindividual variation in the fractal and complexity measures of heart rate behavior and, unlike the traditional measures of heart rate variability, they are not related to lifestyle, metabolic, or demographic variables. However, subtle gender-related differences are also present in fractal and complexity measures of heart rate behavior.     

Efficient Physical Embedding of Topologically Complex Information Processing Networks in Brains and Computer Circuits

Nervous systems are information processing networks that evolved by natural selection, whereas very large scale integrated (VLSI) computer circuits have evolved by commercially driven technology development. Here we follow historic intuition that all physical information processing systems will share key organizational properties, such as modularity, that generally confer adaptivity of function. It has long been observed that modular VLSI circuits demonstrate an isometric scaling relationship between the number of processing elements and the number of connections, known as Rent''s rule, which is related to the dimensionality of the circuit''s interconnect topology and its logical capacity. We show that human brain structural networks, and the nervous system of the nematode C. elegans, also obey Rent''s rule, and exhibit some degree of hierarchical modularity. We further show that the estimated Rent exponent of human brain networks, derived from MRI data, can explain the allometric scaling relations between gray and white matter volumes across a wide range of mammalian species, again suggesting that these principles of nervous system design are highly conserved. For each of these fractal modular networks, the dimensionality of the interconnect topology was greater than the 2 or 3 Euclidean dimensions of the space in which it was embedded. This relatively high complexity entailed extra cost in physical wiring: although all networks were economically or cost-efficiently wired they did not strictly minimize wiring costs. Artificial and biological information processing systems both may evolve to optimize a trade-off between physical cost and topological complexity, resulting in the emergence of homologous principles of economical, fractal and modular design across many different kinds of nervous and computational networks.     

Fractal analysis of the Orce skull sutures

Methods of fractal geometry (Mandelbrot, 1983) are used here to analyse the relative complexity of the sagittal and lambdoid sutures visible in the skull fragment formed by parts of an occipital squame and parietals found in a sealed deposit at the early Lower Pleistocene site of Venta Micena (Orce, Granada, Spain), generally regarded as human bone but occasionally suggested as belonging to an equid. For comparison with the fossil, corresponding sutures of various primates (hominids, pongids and cercopithecids) and two other groups of mammals (equids and ruminants) were analysed using the computer program FRACTAL-D (Slice, 1989) in order to determine their fractal dimensions as a measure of differential sutural design complexity. The results show that the fractal dimension of the Venta Micena skull sutures lies within the range of variation for infant specimens of both modern and Plio-Pleistocene hominids. Sutural complexity in young pongids and cercopithecids overlaps the range of fractal dimensions found in hominids, whereas values obtained from equids and ruminants are significantly greater than those for all the primates analysed here. Therefore, in terms of fractal dimension measures of relative complexity, the sutures preserved in the Venta Micena fossil could not have belonged to an equid (pace Agusti & Moyà-Sola, 1987); rather, its fractal dimension is consistent with the attribution of the fossil to an infant of Homo sp.     

Structural complexity of species assemblages and spatial scale of community organization: A case study of marine benthos

In this paper, definitions and measures of complexity with regard to biological communities are briefly considered. A new topological approach that considers the community's complexity in terms of groups of species coherently varied in space or time is proposed. For a given set of samples, the number of such groups is related to the minimal number M of axes necessary to represent the original configuration of the data set. I interpret this “minimal dimensionality of structure” as the number of independent factors of structural variability and its normalized value M/M_MAX as a measure of the organizational complexity of a community. The M value can be estimated as the number of significant axes obtained by ordination procedures. The percentage of total variance explained by these axes, T, is used as measure of structural rigidity. This approach is applied to data on the multi-scaled spatial distribution of marine benthic ciliates and macrofauna. Both the M and the T values obtained by principal component analysis show significant scale-dependence with an evident threshold at some critical area, with values of zero below this threshold, then increasing sharply as the area extends beyond the threshold. The critical scale of community organization ranges from hundreds of meters to kilometers for macroorganisms, whereas several meters are sufficient when considering ciliates.     

SEGMENT: identifying compositional domains in DNA sequences

MOTIVATION: DNA sequences are formed by patches or domains of different nucleotide composition. In a few simple sequences, domains can simply be identified by eye; however, most DNA sequences show a complex compositional heterogeneity (fractal structure), which cannot be properly detected by current methods. Recently, a computationally efficient segmentation method to analyse such nonstationary sequence structures, based on the Jensen-Shannon entropic divergence, has been described. Specific algorithms implementing this method are now needed. RESULTS: Here we describe a heuristic segmentation algorithm for DNA sequences, which was implemented on a Windows program (SEGMENT). The program divides a DNA sequence into compositionally homogeneous domains by iterating a local optimization procedure at a given statistical significance. Once a sequence is partitioned into domains, a global measure of sequence compositional complexity (SCC), accounting for both the sizes and compositional biases of all the domains in the sequence, is derived. SEGMENT computes SCC as a function of the significance level, which provides a multiscale view of sequence complexity.     

Insertions and deletions as phylogenetic signal in an alignment-free context

Most methods for phylogenetic tree reconstruction are based on sequence alignments; they infer phylogenies from substitutions that may have occurred at the aligned sequence positions. Gaps in alignments are usually not employed as phylogenetic signal. In this paper, we explore an alignment-free approach that uses insertions and deletions (indels) as an additional source of information for phylogeny inference. For a set of four or more input sequences, we generate so-called quartet blocks of four putative homologous segments each. For pairs of such quartet blocks involving the same four sequences, we compare the distances between the two blocks in these sequences, to obtain hints about indels that may have happened between the blocks since the respective four sequences have evolved from their last common ancestor. A prototype implementation that we call Gap-SpaM is presented to infer phylogenetic trees from these data, using a quartet-tree approach or, alternatively, under the maximum-parsimony paradigm. This approach should not be regarded as an alternative to established methods, but rather as a complementary source of phylogenetic information. Interestingly, however, our software is able to produce phylogenetic trees from putative indels alone that are comparable to trees obtained with existing alignment-free methods.     

Exploiting Nonlinear Recurrence and Fractal Scaling Properties for Voice Disorder Detection

Background  

Voice disorders affect patients profoundly, and acoustic tools can potentially measure voice function objectively. Disordered sustained vowels exhibit wide-ranging phenomena, from nearly periodic to highly complex, aperiodic vibrations, and increased "breathiness". Modelling and surrogate data studies have shown significant nonlinear and non-Gaussian random properties in these sounds. Nonetheless, existing tools are limited to analysing voices displaying near periodicity, and do not account for this inherent biophysical nonlinearity and non-Gaussian randomness, often using linear signal processing methods insensitive to these properties. They do not directly measure the two main biophysical symptoms of disorder: complex nonlinear aperiodicity, and turbulent, aeroacoustic, non-Gaussian randomness. Often these tools cannot be applied to more severe disordered voices, limiting their clinical usefulness.     

Statistic Complexity: Combining Kolmogorov Complexity with an Ensemble Approach

Background

The evaluation of the complexity of an observed object is an old but outstanding problem. In this paper we are tying on this problem introducing a measure called statistic complexity.

Methodology/Principal Findings

This complexity measure is different to all other measures in the following senses. First, it is a bivariate measure that compares two objects, corresponding to pattern generating processes, on the basis of the normalized compression distance with each other. Second, it provides the quantification of an error that could have been encountered by comparing samples of finite size from the underlying processes. Hence, the statistic complexity provides a statistical quantification of the statement ‘ is similarly complex as ’.

Conclusions

The presented approach, ultimately, transforms the classic problem of assessing the complexity of an object into the realm of statistics. This may open a wider applicability of this complexity measure to diverse application areas.     

Prediction of protein structural class using a complexity-based distance measure

Knowledge of structural class plays an important role in understanding protein folding patterns. So it is necessary to develop effective and reliable computational methods for prediction of protein structural class. To this end, we present a new method called NN-CDM, a nearest neighbor classifier with a complexity-based distance measure. Instead of extracting features from protein sequences as done previously, distance between each pair of protein sequences is directly evaluated by a complexity measure of symbol sequences. Then the nearest neighbor classifier is adopted as the predictive engine. To verify the performance of this method, jackknife cross-validation tests are performed on several benchmark datasets. Results show that our approach achieves a high prediction accuracy over some classical methods.     

Effects of macrophyte architecture and leaf shape complexity on structural parameters of the epiphytic algal community in a Pampean stream

Habitat heterogeneity is one of the main factors determining distribution of organisms, and vegetation is of primary importance in shaping the structural environment in aquatic systems. The effect of macrophyte complexity on macroinvertebrates has been well researched; however, much remains to be revealed about the influence of complexity on epiphytic algae. Here, we used fractal dimension to study the effect of complexity at two scales, macrophyte architecture and leaf shape, on several parameters of the epiphytic algal community (number of individuals, biomass, taxon richness and diversity) in a Pampean stream. Four submerged macrophyte species with different complexities and associated algae were sampled in late spring, summer and autumn. Important differences were found in fractal dimension of the whole plant and leaves among macrophyte species. The particulate organic matter and chlorophyll a associated positively to leaf fractal dimension, but not to plant fractal dimension, partially supporting the hypothesis of a positive effect of macrophyte complexity on periphyton biomass. No association was found in fractal dimension with algal abundance, taxon richness or diversity. Complementary, a mesocosm experiment was performed with plastic imitations of different plant fractal dimensions. After four weeks, there were differences in chlorophyll a and autotrophy index between treatments that suggested a positive effect of complexity on autotrophic periphyton biomass. These results indicate that the well-known positive effect of macrophyte complexity on macroinvertebrates might be partially explained by a positive effect of complexity on periphyton biomass.     

Analysis of fractal dimension of O2A glial cells differentiating in vitro

Fractal dimension is a quantitative measure of morphological complexity. Glial cells of the oligodendrocyte-type 2 astrocyte (O2A) lineage exhibit increasing morphological complexity as they differentiate in vitro. Enriched populations of O2A progenitor cells isolated from neonatal rat cerebral hemispheres or optic nerves were allowed to differentiate in vitro, and their fractal dimensions were measured over time. The fractal dimensions of the maturing cells correlated with perceived complexity; cells with elaborate process branching had larger fractal dimensions than cells with a simpler morphology. An analysis of changes in fractal dimension revealed distinct rates of growth for both oligodendrocytes and type 2 astrocytes. The fractal dimension remained constant over a 10-fold range in optical magnification, demonstrating that cultured O2A glial cells exhibit self-similarity, a defining characteristic of fractal objects. These results illustrate that fractal dimension analysis of maturing cell populations is a useful method for quantitatively describing the process of cell differentiation.     

Local Renyi entropic profiles of DNA sequences

Background  

In a recent report the authors presented a new measure of continuous entropy for DNA sequences, which allows the estimation of their randomness level. The definition therein explored was based on the Rényi entropy of probability density estimation (pdf) using the Parzen's window method and applied to Chaos Game Representation/Universal Sequence Maps (CGR/USM). Subsequent work proposed a fractal pdf kernel as a more exact solution for the iterated map representation. This report extends the concepts of continuous entropy by defining DNA sequence entropic profiles using the new pdf estimations to refine the density estimation of motifs.     

Development of Scoring Functions for Antibody Sequence Assessment and Optimization

Antibody development is still associated with substantial risks and difficulties as single mutations can radically change molecule properties like thermodynamic stability, solubility or viscosity. Since antibody generation methodologies cannot select and optimize for molecule properties which are important for biotechnological applications, careful sequence analysis and optimization is necessary to develop antibodies that fulfil the ambitious requirements of future drugs. While efforts to grab the physical principles of undesired molecule properties from the very bottom are becoming increasingly powerful, the wealth of publically available antibody sequences provides an alternative way to develop early assessment strategies for antibodies using a statistical approach which is the objective of this paper. Here, publically available sequences were used to develop heuristic potentials for the framework regions of heavy and light chains of antibodies of human and murine origin. The potentials take into account position dependent probabilities of individual amino acids but also conditional probabilities which are inevitable for sequence assessment and optimization. It is shown that the potentials derived from human sequences clearly distinguish between human sequences and sequences from mice and, hence, can be used as a measure of humaness which compares a given sequence with the phenotypic pool of human sequences instead of comparing sequence identities to germline genes. Following this line, it is demonstrated that, using the developed potentials, humanization of an antibody can be described as a simple mathematical optimization problem and that the in-silico generated framework variants closely resemble native sequences in terms of predicted immunogenicity.