arXiv:1708.01751v2 [q-bio.QM] 8 Aug 2017

DNA Sequence Complexity Reveals Structure
Beyond GC Content in Nucleosome Occupancy
Hector Zenil 1,2

∗

Peter Minary 1

August 9, 2017
1

Department of Computer Science, University of Oxford, Oxford, U.K.
Algorithmic Dynamics Lab, Unit of Computational Medicine, SciLife Lab,
Centre for Molecular Medicine, Department of Medicine Solna, Karolinska Institute, Stockholm, Sweden.
2

Abstract
We introduce methods that rapidly evaluate a battery of informationtheoretic and algorithmic complexity measures on DNA sequences in application to potential binding sites for nucleosomes. The first application
of this new tool demonstrates structure beyond GC content on DNA sequences in the context of nucleosome binding. We tested the measures on
well-studied genomic sequences of size 20K and 100K bps. The measures
reveal the known in vivo versus in vitro predictive discrepancies, but they
also uncover the internal structure of G and C within the nucleosome
length, thus disclosing more than simply GC content when one examines
alphabet transformations that separate and scramble the GC content signal and the DNA sequence. Most current prediction methods are based
upon training (e.g. k-mer discovery), the one here advanced, however,
is a training-free approach to investigating informative measures of DNA
information content in connection with structural nucleosomic packing.
Keywords: Nucleosome positioning/occupancy; DNA sequence complexity; DNA structure; genomic information content

1

The challenge of Predicting Nucleosome Organization

DNA in the cell is organized into a compact form, called chromatin. Nucleosome
organization in the cell is referred to as the primary chromatin structure and
can depend on the ‘suitability’ of a sequence for accommodating a nucleosome,
which may in turn be influenced by the packing of neighbouring nucleosomes.
Depending on the context, nucleosomes can inhibit or facilitate transcription
∗ To

whom correspondence should be addressed: hector.zenil@algorithmicnaturelab.org

1

factor binding and are thus a very active area of research. The location of low
nucleosomic occupancy is key to understanding active regulatory elements and
genetic regulation that is not directly encoded in the genome but rather in a
structural layer of information.
Structural organization of DNA in the chromosomes is widely known to be
heavily driven by GC content, involving a simple count of G and C occurrences
in the DNA sequence. Despite its simplicity, uncovering exactly how (and to
what extent) GC content drives/affects nucleosome organization is among the
central questions in modern molecular biology.
GC content, local and short-range signals carried by DNA sequence ‘motifs’
or fingertips (k-mer statistical regularities), have been found (Refs. [1] and [2])
to be able to determine a good fraction of the structural (and thus functional)
properties of DNA, such as nucleosome occupancy, but the explanatory (and
predictive) power of GC content (the G or C count in a sequence) alone and
sequence motifs display very significant differences in vivo versus in vitro [3].
Despite intensive analysis of the statistical correspondence between in vitro
and in vivo positioning, there is a lack of consensus as to the degree to which
the nucleosome landscape is intrinsically specified by the DNA sequence [4], as
well as in regards to the apparently profound difference in dependence in vitro
versus in vivo. Because the nucleosome landscape is known to be significantly
dependent on the DNA sequence, it encodes the structural information of the
DNA (particularly demonstrated in vitro). We consider this an opportunity
to compare the performance of complexity measures, in order to discover how
much of the information encoded in a sequence in the context of the nucleosome landscape can be recovered from information-content versus algorithmic
complexity measures. Nucleosome location is thus an ideal test case to probe
how informative sequence-based indices of complexity can be in determining a
structural (and ultimately functional) property of genomic DNA.

1.1

Algorithmic Information Theory in Genomic Sequence
Profiling

Previous applications of measures based upon algorithmic complexity include
experiments on the evaluation of lossless compression lengths of sets of genomes [5,
7] and more recently [13] with interesting results. For example, in a landmark
paper in the area, a measure of algorithmic mutual information was introduced
to distinguish sequence similarities by way of minimal encodings and lossless
compression algorithms in which a mitochondrial phylogenetic tree that conformed to the evolutionary history of known species was reconstructed [6, 7].
These approaches have, however, either been purely theoretical or have effectively been reduced to applications of Shannon entropy rather than of algorithmic complexity because, implementations of lossless compression are actually
entropy estimators [8, 38]. In some other cases, control tests have been missing. For example, in the comparison of the compressibility indices of different
genomes [6, 7], GC content (counting every G and C in the sequence) can reconstruct the same if not a more accurate phylogenetic tree. This is because
2

two species that are close to each other evolutionarily will have similar GC content (see e.g. [9]). Species close to each other will have similar DNA sequence
entropy values, allowing lossless compression algorithms to compress statistical
regularities of genomes of related species with similar compression rates. Here
we intend to go beyond previous attempts, in breadth as well as depth, using
better-grounded algorithmic measures and more biologically relevant test cases.

1.2

Current Sequence-based Prediction Methods

While the calculation of GC content is extremely simple, the reasons behind its
ability to predict the structural properties of DNA are largely unknown [10, 11].
For example, it has been shown that low GC content can explain low occupancy,
but high GC content can mean either high or low occupancy [12].
Current algorithms that build upon while probing beyond GC content have
been largely influenced by sequence motif ([14, 2]) and dinucleotide models
[15]—and to a lesser degree by k-mers [1], DNA sequence motifs that are experimentally isolated and used for their informative value in determining the
structural properties of DNA.
Table 1 (SI) shows the in vitro nucleosome occupancy dependence on GC
content, with a correlation of 0.684 (similar to that reported by Kaplan [3]) for
the well-studied 20K bp genomic region (187K – 207K) of Yeast Chromosome
14 [16]. Knowledge-based methods dependent on observed sequence motifs [17,
18] are computationally cost-efficient alternatives for predicting genome-wide
nucleosome occupancy. However, they are trained on experimental statistical
data and are not able to predict anything that has not been observed before.
They also require context, as it may not be sufficient to consider only short
sequence motifs such as dinucleotides [19, 3].
More recently, deep machine learning techniques have been applied to DNA
accessibility related to chromatin and nucleosome occupancy [17]. However,
these techniques require a huge volume of data for training if they are to predict
just a small fraction of data with marginally improved accuracy as compared to
more traditional approaches based on k-mers, and they have not shed new light
on the sequence dependence of occupancy.
Here we test the ability of a general set of measures, statistical and algorithmic, to be informative about nucleosome occupancy and/or about the relationship between the affinity of nucleosomes with certain sequences and their
complexities.

2
2.1

Methods
The Dinucleotide Wedge Model

The formulation of models of DNA bending was initially prompted by a recognition that DNA must be bent for packaging into nucleosomes, and that bending
would be an informative index of nucleosome occupancy. Various dinucleotide

3

models can account reasonably well for the intrinsic bending observed in different sets of sequences, especially those containing A-tracts [19].
The Wedge model [20] suggests that bending is the result of driving a wedge
between adjacent base pairs at various positions in the DNA. The model assumes
that bending can be explained by wedge properties attributed solely to an AA
dinucleotide (8.7 degrees for each AA). No current model provides a completely
accurate explanation of the physical properties of DNA such as bending [21],
but the Wedge model (like the more basic Junction model which is less suitable
for short sequences and less general [22]) reasonably predicts the bending of
many DNA sequences [23]. Although it has been suggested that trinucleotide
models may make for greater accuracy in explaining DNA curvature in some of
the sequences, dinucleotide models remain the most effective [19].

2.2

The Segal Model

Segal et al. established a probabilistic model to characterize the possibility
that one DNA sequence is occupied by a nucleosome [16]. They constructed a
nucleosome-DNA interaction model and used a hidden Markov model (HMM)
to obtain a probability score. The model is based mainly on a 10-bp sequence
periodicity that indicates the probability of any base pair being covered by a
nucleosome.
All k-nucleotide models, including that of Segal et al., are based upon
knowledge-based sequence motifs and are thereby dependent on certain previously learned patterns. They can only account for local curvature and local
predictions, not longer range correlations. Perhaps the fact that k-nucleotide
models for k > 2 have not been proven to provide a significant advantage over
k = 2 has led researchers to disregard longer range signals across DNA sequences
involved in both DNA curvature and nucleosome occupancy [24]. To date, these
models, including that of Kaplan [3] (which considers up to k = 5) and of Segal
et al., are considered the gold standard for comparison purposes.
To study the extent of different signals in the determination of nucleosome
occupancy, we applied some basic transformations to the original genomic DNA
sequence. The SW transformation substitutes G and C for S (Strong interaction), and A and T for W (for Weak interaction). The RY transformation
substitutes A and G for R (for puRines), and C and T for Y (pYrimidines).

2.3

Complexity-based Genomic Profiling

In what follows, we generate a function score fc for every complexity measure c
(detailed descriptions in the S.I.) by applying each measure to a sliding window
of length 147 nucleotides (nts) across a 20K and 100K base pair (bps) DNA
sequence from Yeast chromosome 14. At every position of the sliding window,
we get a sequence score for every c that is used to compare against in vivo and
in vitro experimental occupancy.
The following measures (followed by the name we refer to in parenthesis
throughout the text) are here introduced. Among the measures considered are
4

Figure 1: Top: Correlation values of nucleosome occupancy (measured experimentally from chromosomic Yeast) on a sliding window of length 4K nt for both
in vitro and in vivo against different measures/signals: the occupancy predictive Segal model (clearly better for in vitro). Middle: Calculated correlation
values between the SW DNA transformation, carrying the GC content signal,
found highly correlated to the Segal model but poorly explaining in vivo occupancy data. Bottom: The RY DNA transformation, an orthogonal signal to SW
(and thus to GC content) whose values report a non-negligible max-min correlation, suggesting that the mixing of AT and GC carries some information about
nucleosome occupancy (even if weaker than GC content), with in vivo values
showing greatest correlation values unlike SW/GC and thus possibly neglected
in predictive models (such as Segal’s).

5

entropy-based ones (see Supplementary Material for exact definitions):
• Shannon entropy (Entropy) with uniform probability distribution.
• Entropy rate with uniform probability distribution.
• Lossless compression (Compress)
A set of measures of algorithmic complexity (see Supplementary Material
for exact definitions):
• Coding Theorem Method (CTM) as an estimator of algorithmic randomness by way of algorithmic probability via the algorithmic Coding theorem
(see Supplementary Material) relating causal content and classical probability [33, 34].
• Logical Depth (LD) as a BDM-based (see below) estimation of logical
depth [25], a measure of sophistication that assigns both algorithmically
simple and algorithmically random sequences shallow depth, and everything else higher complexity, believed to be related to biological evolution [26, 27].
And a hybrid measure of complexity combining local approximations of algorithmic complexity by CTM and global estimations of (block) Shannon entropy
(see Supplementary Material for exact definitions):
• The Block Decomposition Method (BDM) that approximates Shannon
entropy—up to a logarithmic term—for long sequences, but KolmogorovChaitin complexity otherwise, as in the case of short nucleotides [28].
We list lossless compression under information-theoretic measures and not
under algorithmic complexity measures, because implementations of lossless
compression algorithms such as Compress and all those based on LempelZivWelch
(LZ or LZW) as well as derived algorithms (ZIP, GZIP, PNG, etc.) are actually
entropy estimators [38, 8, 28].
BDM allows us to expand the range of application of both CTM and LD to
longer sequences by using Shannon entropy. However, if sequences are divided
into short enough subsequences (of 12 nucleotides) we can apply CTM and avoid
any trivial connection to Shannon entropy and thus to GC content.
Briefly, to estimate the algorithmic probability [29, 30]—on which the measure BDM is based—of a DNA sequence (e.g. the sliding window of length
147 nucleoides or nt), we produce an empirical distribution [33, 34] to compare with by running a sample of up to 325 433 427 739 Turing machines with
2 states and 4 symbols (the number of nucleotide types in a DNA sequence)
with empty input. If a DNA sequence is algorithmically random, then very
few computer programs (Turing machines) will produce it, but if it has a regularity, either statistical or algorithmic, then there is a high probability of its
being produced. Producing approximations to algorithmic probability provides
approximations to algorithmic complexity by way of the so-called algorithmic
6

Coding Theorem [30, 33, 34]. Because the procedure is computationally expensive (and ultimately uncomputable) only the full set of strings of up to 12 bits
was produced, and thus direct values can be given only to DNA sequences of
up to 12 digits (binary for RY and SW and quaternary for full-alphabet DNA
sequences).
The tool is available at http://complexitycalculator.com/ where the
user can calculate the information content and algorithmic complexity using
the methods here introduced on any DNA segment for the purpose of similar of
any other investigation of the structure of DNA and beyond.

3
3.1

Results
Complexity-based Indices

Fig. 1 shows the correlations between in vivo, in vitro, and the Segal model. In
contrast, the SW transformation captures GC content, which clearly drives most
of the nucleosome occupancy, but the correlation with the RY transformation
that loses all GC content is very interesting. While significantly lower, it is
existent and indicates a signal not contained in the GC content alone, as verified
in Fig. 4.
In Table 1 (SI), we report the correlation values found between experimental nucleosome occupancy data and ab initio training-free complexity measures.
BDM alone explains more than any other index, including GC content in vivo,
and unlike all other measures LD is negatively correlated, as theoretically expected [35] and numerically achieved [28], it being a measure that assigns low
logical depth to high algorithmic randomness, with high algorithmic randomness
implying high entropy (but not the converse).
Surprisingly, entropy alone does not capture all the GC signals, which means
that there is more structure in the distributions of Gs and Cs beyond the GC
content alone. However, entropy does capture GC content in vivo, suggesting
that local nucleotide arrangements (for example, sequence motifs) have a greater
impact on in vivo prediction. Compared to entropy, BDM displays a higher
correlation with in vivo nucleosome occupancy, thereby suggesting more internal
structure than is captured by GC content and Shannon entropy alone.

3.2

Model Curvature versus Complexity Indices

The dinucleotide model incorporates knowledge regarding sequence motifs that
are known to have specific natural curvature properties and adds to the knowledge and predictive power that GC content alone offers.
Using the Wedge dinucleotide model we first estimated the predicted curvature on a set of 20 artificially generated sequences (Table 4 (SI)) with different statistical properties, in order to identify possibly informative informationtheoretic and algorithmic indices. As shown in Table 2 (SI), we found all measures negatively correlated to the curvature modelled, except for LD, which

7

displays a positive correlation–and the highest in absolute value–compared to
all the others. Since BDM negatively correlates with curvature, it is expected
that the minima may identify nucleosome positions (see next subsection).
An interesting observation in Table 2 (SI) concerns the correlation values
between artificially generated DNA sequences and DNA structural curvature
according to the Wedge nucleotide model: all values are negatively correlated,
but curvature as predicted by the model positively correlates with LD, in exact inverse fashion vis-a-vis the correlation values reported in Table 1 (SI).
This is consonant with the theoretically predicted relation between algorithmic
complexity and logical depth [28]. All other measures (except for LD) behave
similarly to BDM.
The results in Tables 1 and 2 (SI) imply that for all measures both extrema
(min and max for BDM and max and min for LD) may be indicative of high
nucleosome occupancy. In the next section we explore whether extrema of these
measures are also informative about nucleosome locations.

3.3

Nucleosome Dyad and Centre Location Test

Positioning and occupancy of nucleosomes are closely related. Nucleosome positioning is the distribution of individual nucleosomes along the DNA sequence
and can be described by the location of a single reference point on the nucleosome, such as its dyad of symmetry [36]. Nucleosome occupancy, on the other
hand, is a measure of the probability that a certain DNA region is wrapped
onto a histone octamer.
Fig. 2 shows the predictive capabilities of algorithmic indices for nucleosome
dyad and centre location when nucleosomic regions are placed against a background of (pseudo-) randomly generated DNA sequences with the same average
GC content as themselves (∼ 0.5). BDM outperforms all methods in accuracy
and strength. When taking the local min/max as potential indicators of nucleosome centres, we find that GC content fails (by design, as the surrounding
sequences have the same GC content as the nucleosomic region of interest);
lossless compression (Compress) performs well on the second half of the nucleosomes (left panel) but fails for the first half (right panel). Entropy performs
as poorly as Compress—not surprisingly, as lossless compression algorithms are
Entropy estimators.
The results for BDM and LD suggest that the first 4 nucleosomal DNA sequences, of which 3 are clones, display greater algorithmic randomness (BDM)
than the statistically pseudo-randomly generated background (surrounding sequences), while all other nucleosomes are of significantly lower algorithmic randomness (BDM) and mixed (both high and low) structural complexity (LD).
The same robust results were obtained after several replications with different
pseudo-random backgrounds. Moreover, the signal produced by similar nucleosomes with strong properties [37], such as clones 601, 603 and 605, had similar
shapes and convexity.
Fig. 3 shows the strength of the BDM signal at indicating the nucleosome
centres based on the min/max value of the corresponding functions. The signal8

Figure 2: Nucleosome centre prediction (red dots) of 14 nucleosomes on an
intercalated background of pseudo-random DNA segments of 147 nts with the
same average GC content as the surrounding nucleosomic regions. Values are
normalized between 0 and 1 and they were smoothed by taking one data point
per 40 and using and interpolating order 2. Experimentally known nucleosome
centres (called dyads) are marked with dashed lines. Panels on the right have
their nucleotide centre estimated by the centre of the nucleosomic sequence (also
dashed lines). Predictions are based on the local min/max values (up to 75 nts
to each side) from the actual/estimated dyad/centre. Some red dots may appear
to be placed slightly off but this is because there was a local min or max that
vanished after the main curve was made smoother for visualization purposes.

9

Figure 3: Signal-to-noise ratio histogram. Distributions of centre predicted values demonstrating how BDM and LD are removed from a normal distribution
thus picking a signal, unlike GC content that distributes values normally and
performs no better than chance on a pseudo-random background with similar
GC content. BDM carries the strongest signal followed by LD skewed in the
opposite direction both peaking closer to the nucleosome centres than GC content. On the x-axis are complexity values arranged in bins of 1000 as reported
in Fig. 2.
to-noise ratio is much stronger for BDM, and is also shifted by LD in the opposite direction (to BDM), as would be consistent with the relation between
algorithmic complexity and logical depth (see S.I.).
Both BDM and LD spike at nucleosome positions stronger than GC content
on a random DNA background with the same GC content, and perform better
than entropy and compression. BDM is informative about every dyad or centre
of nucleosomes, with 10 out of the 14 predicted within 1 to 3 bps distance and
the rest within a 20 bps range. Unlike all other measures, LD performed better
for the first half (left panel) of nucleosome centre locations than for the second
half (right panel), suggesting that the nucleosomes of the first half may have
greater structural organization.
Table 3 (SI) compares distances to the nucleosome centres and error percentages as predicted without any training with BDM, to GC content prediction.
The average distance between the predicted and the actual nucleosome centre is
calculated to the closest local extreme (minima or maxima) within a window of
41 base pairs or bps (20 bps to each side plus the centre) from the actual centre
(the experimentally known dyad or the centre nucleotide when the dyad was
not known). In accordance with the results in Table 1 (SI) the maxima of BDM
(minima of LD) could be informative about nucleosome positions and for those
sequences, whose natural curvature is a fit to the superhelix, the minima BDM
(maxima of LD) could also indicate nucleosome locations. This latter finding is
supported by results in Table 2 (SI).
Our results suggest that if some measures of complexity peak where GC
10

content is (purposely) tricked, there must be some structure different to GC
content along the DNA sequence, either a distribution of GC content within the
nucleosome length that is not related simply to the G and C count, or some
other signal.

3.4

Informative Measures of High and Low Occupancy

To find the most informative measures of complexity c we maximized the potential separation by taking only the sequences with highest (X% high) and lowest
(Y% low) nucleosome occupancy. To this end we took as cutoff values 2 and
0.2 respectively, generating 300 disjoint sequences each from a 100K DNA segment for highest and lowest nucleosome occupancy values. The 100K segment
starting and ending points are 187K − 40K and 207K + 40K nts in the 14th
Yeast chromosome, so 40K nts surrounding the original shorter 20K sequence
first explored.
In Fig. 4 it was puzzling to find that the Segal model correlates less strongly
than GC content alone for in vivo, suggesting that the model assigns greater
weight to k-mer information than to GC content for these extreme cases given
that we already knew that the Segal model is mostly driven by GC content
(Fig. 1 middle). The box plot for the Segal model indicates that the model does
not work as well for extreme sequences of high occupancy, with an average of
0.6 where the maximum over the segments on which these nucleosome regions
are contained reaches an average correlation of ∼ 0.85 (in terms of occupancy),
as shown in Fig. 1 for in vitro data. This means that these high occupancy
sequences are on the outer border of the standard deviation in terms of accuracy
in the Segal model.
While the best model is the one that best separates the highest from the lowest occupancy, and therefore is clearly Segal’s model. Except for informationtheoretic indices (entropy and Compress), all algorithmic complexity indices
were found to be informative of high and low occupancy. Moreover, all algorithmic complexity measures display a slight reduction in accuracy in vivo versus
in vitro, as is consistent with the limitations of current models such as Segal’s.
All but the Segal model are, however, training-free measures, in the sense that
they do not contain any k-mer information related to high or low occupancy and
thus are naive indices, yet all algorithmic complexity measures were informative
to different extents, with CTM and BDM performing best and LD performing
worst, LD displaying inverted values for high and low occupancy as theoretically
expected (because LD assigns low LD to high algorithmic complexity) [35]. Also
of note is the fact that CTM and BDM applied to the RY transformation were
informative of high versus low occupancy, thereby revealing a signal different to
GC content that models such as Segal’s partially capture in their encoded k-mer
information. Interestingly, GC content alone outperforms the Segal model for
high occupancy both in vitro and in vivo, but the Segal model outperforms GC
content for low occupancy.
Lossless compression was the worst behaved, showing how CTM and BDM
outperform what is usually used as an estimator of algorithmic complexity [38,
11

Figure 4: Box plots reporting the informative value of complexity indices in
vivo and in vitro for segments of lowest and highest occupancy, providing an
overview of the informative value of sequence-dependent complexity measures.
The occupancy score is given by the re-scaling of the complexity value fc (yaxis) so that the highest value is 1 and the lowest 0. In the case of the Segal
model, fc is the direct score sequence based on the probability assigned by the
model [16], with no re-scaling (because it is already scaled from origin with
probability values between 0 and 1). Other cases not shown (e.g. entropy
rate or Compress on RY or SW) had no significant results. Magenta and pink
(bright colours) signify measures of algorithmic complexity; in dark gray colour
are information-theoretic based measures.

12

8, 28]. Unlike entropy alone, however, lossless compression does take into consideration sequence repetitions, averaging over all k-mers up to the compression
algorithm sliding window length. The results thus indicate that averaging over
all sequence motifs—both informative and not—deletes all advantages, thereby
justifying specific knowledge-driven k-mer approaches introduced in models such
as Segal’s.

4

Conclusions

The Kaplan and Segal models are considered to be the most accurate and the
gold standard for predicting in vitro nucleosome occupancy. However, previous
approaches including Segal and Kaplan requires extensive (pre-)training. In
contrast, all measures considered by our approach are training free.
These training-free measures revealed that there is more structure to nucleosome occupancy than GC content, and potentially to k-mer structure as well
(e.g. non-AT-based mers), based on the correlations found in RY transformations indicative of low versus high occupancy.
The nucleotide location test suggests a complexity hierarchy in which natural non-nucleosomic regions are less algorithmically random than nucleosomic
regions, which in turn are less algorithmically random than pseudo-randomly
generated DNA sequences with GC content equal to the nucleosomic regions.
When pseudo-random regions are placed between nucleosomes, we showed that
BDM tends to identify nucleosomic regions with a preference for lower algorithmic randomness with relative accuracy, and more consistently than GC content,
which showed no pattern and mostly failed, as was expected, when fooled with
a background of similar GC content.
We have thus gone beyond previous attempts to connect and apply measures of complexity to structural and functional properties of genomic DNA,
specifically in the highly active and open challenge of nucleosome occupancy in
molecular biology.
A direction for future research suggested by our work is the exploration
of the use of these complexity indices to complement current machine learning approaches for reducing the feature space, by, e.g., determining which kmers are more and less informative, and thereby ensuring better prediction
results. Another direction is a more extensive investigation of the possible use
of genomic profiling for other types of structural and functional properties of
DNA, with a view to contributing to, e.g., HiC techniques or protein encoding/promoter/enhancer region detection, and to furthering our understanding
of the effect of extending the alphabet transformation of a sequence to epigenetics.

13

References
[1] Gu C et al. (2015) DNA structural correlation in short and long ranges.
The Journal of Physical Chemistry B 119(44):13980–13990.
[2] Schep AN et al. (2015) Structured nucleosome fingerprints enable highresolution mapping of chromatin architecture within regulatory regions.
Genome research 25(11):1757–1770.
[3] Kaplan N et al. (2009) The DNA-encoded nucleosome organization of a
eukaryotic genome. Nature 458(7236):362–366.
[4] Gracey LE et al. (2010) An in vitro-identified high-affinity nucleosomepositioning signal is capable of transiently positioning a nucleosome in
vivo. Epigenetics & chromatin 3(1):1.
[5] Rivals E, Delahaye JP, Dauchet M, Delgrange O (1996) Compression and
genetic sequence analysis. Biochimie 78:315–322.
[6] Li M, Chen X, Li X, Ma B, Vitányi PM (2004) The similarity metric.
IEEE transactions on Information Theory 50(12):3250–3264.
[7] Cilibrasi R, Vitányi PM (2005) Clustering by compression. IEEE Transactions on Information theory 51(4):1523–1545.
[8] Zenil H, Kiani, NA, Tegnér, J (2017) Low Algorithmic Complexity
Entropy-deceiving Graphs Phys Rev E. (accepted)
[9] Pozzoli U et al. (2008) Both selective and neutral processes drive GC
content evolution in the human genome. BMC evolutionary biology 8(1):1.
[10] Tillo D, Hughes TR (2009) G+C content dominates intrinsic nucleosome
occupancy. BMC bioinformatics 10(1):1.
[11] Galtier N, Piganeau G, Mouchiroud D, Duret L (2001) GC-content evolution in mammalian genomes: the biased gene conversion hypothesis.
Genetics 159(2):907–911.
[12] Minary P, Levitt M (2014) Training-free atomistic prediction of nucleosome occupancy. Proceedings of the National Academy of Sciences
111(17):6293–6298.
[13] Diogo Pratas, Armando J. Pinho (2017) On the Approximation of the
Kolmogorov Complexity for DNA Lecture Notes in Computer Science
book series (LNCS), vol. 10255:pp 259–266.
[14] Cui F, Zhurkin VB (2010) Structure-based analysis of DNA sequence patterns guiding nucleosome positioning in vitro. Journal of Biomolecular
Structure and Dynamics 27(6):821–841.

14

[15] Trifonov, E. N., and Sussman, J. L. (1980) The pitch of chromatin DNA
is reflected in its nucleotide sequence. Proc. Natl. Acad. Sci. USA 77, pp.
3816–3820.
[16] Segal E et al. (2006) A genomic code for nucleosome positioning. Nature
442(7104):772–778.
[17] Kelley DR, Snoek J, Rinn JL (2016) Basset: Learning the regulatory
code of the accessible genome with deep convolutional neural networks.
Genome research.
[18] Lee W et al. (2007) A high-resolution atlas of nucleosome occupancy in
yeast. Nature genetics 39(10):1235–1244.
[19] Kanhere A, Bansal M (2003) An assessment of three dinucleotide parameters to predict DNA curvature by quantitative comparison with experimental data. Nucleic acids research 31(10):2647–2658.
[20] Ulanovsky LE, Trifonov EN (1986) Estimation of wedge components in
curved DNA. Nature 326(6114):720–722.
[21] Burkhoff AM, Tullius TD (1988) Structural details of an adenine tract
that does not cause DNA to bend. Nature 331:455–457.
[22] Crothers DM, Haran TE, Nadeau JG (1990) Intrinsically bent DNA. J.
Biol. Chem 265(13):7093–7096.
[23] Sinden RR (2012) DNA structure and function. (Elsevier).
[24] van der Heijden T, van Vugt JJ, Logie C, van Noort J (2012) Sequencebased prediction of single nucleosome positioning and genome-wide nucleosome occupancy. Proceedings of the National Academy of Sciences
109(38):E2514–E2522.
[25] Bennett CH (1995) Logical depth and physical complexity. The Universal
Turing Machine, A Half-Century Survey pp. 207–235.
[26] Bennett CH (1993) Dissipation, information, computational complexity
and the definition of organization in Santa Fe Institute Studies in the Sciences of Complexity -Proceedings Volume-. (Addison-Wesley Publishing
Company), Vol. 1, pp. 215–215.
[27] Hernández-Orozco S, Hernández-Quiroz F, Zenil H (2016) The limits of
decidable states on open-ended evolution and emergence in ALIFE Conference. (MIT Press).
[28] Zenil H, Soler-Toscano F, Kiani NA, Hernández-Orozco S, Rueda-Toicen
A (2016) A decomposition method for global evaluation of Shannon entropy and local estimations of algorithmic complexity. arXiv preprint
arXiv:1609.00110.

15

[29] Solomonoff RJ (1964) A formal theory of inductive inference. parts i and
ii. Information and control 7(1):1–22 and 224–254.
[30] Levin LA (1974) Laws of information conservation (nongrowth) and aspects of the foundation of probability theory. Problemy Peredachi Informatsii 10(3):30–35.
[31] Kolmogorov AN (1968) Three approaches to the quantitative definition of
information. International Journal of Computer Mathematics 2(1-4):157–
168.
[32] Chaitin GJ (1969) On the length of programs for computing finite binary sequences: statistical considerations. Journal of the ACM (JACM)
16(1):145–159.
[33] Delahaye JP, Zenil H (2012) Numerical evaluation of algorithmic complexity for short strings: A glance into the innermost structure of randomness.
Applied Mathematics and Computation 219(1):63–77.
[34] Soler-Toscano F, Zenil H, Delahaye JP, Gauvrit N (2014) Calculating
kolmogorov complexity from the output frequency distributions of small
Turing machines. PloS one 9(5):e96223.
[35] Soler-Toscano F, Zenil H, Delahaye JP, Gauvrit N (2013) Correspondence
and Independence of Numerical Evaluations of Algorithmic Information
Measures Computability, vol. 2, no. 2, pp 125–140.
[36] Klug A, Rhodes D, Smith J, Finch J, Thomas J (1980) A low resolution
structure for the histone core of the nucleosome. Nature 287(5782):509–
516.
[37] Gaykalova DA et al. (2011) A polar barrier to transcription can be circumvented by remodeler-induced nucleosome translocation. Nucleic acids
research p. gkq1273.
[38] Zenil H (2013) Algorithmic data analytics, small data matters and correlation versus causation in Computability of the World? Philosophy and
Science in the Age of Big Data, eds. Pietsch W, Wernecke J, Ott M.
(Springer Verlag). In press.
[39] Collier JD (1998) Information increase in biological systems: how does
adaptation fit? in Evolutionary systems. (Springer), pp. 129–139.
[40] Rado T (1962) On non-computable functions. Bell System Technical Journal 41(3):877–884.

16

Supplementary Material
5

Indices of Information and of Algorithmic Complexity

Here we describe alternative measures to explore correlations from an informationtheoretic and algorithmic (hence causal) complexity perspective.

5.1

Shannon Entropy

Central to information theory is the concept of Shannon’s information entropy,
which quantifies the average number of bits needed to store or communicate a
message. Shannon’s entropy determines that one cannot store (and therefore
communicate) a symbol with n different symbols in less than log(n) bits. In
this sense, Shannon’s entropy determines a lower limit below which no message
can be further compressed, not even in principle. Another application (or interpretation) of Shannon’s information theory is as a measure for quantifying the
uncertainty involved in predicting the value of a random variable.
For an ensemble X(R, p(xi )), the Shannon information content or entropy
of X is then given by
H(X) = −

n
X

p(xi ) log2 p(xi )

i=1

where R is the set of possible outcomes (the random variable), n = |R| and
p(xi ) is the probability of an outcome in R.
5.1.1

Entropy Rate

The function R gives what is variously denominated as rate or block entropy
and is Shannon entropy over blocks or subsequences of X of length b. That is,
b=|X|

R(X) = min H(Xb )
b=1

If the sequence is not statistically random, then R(X) will reach a low value
for some b, and if random, then it will be maximally entropic for all blocks b.
R(X) is computationally intractable as a function of sequence size, and typically
upper bounds are realistically calculated for a fixed value of b (e.g. a window
length). Notice that, as discussed in the main text, having maximal entropy
does not by any means imply algorithmic randomness (c.f. 5.3).

5.2

Compression algorithms

Two widely used lossless compression algorithms were employed.

17

5.2.1

Bzip2

Bzip2 is a lossless compression method that uses several layers of compression techniques stacked one on top of the other, including Run-length encoding
(RLE), BurrowsWheeler transform (BWT), Move to Front (MTF) transform,
and Huffman coding, among other sequential transformations. Bzip2 compresses
more effectively than LZW, LZ77 and Deflate, but is considerably slower.
5.2.2

Compress

Compress is a lossless compression algorithm based on the LZW compression
algorithm. LempelZivWelch (LZW) is a lossless data compression algorithm
created by Abraham Lempel, Jacob Ziv, and Terry Welch, and is considered universal for an infinite sliding window (in practice the sliding window is bounded
by memory or choice). It is considered universal in the sense of Shannon entropy, meaning that it approximates the entropy rate of the source (an input
in the form of a file/sequence). It is the algorithm of the widely used Unix
file compression utility ‘Compress’, and is currently in the international public
domain.

5.3

Measures of Algorithmic Complexity

A binary sequence s is said to be random if its Kolmogorov complexity C(s) is
at least twice its length. It is a measure of the computational resources needed
to specify the object. Formally,
C(s) = min{|p| : T (p) = s}
where p is a program that outputs s running on a universal Turing machine T . A
technical inconvenience of C as a function taking s to the length of the shortest
program that produces s is its uncomputability. This is usually considered a
major problem. The measure was first conceived to define randomness and is
today the accepted objective mathematical measure of complexity, among other
reasons because it has been proven to be mathematically robust (by virtue of
the fact that several independent definitions converge to it).
The invariance theorem guarantees that complexity values will only diverge
by a constant (e.g. the length of a compiler, a translation program between T1
and T2 ) and will converge at the limit. Formally,
|C(s)T1 − C(s)T2 | < c
5.3.1

Lossless Compression as Approximation to C

Lossless compression is traditionally the method of choice when a measure of algorithmic content related to Kolmogorov-Chaitin complexity C is needed. The
Kolmogorov-Chaitin complexity of a sequence s is defined as the length of the

18

shortest computer program p that outputs s running on a reference universal Turing machine T . While lossless compression is equivalent to algorithmic
complexity, actual implementations of lossless compression (e.g. Compress) are
heavily based upon entropy rate estimations [38, 8, 28] that mostly deal with
statistical repetitions or k-mers of up to a window length size L, such that
k ≤ L.
5.3.2

Algorithmic Probability as Approximation to C

Another approach consists in making estimations by way of a related measure,
Algorithmic Probability [33, 34]. The Algorithmic Probability of a sequence s
is the probability that s is produced by a random computer program p when
running on a reference Turing machine T . Both algorithmic complexity and
Algorithmic Probability rely on T , but invariance theorems for both guarantee
that the choice of T is asymptotically negligible.
One way to minimize the impact of the choice of T is to average across a
large set of different Turing machines all of the same size. The chief advantage
of algorithmic indices is that causal signals in a sequence may escape entropic
measures if they do not produce statistical regularities. And it has been the case
that increasing the length of k in k-nucleotide models of structural properties
of DNA have not returned more than a marginal advantage.
The Algorithmic Probability [29] (also known as Levin’s semi-measure [30])
of a sequence s is a measure that describes the expected probability of a random
program p running on a universal prefix-free Turing machine T producing s.
Formally,
X
m(s) =
1/2|p|
p:T (p)=s

The Coding theorem beautifully connects C(s) and m(s):
C(s) ∼ − log m(s)
5.3.3

Bennett’s Logical Depth

Another measure of great interest is logical depth [25]. The logical depth (LD)
of a sequence s is the shortest time logged by the shortest programs pi that produce s when running on a universal reference Turing machine. In other words,
just as algorithmic complexity is associated with lossless compression, LD can
be associated with the shortest time that a Turing machine takes to decompress
the sequence s from its shortest computer description. A multiplicative invariance theorem for LD has also been proven [25]. Estimations of Algorithmic
Probability and logical depth of DNA sequences were performed as determined
in [33, 34].
Unlike algorithmic (Kolmogorov-Chaitin) complexity C, logical depth is a
measure related to ‘structure’ rather than randomness. LD can be identified

19

with biological complexity [26, 39] and is therefore of great interest when comparing different genomic regions.

5.4

Measures Based on Algorithmic Probability and on
Logical Depth

The Coding theorem method (or simply CTM) is a method [33, 34] rooted in the
relation between C(s) and m(s) specified by Algorithmic Probability, that is,
between frequency of production of a sequence from a random program and its
Kolmogorov complexity as described by Algorithmic Probability. Essentially,
it uses the fact that the more frequent a sequence the lower its Kolmogorov
complexity, and sequences of lower frequency have higher Kolmogorov complexity. Unlike algorithms for lossless compression, the Algorithmic Probability
approach not only produces estimations of C for sequences with statistical regularities, but it is deeply rooted in a computational model of Algorithmic Probability, and therefore, unlike lossless compression, has the potential to identify
regularities that are not statistical (e.g. a sequence such as 1234...), that is,
sequences with high entropy or no statistical regularities but low algorithmic
complexity [38, 8].
Let (n, m) be the space of all n-state m-symbol Turing machines, n, m > 1
and s a sequence, then:
D(n, m)(s) =

|{T ∈ (n, m) : T produces s}|
|{T ∈ (n, m)}|

(1)

T is a standard Turing machine as defined in the Busy Beaver problem by
Radó [40] with 4 symbols (in preparation for the calculation of the DNA alphabet size).
Then using the relation established by the Coding theorem, we have:
CT M (s) = − log2 (D(n, m)(s))

(2)

That is, the more frequently a sequence is produced the lower its Kolmogorov
complexity, and vice versa. CTM is an upper bound estimation of KologorovChaitin complexity.
From CTM, a measure of Logical Depth can also be estimated–as the computing time that the shortest Turing machine (i.e. the first in the quasilexicographic order) takes to produce its output s upon halting. CTM thus
produces both an empirical distribution of sequences up to a certain size, and
an LD estimation based on the same computational model.
Because CTM is computationally very expensive (equivalent to the Busy
Beaver problem [40]), only short sequences (currently only up to length k = 12)
have associated estimations of their algorithmic complexity. To approximate
the complexity of genomic DNA sequences up to length k = 12, we calculated
D(5, 4)(s), from which CT M (s) was approximated.
To calculate the Algorithmic Probability of a DNA sequence (e.g. the sliding window of length 147 nt) we produced an empirical Algorithmic Probability
20

Table 1: Spearman correlations between complexity indices with in vivo and
in vitro experimental nucleosome occupancy data from position 187 001 bp to
207 000 bp on the 14th Yeast chromosome

in vitro
in vivo
GC content
LD
Entropy
BDM
Compress

in vitro
1
0.5
0.684
-0.29
0.588
0.483
0.215

in vivo
0.5
1
0.26
-0.23
0.291
0.322
0.178

distribution from (5, 4) to compare with by running a sample of 325 433 427 739
Turing machines with up to 5 states and 4 symbols (the number of nucleotides
in a DNA sequence) with empty input (as required by Algorithmic Probability).
The resulting distribution came from 325 378 582 327 non-unique sequences (after removal of those sequences only produced by 5 or fewer machines/programs).

5.5

Relation of BDM to Shannon Entropy and GC Content

The Block Decomposition Method (BDM) is a divide-and-conquer method that
can be applied to longer sequences on which local approximations of C(s) using
CTM can be averaged, thereby extending the range of application of CTM.
Formally,
X
BDM (s, k) =
log(n) + CTM(r).
(3)
sk

The set of subsequences sk is composed of the pairs (r, n), where r is an element
of the decomposition of sequence s of size k, and n the multiplicity of each
subsequence of length k. BDM (s) is a computable approximation from below
to the algorithmic information complexity of s, C(s). BDM approximations
to K improve with smaller departures (i.e. longer k-mers) from the Coding
Theorem method. When k decreases in size, however, we have shown [28] that
BDM approximates the Shannon entropy of s for the chosen k-mer distribution.
In this sense, BDM is a hybrid complexity measure that in the ‘worst case’
behaves like Shannon entropy and in the best approximates K. We have also
shown that BDM is robust when instead of partitioning a sequence, overlapping
subsequences are used, but this latter method tends to over-fit the value of the
resultant complexity of the original sequence that was broken into k-mers.

21

Table 2: Spearman correlation values of complexity score functions versus the
Wedge dinucleotide model prediction of DNA curvature on 20 synthetically generated DNA sequences

p
rho

GC
content
0.047
-0.45

Entropy
0.051
-0.44

Entropy
rate (4)
0.0094
-0.57

Compress

BZip2

BDM

LD

0.0079
-0.58

0.048
-0.45

0.0083
-0.57

0.0019
0.65

Table 3: Distance in nucleotides to local min/max within a window of 2 tests,
around 40 and 140 nts around the centre on a pseudo-randomly generated DNA
background with the same GC content as the mean of the GC content of the
next contiguous nucleosomic region. Clearly the experiment is designed for GC
content to fail, yet BDM predicts the nucleosome position (by its centre) in a
high number of cases and with great accuracy, with 10 out of the 14 centres
predicted to within a 1 to 3 nt distance, thereby suggesting that there is more
structure than GC content. Contrast this to GC content performing no better
than chance, with an average fractional distance of 0.538 versus 0.105 for BDM
from the predicted centre. Likewise for windows around the centre of 40 nt and
140 nt. All other methods (not included) reported intermediate values between
GC content and BDM
BDM
601
603
605
5Sr DNA
pGub
chicken β−
globulin
-48
-2
-1
-1
19
25
msat CAG TATA
CA
NoSecs
TGGA
TGA BadSecs
2
1
1
1
14
1
1
1

Table 4: The 20 short artificial DNA sequences generated covering a wide range
of patterns and regularities used to find informative measures of DNA curvature.
AAAAAAAAAAAA
AAAAAAAAATAA
ATAGAACGCTCC
TCGTTCGCGAAT
CTCTCAGGTCGT
GGCGGGGGGTGG
GCGCGCGCGCGC

ATATATATATAT
AAAAAAAACAAT
ACCTATGAAAGC
TGCACGTGTGGA
CTCGTGGATATC
GGGGGGGCGGGC
GGGGGGGGGGGG

22

AAAAAATTTTTT
AAGATCTACACT
TAGGCGGCGGGC
CTAAACACAATA
CCACGATCCCGT
GGGGGGCCCCCC

Table 5: 14 Experimental nucleosome sequences [24]. Only the first 6 have
known dyads
name
601

dyad
position
74

sequence
ACAGGATGTATATATCTGACACGTGCCTGGAGACTAGGGAGTA
ATCCCCTTGGCGGTTAAAACGCGGGGGACAGCGCGTACGTGCG
TTTAAGCGGTGCTAGAGCTGTCTACGACCAATTGAGCGGCCTCG
GCACCGGGATTCTCCAG

603

154

CGAGACATACACGAATATGGCGTTTTCCTAGTACAAATCACCCCA
GCGTGACGCGTAAAATAATCGACACTCTCGGGTGCCCAGTTCGC
GCGCCCACCTACCGTGTGAAGTCGTCACTCGGGCTTCTAAGTACG
CTTAGGCCACGGTAGAGGGCAATCCAAGGCTAACCACCGTGCAT
CGATGTTGAAAGAGGCCCTCCGTCCTTATTACTTCAAGTCCCTGG
GGTACCGTTTC

605

132

TACTGGTTGGTGTGACAGATGCTCTAGATGGCGATACTGACAGG
TCAAGGTTCGGACGACGCGGGATATGGGGTGCCTATCGCACATT
GAGTGCGAGACCGGTCTAGATACGCTTAAACGACGTTACAACCC
TAGCCCCGTCGTTTTAGCCGCCCAAGGGTATTCAAGCTCGACGCT
AATCACCTATTGAGCCGGTATCCACCGTCACGACCATATTAATAG
GACACGCCG

5Sr DNA

74, 92

AACGAATAACTTCCAGGGATTTATAAGCCGATGACGTCATAACAT
CCCTGACCCTTTAAATAGCTTAACTTTCATCAAGCAAGAGCCTAC
GACCATACCATGCTGAATATACCGGTTCTCGTCCGATCACCGAAG
TCAAGCAGCATAGGGCTCGGTTAGTACTTGGATGGGAGACCGCC
TGGGAATACCG

pGub

84, 104

GATCCTCTAGACGGAGGACAGTCCTCCGGTTACCTTCGAACCACGT
GGCCGTCTAGATGCTGACTCATTGTCGACACGCGTAGATCTGCTAG
CATCGATCCATGGACTAGTCTCGAGTTTAAAGATATCCAGCTGCCC
GGGAGGCCTTCGCGAAATATTGGTACCCCATGGAATCGAGGGATC

chicken β-globulin

125

CTGGTGTGCTGGGAGGAAGGACCCAACAGACCCAAGCTGTGGTC
TCCTGCCTCACAGCAATGCAGAGTGCTGTGGTTTGGAATGTGTGA
GGGGCACCCAGCCTGGCGCGCGCTGTGCTCACAGCACTGGGGTG
AGCACAGGGTGCCATGCCCACACCGTGCATGGGGATGTATGGCGC
ACTCCGGTATAGAGCTGCAGAGCTGGGAATCGGGGGG

mouse minor
satellite

ATTTGTAGAACAGTGTATATCAATGAGCTACAATGAAAATCATGGA

CAG

AGCAGCAGCAGCAACAGTAGTAGAAGCAGCAGCACTAACGACAG

AAATGATAAAAACCACACTGTAGAACATATTAGATGAGTGAGTTA
CACTGAAAAACACATCCGTTGGAAACCGGCAT

CACAGCAGTAGCAGTAATAGAAGCAGCAGCAGCAGCAGTAGCAG
TAGCAGCAGCAGCAGCAGCAATTTCAACAACAGCAGCAGCAGCT

TATA

AGGTCTATAAGCGTCTATAAGCGTCTATGAACGTCTATAAACGTCT
ATAAACGCCTATAAACGCCTATAAACGCCTATACAAGCCTATAAAC
GCCTATACACGTCTATGCACGACTATACACGTCT

CA

GAGAGTAACACAGGCACAGGTGTGGAGAGTAACACAGGCACAG
GTGTGGGAGAGTGACACACAGGCACAGGTGAGGAGAGTACACA
CAGGCACAGGTGTGGAGAGCACACACAGGTGCGGAGAG

NoSecs

GGGCTGTAGAATCTGATGGAGGTGTAGGATGGATGGACAGTATGA
CAAAAGGGTACTAGCCTGGGACAGCAGGATTGGTGGAAAGGTTA
CAGGCAGGCCCAGCAGGCTCGGACGCTGTATAGAG

TGGA

AGATGGATGGATGATGGATGGATGATGGATAGATGGATGATGGAT
GGATGGATGATGATGGATGAATAGATGGATGGATGGATGATGGAT
GGATGGACGATGGATGGATAGATGGATGGATGG

TGA

ATAGATGGATGAGTGGATGGATGGGTGGATGGATAGATGGGTGG
ATGGGTGGATGGGTGGATGGATGATGGATGGATGAGTGGATGGA
TGGATGGATGGGTGGATGGGTGGACGG

BadSecs

TCTAGAGTGTACAACTATCTACCCTGTAGGCATCAAGTCTATTTCGG

23

TAATCACTGCAGTTGCATCATTTCGATACGTTGCTCTTGCTTCGCTAG
CAACGGACGATCGTACAAGCAC

