BACKGROUND
the history of life is written in genomes.
evolutionary forces and historical artefacts leave discernible footprints on dna sequence, and their identification and subsequent interpretation is an active area of genetic research.
single nucleotide polymorphism microarray  data capture within species variation.
snp data are typically used to investigate the genetic origin of diseases and other phenotypes, identify genetic differences between populations, and to infer the shared evolutionary history of those populations  <cit> .
these inferences are usually derived from analyses of percent heterozygosity , explorations of allele frequency using fixation index  and principal component analysis   <cit> .
while being one of the most recognized and commonly implemented metrics, the use of fst to quantify the genetic distance between populations is not free of challenges.
it has been demonstrated  <cit>  that the choice of estimator, the method of combining estimates across snps, and the scheme of snp ascertainment can impact the fst results.
similarly, according to  <cit>  a weakness of fst is that it implicitly assumes that populations have the same effective size and were independently derived from the same ancestral population.
if this assumption is violated, which is often the case, genome scans can yield false positives.
strengths and weaknesses of applying pca to population genetics are discussed in detail elsewhere  <cit> .
the linear data strings produced by snp-chips possess two very simple numerical properties – the order and proportion of 0’s, 1’s and 2’s .
these compositional numerical properties have not been fully explored but may be amenable to novel pattern recognition analyses thereby yielding unique new biological insights.
it has long been recognized that regularities in data structure enforce statistical redundancies that can be quantified by the related concepts of entropy and compression  <cit> .
this compressibility is a proxy for the minimum amount of information required to reproduce a data set, i.e.
its kolmogorov complexity  <cit> .
the compression output can be queried to identify patterns that may have otherwise remained obscure.
clustering large data sets by compression metrics has been successfully applied to whole mitochondrial genome phylogenetic reconstructions  <cit> , microbiota composition comparison  <cit> , interpretation and segregation of gene expression data  <cit> , virus phylogeny, relatedness of languages, and even clustering of musical genres  <cit> .
here we use dense genome-wide snp-chip data as a proxy for genome composition, which facilitates exploitation of broad patterns of genomic organization relating to the order and proportion of homozygote and heterozygote genotypes.
by expressing the compressed file size to its uncompressed form one gets a measure of compression efficiency .
this output reflects data regularities in a convenient manner.
our approach spans datasets derived from five mammalian species, and includes humans and several domestic animals.
the inclusion of domestic animals allowed us to explore genomic patterns in populations with well-defined phenotypes, varying periods and intensities of artificial selection, and variations in past effective population size  <cit> .
we show that ce analyses can be successfully deployed to discriminate between populations and breeds in a computationally efficient manner that has an appealingly simple methodology.
RESULTS
genome-wide compression efficiency reveals population structure
in this study snp data were used as a proxy for genomic dna sequence composition.
the data regularities exploited by the compression efficiency metric were derived from the patterns of allele order and proportion across both individuals and populations.
our expectation is that snp data are dense enough to provide a reasonable reflection of overall genomic composition.
however, some clear differences between real sequence versus snp data include the absence of dna repeat regions on snp arrays.
furthermore, snp are intended to capture allele variation relative to a reference, and in this sense are abstracted from raw genome sequence.
finally, caution is needed as snp ascertainment bias may complicate interpretation across populations.
the ce output for some exemplar data strings are shown in table  <dig>  they reveal that the two properties driving data regularity  - order and proportion - bear a strong mutual relationship with each other.
high levels of proportional bias will serve to enforce bias in order, and vice versa.
in contrast, shannon’s entropy  <cit> , an information theory statistic for measuring regularities in data streams, exploits proportion.
like shannon’s entropy, ce captures proportion, but it also reflects sequence regularity in scenarios where shannon’s entropy is uninformative , because shannon’s entropy does not exploit patterns relating to order.when genome-wide ce values were obtained for each individual from the  <dig> human populations from hapmap <dig>  it successfully sorted individuals into their population of origin with varying degrees of overlap .
although the spread of the data is narrow, it clearly segregates the populations such that the african show low ce values and high heterozygosity, while the asian populations have high ce values and low heterozygosity.
indeed, all populations within the hgdp and pan asian data were discriminated to some extent by the ce approach, yielding population resolution in all cases .
comparing all human snp data sets, the indigenous brazilian populations  exhibited the highest ce.
compression efficiency for hypothetical sequences based on  <dig> snps for one individual  or five individuals .
in all cases the shannon’s entropy would be identical i.e.
<dig>   log <dig> ) because each snp call is equi-probable.
compression efficiency exploits patterns in order as well as proportion allowing it to discriminate data that cannot be discriminated by shannon’s entropy.
the rationale column is a verbal approximation of the algorithmic complexity.
regular sequences have a small algorithmic complexity and high compression efficiency.
however, complex, irregular sequences embedded in a homogeneous population can still exhibit a relatively high compression efficiency %.
our sliding window heterozygosity corrected compression efficiency approach exploits this combination .
in effect, a population-level assessment is made of a region’s sequence entropy, detecting high co-sharing of even very complex regions.
relationship between ce and fst
the correlation between fst and ce is  <dig>  implying ce reflects to a large extent the population resolution of fst.
the pairwise relationship for all  <dig> population pairs can be found in figure  <dig>
given that only a fraction of the human genome is protein-coding, and that canonical genes are on average more highly conserved and have a substantially lower mutation rate  <cit> , we explored the possibility in the human hapmap data that human protein-coding and non-protein-coding regions would segregate by ce.
we would normally expect an increase in ce to correspond with a decrease in heterozygosity.
for all populations, coding regions have lower het than non coding regions .
however, when examining ce of the low het coding regions in isolation the expected increase in ce was only observed in the african populations .
for the remainder, i.e.
all the non-african populations, there was no increase in ce when examining coding regions in isolation.
we find that in all human populations there is a relationship between high heterozygosity and low ce.
this is because a more even proportion of 0’s, 1’s and 2’s  naturally increases the entropy of the data stream, for the same reason the outcome of a 3-sided dice roll is less certain than that of a 2-sided dice roll.
however, heterozygosity does not fully account for the ce output because 1) much genomic regularity is a product of order in combination with proportion and 2) the percentage of 1’s does not exclusively govern either the order or proportion of 0’s and 2’s that comprise the remainder.
we also note that in addition to being easier to implement than fst the ce approach was computationally more efficient, taking 16 seconds compared to 94 seconds.
analysis of non-human populations demonstrated that ce was able to successfully reveal known aspects of population history .
large snp datasets were available from cattle and sheep populations, where multiple animals per breed were drawn from a diversity of breeds and geographic regions.
clear evidence for population substructure was evident in cattle, which is composed of two sub-species  .
ce distinguished brahman cattle  from all other populations.
the combination of ce and heterozygosity separated populations on the basis of their ancestral genomic composition.
for example, breeds with a high proportion of bos indicus ancestry  had high heterozygosity and low ce, while purebred taurine breeds  showed generally higher ce and reduced heterozygosity.
domestic sheep are not composed of separate sub-species and have a population history characterized by frequent gene flow between breeds  <cit> .
this generally weak population substructure  was reflected in the data as domestic breeds from six major geographic regions were positioned in a single large undifferentiated cluster .
feral sheep, however, clustered separately from modern domestic breeds, due to their low heterozygosity and high ce.
the mouse population data shows variation in the ce and heterozygosity relationship .
the german mouse population is arranged in a linear fashion whereas other populations are arranged more diffusely.
this implies that at a whole genome level the german mice possess a particularly tight relationship between ce and heterozygosity, although the heterozygosity itself is variable.
like the mice data, the dog data is based on a single representative individual for each breed .
the extreme position of the village dog , considered to be neither wild nor feral, is noteworthy.
taken together, ce and heterozygosity recapitulated known aspects of population history for each animal species tested.
high resolution sliding window ce reveals regions that discriminate populations including signatures of selection
given the ability of genome-wide ce to recreate phylogeographic relationships, we investigated if ce could be employed to identify individual genomic loci that showed significant deviations in allele order and composition.
we speculated that since positive selection is known to leave detectable signatures in genomic patterns of variability  <cit> , ce may be able to not only identify regions under common constraint across human populations, but also loci that differed systematically between populations.
in this analysis a heterozygosity corrected ce  score, which was subsequently normalized  by its z-score , was computed for sliding windows of  <dig> snps across all  <dig> human hapmap populations.
regions of interest were identified by taking snps with cehz scores 3-fold higher than the mean, and clustering snp within  <dig> kb of one another.
we identified ~ <dig> regions per population with statistically significant cehz scores, with an average size ~97 kb .
analysis of cehz loci revealed that their distribution varies between populations  and that most of them have substantial heterozygosity and so do not correspond to simple runs of homozygosity .
rather, the cehz loci include complex mixes of homozygotes and heterozygotes that are co-shared by many members of a population.
intriguingly, only nine cehz loci were common across all  <dig> human hapmap populations.
these contained retinoblastoma  <dig> , dihydropyrimidine dehydrogenase , histone deacetyase  <dig>  citrate synthase , peroxisome proliferator-activated receptor delta , and neutral alpha-glucosidase c  among others  – all genes involved in fundamental cellular, developmental and metabolic processes.
since the cehz metric is detecting population-level regions of homogeneity, it is tempting to speculate that cehz loci common to all human populations are coincident with regions of fundamental importance to the human lineage.
to investigate if high cehz scores may be indicative of evolutionary pressure, cehz loci were intersected with regions recently identified as harbouring signals of natural selection in central europeans , chinese  or yoruba africans  using the composite of multiple signals  test  <cit> .
this revealed that 20% of the ceu, 13% of the yri, and 10% of the chb regions identified by cehz and cms overlapped .
importantly, this set contains loci that are exemplars of natural selection in modern humans.
for example slc24a <dig> which is associated with skin lightening in cold climate europeans  <cit>  tuscans and gujarati indians  <cit>  is specifically detected by cehz in the ceu, tsi and gih populations ; herc <dig> is associated with variation in eye colour in europeans  <cit>  and is similarly detected by cehz specifically in ceu and mex ; and edar has recently been associated with variation in hair texture in asians  <cit> , and is detected in both chinese populations but not japanese .
a detailed example of the sort of population-level shared patterns identified by cehz is illustrated for the skin lightening slc24a <dig> region in light skinned ceu compared to darker skinned asw .
we created three heatmap matrices, clustered on rows.
patterns of population sub-structure based on haplotypes are clearly evident within the ceu and jpt, as are systematic differences between the three populations.
the darker skinned asw are much more heterogeneous  in this region at the population-level than the other two populations.
a substantial reduction in het is apparent in the jpt but not the ceu.
it is noteworthy that the ceu show a compression peak as strong as the jpt, but without the reduction in het.
intriguingly, cehz analysis reveals peaks for both the ceu and the maasai overlapping lct, or lactase .
we note that the cehz data show a more pronounced peak in the maasai compared to ceu.
to identify high-confidence cehz loci that may warrant further investigation, regions specific to population clusters were collated.
this revealed  <dig> african ,  <dig> european , and  <dig> asian  cehz loci.
these sites include a european cehz peak that corresponds to an apparent “gene desert” containing a long non-coding rna of unknown annotated function  preferentially expressed in placenta , an african peak  over a chromatin remodeller and polycomb group protein that has been previously associated with genetic determinants of height   <cit> , and an asian peak  over the x chromosome gene, eda2r, which encodes the ectodysplasin a <dig> receptor and neighbours the androgen receptor.
these regions have been uniquely identified by the cehz approach.
we hypothesize that further investigation of these loci will reveal a possible role in population-specific biological processes.
extending the cehz approach to two cattle species, angus and brahman, comparing to the literature revealed that  <dig> of  <dig> the most extreme cehz loci overlap with genomic regions previously described as being under selection.
similarly, in an analysis equivalent to the human sliding window approach we found  <dig> of the top  <dig> regions also have been previously documented as harbouring signatures of selection   <cit> .
furthermore, we also identified cehz loci overlapping with known qtl for production traits, including bta14:~25 mb which contains the plag <dig> gene  <cit>   previously associated with cattle growth and fertility  <cit> .
we have highlighted  <dig> other regions that also discriminate the breeds, in each case coincident with genes encoding proteins of fundamental developmental importance: en <dig>  plays a role in central nervous system pattern formation  <cit> , eya <dig>  plays a role in muscle fibre composition  <cit>  and arid4a  plays a role in male fertility  <cit> .
1heterozygosis, compression efficiency and z-scores values are averages of a window  from the reference position.
*the snps giving the signal in these regions were unassigned on the bovine assembly btau <dig> .
enomic regions with noteworthy  z-score normalized heterozygosity corrected compression efficiency across bovine brahman and angus populations.
unlike fst cehz is computed on a within genome basis.
no contrasting population is required , which means the analysis can be run on newly genotyped populations in isolation, identifying regions of interest even in species whose genome has poor functional annotation.
furthermore, cehz can also be computed on the mammalian x chromosome whose hemizygosity in males normally precludes population-level analyses by conventional methods.
the cehz human and bovine data  are available as a hub that can be visualized using the ucsc genome browser: https://surf.genome.at.uq.edu.au/~uqrtaft/cehz/hub.txt).
defining the compression efficiency parameter space
in the discipline of complex systems science there exists the concept of ‘the edge of chaos’ capturing the properties of the phase transition that exists between order and chaos.
this transition zone is important because it has been found to possess desirable evolutionary and computational properties.
it did not escape our notice that the ce approach allows one to formalise and test this concept in the context of genomics.
one can scramble the data, measure the ce consequences, and compare it to the informational properties of the real genomes.
we scrambled the order of snps using both the proportions from that particular individual  but also a deeper randomization based on proportions derived from the population at large .
rand <dig> is valuable in defining the parameter space we are interested in, as it can be explored for the entire range of conceivable heterozygosity i.e.
from  <dig> to  <dig>  here, 100% produces a highly compressible string of 1’s while 0% is composed of a random string of 0’s and 2’s only.
because this rand <dig> sequence is maximally chaotic the resultant curve defines the signal to noise threshold for every level of heterozygosity.
intriguingly, it can be observed that the real mammalian dna sequences align to, or emanate from, the point of minimum ce coincident with ~33% heterozygosity .
the outcome is similar across species.
that is, the ce of genomes always aligns with the point of minimum ce.
superimposed in figure  <dig> are lines intended to elucidate possible mechanisms for driving genomic movement through information space.
overall, this creates an impression that genomes evolve from  the point of minimum ce, reflecting the combined impacts of inbreeding, ld  and other unidentified factors.
there is a strong negative relationship between ce and het.
however, through outbreeding, het values beyond 33% can be achieved and, in this region increases in het can be associated with increases in ce.
from a numerical perspective, proportion-based regularity  increases as one moves farther away from the ~33% het  on both sides of the x axis, while order-based regularity  increases as you increase ce moving upwards on the y axis.
discussion
given that the purpose of genomes is to encode and transact information, it is not surprising that principles from information theory have been previously used to quantify their informational properties  <cit> .
however, the historical use of compression per se in genomics has been more from a practical and technical perspective  <cit> , such as how to store large datasets in an efficient manner, rather than that of pattern recognition and biological interpretation.
the only previous example of clustering by compression in the genomic area that we are aware of is the mitochondrial work of  <cit>  which reconstructed eutherian and mammalian phylogenies.
here, we have illustrated that ce analysis of snp data allows one to 1) discriminate populations reconstituting known aspects of their diversity, 2) identify at very high resolution genomic regions of evolutionary interest including validated signatures of selection 3) visualise evolution through informational space and 4) achieve these goals using a method that has an appealing logical simplicity.
the hypothesis-free pattern recognition qualities of ce allow exploitation of order as well as proportion, the two sources of regularity in any data stream.
this is important because the detection of patterns can be used to cluster data based on guilt-by-association and drive the inference of biological meaning.
one conceptual advantage of using a proxy for direct genetic evidence  rather than the direct evidence itself  is that previously unrecognized informational footprints may be present in the data which we may wish to exploit but whose expected properties we do not need to identify, nor fully understand, a priori.
overall, we document a promising new perspective on analysing genomic data which is intended to be complementary to existing mathematical approaches, not to supplant them.
given this is the first publication of a wholly new approach, we are not yet in a position to formally connect our ideas to existing population genetics theory in a rigorous mathematical sense.
nevertheless, given its particular biological interest to human genetics, we do explore the population-level allele pattern content of the ceu and asw slc24a <dig> skin pigmentation region in some more detail.
from the broader genome-wide perspective we have to rely on less quantitative verbally expressed arguments.
these draw intuitive connections between ce and various aspect of population genetic theory.
population discrimination
in order to infer population history, molecular geneticists conventionally look for specific genomic sites across individuals and search for changes in abundance or even fixation of an ancestral or derived allele  <cit> .
here we have taken a complementary strategy, exploiting various longitudinal patterns along an individual’s genome .
the assumption we make is that closely related individuals will be more likely to share these longitudinal patterns of genome composition , however complex they may be.
one appeal of this approach is we do not lose the informational context provided by physically proximate snps.
in terms of the whole genome, we find ce allows all human populations to be discriminated, sometimes with little or no overlap.
using the human hapmap <dig> dataset, the lowest ce is exhibited by the african american and other african populations and the highest ce by the asian populations .
the groupings resonate with published phylogeographic reconstructions based on fst and pca analyses  <cit>  but are computationally much quicker and cheaper, consuming only a fraction of cpu time.
in broad terms, at heterozygosity levels less than a third, there is clearly a strong negative relationship between ce and heterozygosity.
however, this observation does not explain the ce output, with populations of similar heterozygosity discriminated by differential ce.
the population discrimination is robust across mammalian species .
runs of homozygosity are clearly an obvious compositional feature that will be exploited by gzip to compress the snp data string in the whole genome version of the ce analysis, but there are many others sources of regularity.
one appealing analytical implication of the genome-wide ce approach is that the different scales of the various informational regularities can be assessed simultaneously by a single metric, irrespective of their size, direction or crypticity.
the genomes of domesticated species offer a useful model in which to explore the genomic consequences imparted by population histories characterized by bottlenecks and artificial selection, as the genetic similarity of the various breeds provides a relatively stable background against which various evolutionary forces can be inferred  <cit> .
in each domestic species broadly similar patterns were observed.
genome-wide ce increased for populations likely to have been founded from a small number of founders, and it decreased for outbred populations expected to be highly heterogeneous.
ce was plotted against heterozygosity showing that signals of population substructure were evident in non-human species .
genomic regions harbouring signatures of selection
given the ability of whole genome ce to discriminate populations, we next explored within-genome structure to prioritise regions of particular biological interest.
we used a high resolution sliding window expressed relative to heterozygosity and normalized by z-score .
the correction for heterozygosity means the ce differences are more likely to be attributable to the pattern in order of heterozygotes and homozygotes and less to changes in proportion.
the approach integrates a combination of individual genome regularity in the context of population homogeneity in that region .
regions of even quite complex composition will yield a compression peak by cehz if they are shared by many members of a given population.
this feature discriminates the window-based cehz analysis  from the whole genome ce .
that is, for cehz not only would we expect to find peaks over regions characterized by shared runs of homozygosity , but other compositionally more complex regions as well.
the application of a matrix structure that permits comparisons of the same genomic regions across individuals clearly connects the output to existing population-level metrics such as ld.
however, cehz finds loci over many different kinds of compositional regularities in a manner that defies a simple summary.
a more detailed examination of allele composition in the slc24a <dig> region in asw, ceu and jpt reinforces the challenge of describing the mathematical nature of the compressible patterns exploited by gzip .
irrespective of this, the data can be exploited to find commonalities and differences across any set of population groupings, in this particular case highlighting population substructure and showing the ceu and jpt are awarded similarly high cehz peaks for different reasons, and with different background het.
in attempting to interpret the biological relevance of the compression peaks we examined the extent to which our new regions overlap with known signatures of selection.
we find cehz successfully detects many of the known major signatures of selection in the various species.
with regard to the human output we used  <cit>  and found substantial overlap .
the ce approach has the appeal of pinpointing particular genomic regions, such as coding sequence or parts of coding sequences, at very high resolution.
in human populations the highlighted regions capture genes encoding proteins involved in skin pigmentation , blue eye colour , lactase persistence  and hair texture .
a recent paper  <cit>  detected a signature of positive selection in slc24a <dig> in ceu, gih and tsi exactly concordant with our observations based on cehz.
they used a new method  which leverages  <dig> sources of information relating to haplotype length and structure.
haplops is similar to ehh and xp-ehh except that it estimates the population frequency of the allele under question and identifies the haplotype sequence on which the selected allele sits.
furthermore, the lct gene encodes the lactase protein that allows milk digestion into adulthood.
it is known to be under selection only in those european  and african  populations with an extensive pastoral history characterised by livestock domestication and an adaptation favouring regular milk and dairy consumption .
the lactase signature recently detected in mkk was notable in that a combination of  <dig> computationally intensive measures had to be leveraged   <cit> .
moreover, in contrast to cehz which provides strong evidence for the exact gene, the alternative methods could resolve the region only to a relatively broad  <dig>  mb  <cit> .
in our data the nature of the lct-specific peak in ceu and mkk is visibly different, consistent with the purported evolutionary independence of the selection event  <cit> .
new human population predictions unique to cehz imply hitherto unrecognised roles for a long non-coding rna in european populations, a chromatin remodeller  in african populations and the eda2r gene in asian populations .
the eda2r is noteworthy in that it is present on the x chromosome which is not amenable to conventional analyses because it is hemizygous in males.
a number of cehz peaks are shared by all the human populations.
we might speculate these represent genomic constraint at a much deeper taxonomic level, perhaps the branch point of modern humans from other primates.
it is interesting to note that the more homogeneous asian populations exhibit a frequency distribution of ceh z-scores characterised by a low mean value, but a number of very extreme outliers compared to the more heterogeneous african populations .
in the cattle divergent regions contrasting angus  and brahman  breeds aligned to previously described signatures of selection.
the recently documented plag <dig> is considered fundamental to tropical adaptation in brahman cattle .
new predictions for the cattle breed comparison include en <dig>  eya <dig> and arid4a .
overall, it appears cehz is a useful metric for exploiting intra-chromosomal heterogeneity in a rapid, straightforward fashion.
evolution and information compression
what are the biological implications of the ce values we have computed?
as a first step, we defined the total parameter space .
this allows us to encapsulate the boundaries of the dna informational universe.
in turn, this universe enables us to envisage how real dna sequence evolves at a whole genome level.
we modelled ‘totally regular’  by first sorting each individual snp genotype prior to compression, and ‘totally irregular’  through several different randomisation procedures set at both the individual and population levels that account for proportion and order.
the initial randomisation provided by rand <dig> breaks ld by scrambling the identical “ <dig>   <dig>  2” proportions into chaotic order .
this result shows that in practice ld serves to enforce data regularities  on real-world dna sequences.
the deeper randomisation provided by rand <dig>  is perhaps surprising.
it suggests each individual genome possesses highly cryptic proportional regularities not present in the population at large .
we found that all populations in all species occupy a very specific zone, clearly converging at – or emerging from – a very well defined point in ce genomic space.
they intersect at the point at which highly complex sequence most deeply explores the disordered space, without actually becoming chaotic.
the overall uniformity of the shape of the output across all the populations/breeds of all the species, despite considerable compositional differences in both the density and functional bias of the snp chip technologies, points to the very high robustness of the result.
nevertheless, snp chips characterise highly variable  regions, so the translation of this output to full genome sequence remains uncertain and should be a focus of future work.
we were next interested in direction of travel through this space.
are we observing an emergence or a convergence from the point of minimum ce and maximum noise?
our first attempt to answer this question was to examine the domestic species data.
these species have a clearly identified progenitor which provides an unambiguous evolutionary sequence.
however, snp ascertainment bias confounds interpretation here.
what we can say though, is that life - characterised by negative entropy  <cit>  evolved from non-life which is usually characterised by high entropy.
it is therefore tempting to assume that the more ancestral compositional states would have been more entropic.
further, another source of sequence data in a range of species supports this idea.
in the context of particular protein coding sequences, we have previously noted that when genome-wide codon bias is quantified informationally, it is those proteins apparently most relevant to  the lineage under scrutiny that exhibit the lowest entropy.
examples of these low-entropy ‘derived’ molecules include proteins influencing chloroplast physiology in plants, mitochondrial function in birds and hair formation in mammals  <cit> .
generalizing this broad line of reasoning  is appealing as it places representatives of the modern african populations as relatively basal , which seems to be consistent with the consensus “out of africa” hypothesis of modern human evolution  <cit> .
in the future the hypothesis that derived genome sequences possess relatively low entropy could be validated using domestic species as a resource.
one could compare the whole genome ce of the extant representative of the wild ancestor to various domestic populations.
for example, we would predict the ce of the red jungle fowl genome, at an individual level, to be lower  than individual genomes representing meat and egg producing domestic chickens.
we would also predict population-level cehz sliding window scores to possess a more extreme distribution in the domestic breeds.
some of these cehz peaks would characterise signatures of selection for egg and meat production.
what else does this mean for our understanding of biological encoding systems?
the phase transition between regularity and irregularity is theorised to be a high-impact zone of enormous computational power and evolutionary potential  <cit> .
this interests us given a genome is a computing device made of nucleic acid that is the product of evolution.
the overall position of all the human populations supports a controversial concept from complex systems science  <cit>  that genomes are poised at or close to ‘the edge of chaos.’ this conclusion resonates closely with that of kong et al.,  <cit>  who analysed  <dig> prokaryotic and  <dig> eukaryotic genomes using an novel regularity/order index called ø and based on averages of nucleotide distributions in a given sequence of pre-defined length.figure  <dig> also summarise the possible mechanistic explanations for the various trajectories taken by the populations and individuals through information space, based on considerations of both the implications of our data modelling coupled with the real world mammalian genomes.
we see different spatial impacts of ld and extent of outbreeding depending on the particular population under consideration.
the meaning of ce in the context of population genetics theory
to finish, it is appropriate to more directly connect our ce work to existing population genetics theory, whose goal is to study the frequency and interaction of alleles and genes in populations.
in population genetics theory, various evolutionary processes, particularly natural selection , drift, mutation and gene flow are explored to make inference about population history.
the hardy-weinberg principle says that the frequency of alleles will remain constant in the idealised absence of selection, mutation, migration and drift  <cit>  and this provides a theoretical expectation  against which population level deviations from equilibrium  can be quantified and subsequently interpreted.
in information theory terms, the point of equilibrium corresponds to maximum entropy, and extent of dis-equilibrium reflects differing amounts of negentropy.
at a population level, nearby pairs of alleles have a high tendency to be correlated with each other .
in genetic ‘hitchhiking’ an allele at one locus rises to high frequency in a population because it is linked to an allele under selection at a nearby locus, not because it has been selected itself.
the same phenomenon applies to genes under runaway sexual selection  <cit> .
clearly, this phenomenon culminates in population-level homogeneity  in allele combinations because of genomic similarity between individuals.
adding further dynamism, these population-level patterns are gradually broken by the individual cellular/molecular process of genetic recombination, but at a slow rate.
this ebb and flow of allele pattern formation and destruction among individuals can be exploited to detect the action of natural selection via selective sweeps, and to view the impact of migrations and founder effects.
for example, it is well known that there is higher ld in asian populations, presumably due to the founder effects that occur during migrations limiting the number of haplotypes.
ld is often viewed by a decay plot e.g.
<cit> , where it can be shown that deviation from equilibrium is considerably stronger for nearby loci.
these decay plots are relatively extreme for africans due to faster ld decay and correspondingly smaller haplotype blocks than in the comparison asian and european populations.
a number of existing metrics for selection  are based on considerations of local decay of haplotypes.
what does this mean for the various ce metrics and what are the phenomena that serve to underpin the patterns quantified by ce?
whole genome ce is computed on an isolated individual basis.
the coordinates  of the population cluster describes the data at the population level.
however, given this is fundamentally an individual-level metric, its relationship to ld might not be straightforward.
for example, other sources of  compositional regularity may apply including segmental duplications  <cit>  and g <dig> motifs and structures  <cit> .
it is also true in theory, that one can achieve the same compression efficiency for different reasons, but in practice we find that the accurate phylogeographic population-level clustering implies it is only similar related genome compositions that are awarded similar ce scores.
also, we know that the rand <dig> modelling procedure serves to break ld and reduces ce .
based on this reasoning, it is tempting to speculate that individuals with high ce presumably belong to populations that have even higher ld.
this conclusion is clearly consistent with the population-level ce ranking we observe in figures  <dig> , <dig>   <dig> that mirrors known differences in ld between human populations, that is the africans showing the least ld and the asians the most ld, with the europeans intermediate.
next we will consider the relationship of this thinking to the particular genomic regions identified by the sliding window cehz.
from our informational perspective, remnant population-level patterns can clearly be quantified by cehz, and contrasted across populations, no matter how cryptic or complex the genomic composition may be at an individual level.
a detailed specific example is given by the ceu and gih skin lightening signature of selection that resides over slc24a <dig> .
at this stage, a confident determination of cehz’s exact biological origin – i.e.
is there a particular compressible pattern diagnostic of natural selection versus genetic drift versus a founder effect?
– is not possible.
that being said, there are clearly numerous reliable patterns present at very specific genomic regions in one population, but not another.
many of these have not been described before including those specifically overlying known functionally important parts of the genome, such as protein-coding genes, non-coding rna and so on.
these new discoveries may reflect the fact that the mathematical nature of the population-level patterns we have highlighted did not have to be specified a priori, unlike fst which is more tightly expressed.
the guilt-by-association heuristic tells us there is some bona fide population-level meaning in those regions.
it is our contention that a post-publication community effort and a range of techniques will be required to ascribe functional significance or not on a case-by-case basis.
to expedite this process, we have uploaded the cehz tracks onto the ucsc genome web browser.
slower ld decay in asian populations seems consistent with our finding that the asians possess extreme outlier peaks in cehz reflecting high homogeneity in certain regions not observed in the other populations .
it is worth pointing out that direct comparisons of two specified loci between populations are not apparent in decay plots, as all conceivable pairs are simultaneously plotted.
by contrast, one strength of the cehz sliding window approach is we maintain the identity of the genomic region such that the population contrasts are directly comparable, and therefore biological interpretation can conveniently be made on a fine-grained regional basis.
an example would be the european and gujarati indian selection events around the slc24a <dig> gene .
finally, population genetic diversity has been quantified by allelic diversity – namely, the proportion of all copies of a gene made up of a particular variant  <cit> .
the  <dig> genomes consortium  <cit>  showed that ceu, jpt and yri possess many snps displaying substantial absolute differences in allele frequency, and that this ability to differentiate populations decays rapidly as one increases physical distance from genic snps.
our observations are consistent with some of these findings, namely the whole genome discrimination determined by ce, the concordance of some ceh peaks over genic regions in particular, and the elevation of african ce when examining coding snps only.
caveats
ce operates by exploiting regularities within a sequence regardless of the origin of the sequence.
ce is not based on any theory of segregation inheritance, nor does it require knowledge of ancestry to phase the genotypes.
in light of the strong correlation between fst and ce  we conclude that ce accurately estimates genetic relatedness among populations without recourse to additional sources of information.
the same conclusion is reached when ce is used a sliding window approach to capture genes under selection.
because ce is a hypothesis-free pattern recognition method that detects regularities in segments of the genome, it is more in the spirit of the various haplotype-based methods, rather than single marker methods of population differentiation.
the main weakness we have identified is - like ehh and fst - it does not allow for population stratification.
further work is required to formalise other strengths and weaknesses relative to existing methods.
our implementation of ce requires the use of the gzip tool which incorporates the deflate algorithm.
this is included in all unix environments.
however, other compression tools exist and could be used.
also, from the computational perspective, the sequential use of gzip  requires a great deal of parsing arguments and i/o operations.
this is not an issue when compressing a whole matrix comprising genotype sequences from individuals within a population.
nevertheless, if we were to program the deflate algorithm and perform ce analyses entirely in memory then the computation efficiency of ce analyses would be greatly improved.
CONCLUSIONS
we have exploited the pattern recognition qualities of information compression efficiency to assess genome patterns within and between genomes.
this approach recreates established phylogeography and highlights known signatures of selection.
some new regions with high population level scores overlying functional apparatus such as non-coding rna have also been identified.
these regions are not simple runs of homozygosity so direct assessments of this nature cannot identify them.
rather they are compositionally complex regions shared by individuals of a given population.
we hypothesise some of these regions to be previously unidentified signatures of selection.

 the history of life is written in genomes. evolutionary forces and historical artefacts leave discernible footprints on dna sequence, and their identification and subsequent interpretation is an active area of genetic research. single nucleotide polymorphism microarray data capture within species variation. snp data are typically used to investigate the genetic origin of diseases and other phenotypes, identify genetic differences between populations, and to infer the shared evolutionary history of those populations. these inferences are usually derived from analyses of percent heterozygosity, explorations of allele frequency using fixation index and principal component analysis. while being one of the most recognized and commonly implemented metrics, the use of fst to quantify the genetic distance between populations is not free of challenges. it has been demonstrated that the choice of estimator, the method of combining estimates across snps, and the scheme of snp ascertainment can impact the fst results. similarly, according to a weakness of fst is that it implicitly assumes that populations have the same effective size and were independently derived from the same ancestral population. if this assumption is violated, which is often the case, genome scans can yield false positives. strengths and weaknesses of applying pca to population genetics are discussed in detail elsewhere. the linear data strings produced by snp-chips possess two very simple numerical properties – the order and proportion of 0’s, 1’s and 2’s. these compositional numerical properties have not been fully explored but may be amenable to novel pattern recognition analyses thereby yielding unique new biological insights. it has long been recognized that regularities in data structure enforce statistical redundancies that can be quantified by the related concepts of entropy and compression. this compressibility is a proxy for the minimum amount of information required to reproduce a data set, i.e. its kolmogorov complexity. the compression output can be queried to identify patterns that may have otherwise remained obscure. clustering large data sets by compression metrics has been successfully applied to whole mitochondrial genome phylogenetic reconstructions, microbiota composition comparison, interpretation and segregation of gene expression data, virus phylogeny, relatedness of languages, and even clustering of musical genres. here we use dense genome-wide snp-chip data as a proxy for genome composition, which facilitates exploitation of broad patterns of genomic organization relating to the order and proportion of homozygote and heterozygote genotypes. by expressing the compressed file size to its uncompressed form one gets a measure of compression efficiency. this output reflects data regularities in a convenient manner. our approach spans datasets derived from five mammalian species, and includes humans and several domestic animals. the inclusion of domestic animals allowed us to explore genomic patterns in populations with well-defined phenotypes, varying periods and intensities of artificial selection, and variations in past effective population size. we show that ce analyses can be successfully deployed to discriminate between populations and breeds in a computationally efficient manner that has an appealingly simple methodology.  genome-wide compression efficiency reveals population structure in this study snp data were used as a proxy for genomic dna sequence composition. the data regularities exploited by the compression efficiency metric were derived from the patterns of allele order and proportion across both individuals and populations. our expectation is that snp data are dense enough to provide a reasonable reflection of overall genomic composition. however, some clear differences between real sequence versus snp data include the absence of dna repeat regions on snp arrays. furthermore, snp are intended to capture allele variation relative to a reference, and in this sense are abstracted from raw genome sequence. finally, caution is needed as snp ascertainment bias may complicate interpretation across populations. the ce output for some exemplar data strings are shown in table  they reveal that the two properties driving data regularity - order and proportion - bear a strong mutual relationship with each other. high levels of proportional bias will serve to enforce bias in order, and vice versa. in contrast, shannon’s entropy, an information theory statistic for measuring regularities in data streams, exploits proportion. like shannon’s entropy, ce captures proportion, but it also reflects sequence regularity in scenarios where shannon’s entropy is uninformative, because shannon’s entropy does not exploit patterns relating to order.when genome-wide ce values were obtained for each individual from the human populations from hapmap it successfully sorted individuals into their population of origin with varying degrees of overlap. although the spread of the data is narrow, it clearly segregates the populations such that the african show low ce values and high heterozygosity, while the asian populations have high ce values and low heterozygosity. indeed, all populations within the hgdp and pan asian data were discriminated to some extent by the ce approach, yielding population resolution in all cases. comparing all human snp data sets, the indigenous brazilian populations exhibited the highest ce. compression efficiency for hypothetical sequences based on snps for one individual or five individuals. in all cases the shannon’s entropy would be identical i.e. log ) because each snp call is equi-probable. compression efficiency exploits patterns in order as well as proportion allowing it to discriminate data that cannot be discriminated by shannon’s entropy. the rationale column is a verbal approximation of the algorithmic complexity. regular sequences have a small algorithmic complexity and high compression efficiency. however, complex, irregular sequences embedded in a homogeneous population can still exhibit a relatively high compression efficiency %. our sliding window heterozygosity corrected compression efficiency approach exploits this combination. in effect, a population-level assessment is made of a region’s sequence entropy, detecting high co-sharing of even very complex regions. relationship between ce and fst the correlation between fst and ce is implying ce reflects to a large extent the population resolution of fst. the pairwise relationship for all population pairs can be found in figure  given that only a fraction of the human genome is protein-coding, and that canonical genes are on average more highly conserved and have a substantially lower mutation rate, we explored the possibility in the human hapmap data that human protein-coding and non-protein-coding regions would segregate by ce. we would normally expect an increase in ce to correspond with a decrease in heterozygosity. for all populations, coding regions have lower het than non coding regions. however, when examining ce of the low het coding regions in isolation the expected increase in ce was only observed in the african populations. for the remainder, i.e. all the non-african populations, there was no increase in ce when examining coding regions in isolation. we find that in all human populations there is a relationship between high heterozygosity and low ce. this is because a more even proportion of 0’s, 1’s and 2’s naturally increases the entropy of the data stream, for the same reason the outcome of a 3-sided dice roll is less certain than that of a 2-sided dice roll. however, heterozygosity does not fully account for the ce output because 1) much genomic regularity is a product of order in combination with proportion and 2) the percentage of 1’s does not exclusively govern either the order or proportion of 0’s and 2’s that comprise the remainder. we also note that in addition to being easier to implement than fst the ce approach was computationally more efficient, taking 16 seconds compared to 94 seconds. analysis of non-human populations demonstrated that ce was able to successfully reveal known aspects of population history. large snp datasets were available from cattle and sheep populations, where multiple animals per breed were drawn from a diversity of breeds and geographic regions. clear evidence for population substructure was evident in cattle, which is composed of two sub-species. ce distinguished brahman cattle from all other populations. the combination of ce and heterozygosity separated populations on the basis of their ancestral genomic composition. for example, breeds with a high proportion of bos indicus ancestry had high heterozygosity and low ce, while purebred taurine breeds showed generally higher ce and reduced heterozygosity. domestic sheep are not composed of separate sub-species and have a population history characterized by frequent gene flow between breeds. this generally weak population substructure was reflected in the data as domestic breeds from six major geographic regions were positioned in a single large undifferentiated cluster. feral sheep, however, clustered separately from modern domestic breeds, due to their low heterozygosity and high ce. the mouse population data shows variation in the ce and heterozygosity relationship. the german mouse population is arranged in a linear fashion whereas other populations are arranged more diffusely. this implies that at a whole genome level the german mice possess a particularly tight relationship between ce and heterozygosity, although the heterozygosity itself is variable. like the mice data, the dog data is based on a single representative individual for each breed. the extreme position of the village dog, considered to be neither wild nor feral, is noteworthy. taken together, ce and heterozygosity recapitulated known aspects of population history for each animal species tested. high resolution sliding window ce reveals regions that discriminate populations including signatures of selection given the ability of genome-wide ce to recreate phylogeographic relationships, we investigated if ce could be employed to identify individual genomic loci that showed significant deviations in allele order and composition. we speculated that since positive selection is known to leave detectable signatures in genomic patterns of variability, ce may be able to not only identify regions under common constraint across human populations, but also loci that differed systematically between populations. in this analysis a heterozygosity corrected ce score, which was subsequently normalized by its z-score, was computed for sliding windows of snps across all human hapmap populations. regions of interest were identified by taking snps with cehz scores 3-fold higher than the mean, and clustering snp within kb of one another. we identified ~ regions per population with statistically significant cehz scores, with an average size ~97 kb. analysis of cehz loci revealed that their distribution varies between populations and that most of them have substantial heterozygosity and so do not correspond to simple runs of homozygosity. rather, the cehz loci include complex mixes of homozygotes and heterozygotes that are co-shared by many members of a population. intriguingly, only nine cehz loci were common across all human hapmap populations. these contained retinoblastoma, dihydropyrimidine dehydrogenase, histone deacetyase citrate synthase, peroxisome proliferator-activated receptor delta, and neutral alpha-glucosidase c among others – all genes involved in fundamental cellular, developmental and metabolic processes. since the cehz metric is detecting population-level regions of homogeneity, it is tempting to speculate that cehz loci common to all human populations are coincident with regions of fundamental importance to the human lineage. to investigate if high cehz scores may be indicative of evolutionary pressure, cehz loci were intersected with regions recently identified as harbouring signals of natural selection in central europeans, chinese or yoruba africans using the composite of multiple signals test. this revealed that 20% of the ceu, 13% of the yri, and 10% of the chb regions identified by cehz and cms overlapped. importantly, this set contains loci that are exemplars of natural selection in modern humans. for example slc24a which is associated with skin lightening in cold climate europeans tuscans and gujarati indians is specifically detected by cehz in the ceu, tsi and gih populations; herc is associated with variation in eye colour in europeans and is similarly detected by cehz specifically in ceu and mex; and edar has recently been associated with variation in hair texture in asians, and is detected in both chinese populations but not japanese. a detailed example of the sort of population-level shared patterns identified by cehz is illustrated for the skin lightening slc24a region in light skinned ceu compared to darker skinned asw. we created three heatmap matrices, clustered on rows. patterns of population sub-structure based on haplotypes are clearly evident within the ceu and jpt, as are systematic differences between the three populations. the darker skinned asw are much more heterogeneous in this region at the population-level than the other two populations. a substantial reduction in het is apparent in the jpt but not the ceu. it is noteworthy that the ceu show a compression peak as strong as the jpt, but without the reduction in het. intriguingly, cehz analysis reveals peaks for both the ceu and the maasai overlapping lct, or lactase. we note that the cehz data show a more pronounced peak in the maasai compared to ceu. to identify high-confidence cehz loci that may warrant further investigation, regions specific to population clusters were collated. this revealed african, european, and asian cehz loci. these sites include a european cehz peak that corresponds to an apparent “gene desert” containing a long non-coding rna of unknown annotated function preferentially expressed in placenta, an african peak over a chromatin remodeller and polycomb group protein that has been previously associated with genetic determinants of height, and an asian peak over the x chromosome gene, eda2r, which encodes the ectodysplasin a receptor and neighbours the androgen receptor. these regions have been uniquely identified by the cehz approach. we hypothesize that further investigation of these loci will reveal a possible role in population-specific biological processes. extending the cehz approach to two cattle species, angus and brahman, comparing to the literature revealed that of the most extreme cehz loci overlap with genomic regions previously described as being under selection. similarly, in an analysis equivalent to the human sliding window approach we found of the top regions also have been previously documented as harbouring signatures of selection. furthermore, we also identified cehz loci overlapping with known qtl for production traits, including bta14:~25 mb which contains the plag gene previously associated with cattle growth and fertility. we have highlighted other regions that also discriminate the breeds, in each case coincident with genes encoding proteins of fundamental developmental importance: en plays a role in central nervous system pattern formation, eya plays a role in muscle fibre composition and arid4a plays a role in male fertility. 1heterozygosis, compression efficiency and z-scores values are averages of a window from the reference position.*the snps giving the signal in these regions were unassigned on the bovine assembly btau. enomic regions with noteworthy z-score normalized heterozygosity corrected compression efficiency across bovine brahman and angus populations. unlike fst cehz is computed on a within genome basis. no contrasting population is required, which means the analysis can be run on newly genotyped populations in isolation, identifying regions of interest even in species whose genome has poor functional annotation. furthermore, cehz can also be computed on the mammalian x chromosome whose hemizygosity in males normally precludes population-level analyses by conventional methods. the cehz human and bovine data are available as a hub that can be visualized using the ucsc genome browser: https://surf.genome.at.uq.edu.au/~uqrtaft/cehz/hub.txt). defining the compression efficiency parameter space in the discipline of complex systems science there exists the concept of ‘the edge of chaos’ capturing the properties of the phase transition that exists between order and chaos. this transition zone is important because it has been found to possess desirable evolutionary and computational properties. it did not escape our notice that the ce approach allows one to formalise and test this concept in the context of genomics. one can scramble the data, measure the ce consequences, and compare it to the informational properties of the real genomes. we scrambled the order of snps using both the proportions from that particular individual but also a deeper randomization based on proportions derived from the population at large. rand is valuable in defining the parameter space we are interested in, as it can be explored for the entire range of conceivable heterozygosity i.e. from to here, 100% produces a highly compressible string of 1’s while 0% is composed of a random string of 0’s and 2’s only. because this rand sequence is maximally chaotic the resultant curve defines the signal to noise threshold for every level of heterozygosity. intriguingly, it can be observed that the real mammalian dna sequences align to, or emanate from, the point of minimum ce coincident with ~33% heterozygosity. the outcome is similar across species. that is, the ce of genomes always aligns with the point of minimum ce. superimposed in figure  are lines intended to elucidate possible mechanisms for driving genomic movement through information space. overall, this creates an impression that genomes evolve from the point of minimum ce, reflecting the combined impacts of inbreeding, ld and other unidentified factors. there is a strong negative relationship between ce and het. however, through outbreeding, het values beyond 33% can be achieved and, in this region increases in het can be associated with increases in ce. from a numerical perspective, proportion-based regularity increases as one moves farther away from the ~33% het on both sides of the x axis, while order-based regularity increases as you increase ce moving upwards on the y axis. discussion given that the purpose of genomes is to encode and transact information, it is not surprising that principles from information theory have been previously used to quantify their informational properties. however, the historical use of compression per se in genomics has been more from a practical and technical perspective, such as how to store large datasets in an efficient manner, rather than that of pattern recognition and biological interpretation. the only previous example of clustering by compression in the genomic area that we are aware of is the mitochondrial work of which reconstructed eutherian and mammalian phylogenies. here, we have illustrated that ce analysis of snp data allows one to 1) discriminate populations reconstituting known aspects of their diversity, 2) identify at very high resolution genomic regions of evolutionary interest including validated signatures of selection 3) visualise evolution through informational space and 4) achieve these goals using a method that has an appealing logical simplicity. the hypothesis-free pattern recognition qualities of ce allow exploitation of order as well as proportion, the two sources of regularity in any data stream. this is important because the detection of patterns can be used to cluster data based on guilt-by-association and drive the inference of biological meaning. one conceptual advantage of using a proxy for direct genetic evidence rather than the direct evidence itself is that previously unrecognized informational footprints may be present in the data which we may wish to exploit but whose expected properties we do not need to identify, nor fully understand, a priori. overall, we document a promising new perspective on analysing genomic data which is intended to be complementary to existing mathematical approaches, not to supplant them. given this is the first publication of a wholly new approach, we are not yet in a position to formally connect our ideas to existing population genetics theory in a rigorous mathematical sense. nevertheless, given its particular biological interest to human genetics, we do explore the population-level allele pattern content of the ceu and asw slc24a skin pigmentation region in some more detail. from the broader genome-wide perspective we have to rely on less quantitative verbally expressed arguments. these draw intuitive connections between ce and various aspect of population genetic theory. population discrimination in order to infer population history, molecular geneticists conventionally look for specific genomic sites across individuals and search for changes in abundance or even fixation of an ancestral or derived allele. here we have taken a complementary strategy, exploiting various longitudinal patterns along an individual’s genome. the assumption we make is that closely related individuals will be more likely to share these longitudinal patterns of genome composition, however complex they may be. one appeal of this approach is we do not lose the informational context provided by physically proximate snps. in terms of the whole genome, we find ce allows all human populations to be discriminated, sometimes with little or no overlap. using the human hapmap dataset, the lowest ce is exhibited by the african american and other african populations and the highest ce by the asian populations. the groupings resonate with published phylogeographic reconstructions based on fst and pca analyses but are computationally much quicker and cheaper, consuming only a fraction of cpu time. in broad terms, at heterozygosity levels less than a third, there is clearly a strong negative relationship between ce and heterozygosity. however, this observation does not explain the ce output, with populations of similar heterozygosity discriminated by differential ce. the population discrimination is robust across mammalian species. runs of homozygosity are clearly an obvious compositional feature that will be exploited by gzip to compress the snp data string in the whole genome version of the ce analysis, but there are many others sources of regularity. one appealing analytical implication of the genome-wide ce approach is that the different scales of the various informational regularities can be assessed simultaneously by a single metric, irrespective of their size, direction or crypticity. the genomes of domesticated species offer a useful model in which to explore the genomic consequences imparted by population histories characterized by bottlenecks and artificial selection, as the genetic similarity of the various breeds provides a relatively stable background against which various evolutionary forces can be inferred. in each domestic species broadly similar patterns were observed. genome-wide ce increased for populations likely to have been founded from a small number of founders, and it decreased for outbred populations expected to be highly heterogeneous. ce was plotted against heterozygosity showing that signals of population substructure were evident in non-human species. genomic regions harbouring signatures of selection given the ability of whole genome ce to discriminate populations, we next explored within-genome structure to prioritise regions of particular biological interest. we used a high resolution sliding window expressed relative to heterozygosity and normalized by z-score. the correction for heterozygosity means the ce differences are more likely to be attributable to the pattern in order of heterozygotes and homozygotes and less to changes in proportion. the approach integrates a combination of individual genome regularity in the context of population homogeneity in that region. regions of even quite complex composition will yield a compression peak by cehz if they are shared by many members of a given population. this feature discriminates the window-based cehz analysis from the whole genome ce. that is, for cehz not only would we expect to find peaks over regions characterized by shared runs of homozygosity, but other compositionally more complex regions as well. the application of a matrix structure that permits comparisons of the same genomic regions across individuals clearly connects the output to existing population-level metrics such as ld. however, cehz finds loci over many different kinds of compositional regularities in a manner that defies a simple summary. a more detailed examination of allele composition in the slc24a region in asw, ceu and jpt reinforces the challenge of describing the mathematical nature of the compressible patterns exploited by gzip. irrespective of this, the data can be exploited to find commonalities and differences across any set of population groupings, in this particular case highlighting population substructure and showing the ceu and jpt are awarded similarly high cehz peaks for different reasons, and with different background het. in attempting to interpret the biological relevance of the compression peaks we examined the extent to which our new regions overlap with known signatures of selection. we find cehz successfully detects many of the known major signatures of selection in the various species. with regard to the human output we used and found substantial overlap. the ce approach has the appeal of pinpointing particular genomic regions, such as coding sequence or parts of coding sequences, at very high resolution. in human populations the highlighted regions capture genes encoding proteins involved in skin pigmentation, blue eye colour, lactase persistence and hair texture. a recent paper detected a signature of positive selection in slc24a in ceu, gih and tsi exactly concordant with our observations based on cehz. they used a new method which leverages sources of information relating to haplotype length and structure. haplops is similar to ehh and xp-ehh except that it estimates the population frequency of the allele under question and identifies the haplotype sequence on which the selected allele sits. furthermore, the lct gene encodes the lactase protein that allows milk digestion into adulthood. it is known to be under selection only in those european and african populations with an extensive pastoral history characterised by livestock domestication and an adaptation favouring regular milk and dairy consumption. the lactase signature recently detected in mkk was notable in that a combination of computationally intensive measures had to be leveraged. moreover, in contrast to cehz which provides strong evidence for the exact gene, the alternative methods could resolve the region only to a relatively broad  mb. in our data the nature of the lct-specific peak in ceu and mkk is visibly different, consistent with the purported evolutionary independence of the selection event. new human population predictions unique to cehz imply hitherto unrecognised roles for a long non-coding rna in european populations, a chromatin remodeller in african populations and the eda2r gene in asian populations. the eda2r is noteworthy in that it is present on the x chromosome which is not amenable to conventional analyses because it is hemizygous in males. a number of cehz peaks are shared by all the human populations. we might speculate these represent genomic constraint at a much deeper taxonomic level, perhaps the branch point of modern humans from other primates. it is interesting to note that the more homogeneous asian populations exhibit a frequency distribution of ceh z-scores characterised by a low mean value, but a number of very extreme outliers compared to the more heterogeneous african populations. in the cattle divergent regions contrasting angus and brahman breeds aligned to previously described signatures of selection. the recently documented plag is considered fundamental to tropical adaptation in brahman cattle. new predictions for the cattle breed comparison include en eya and arid4a. overall, it appears cehz is a useful metric for exploiting intra-chromosomal heterogeneity in a rapid, straightforward fashion. evolution and information compression what are the biological implications of the ce values we have computed? as a first step, we defined the total parameter space. this allows us to encapsulate the boundaries of the dna informational universe. in turn, this universe enables us to envisage how real dna sequence evolves at a whole genome level. we modelled ‘totally regular’ by first sorting each individual snp genotype prior to compression, and ‘totally irregular’ through several different randomisation procedures set at both the individual and population levels that account for proportion and order. the initial randomisation provided by rand breaks ld by scrambling the identical “ 2” proportions into chaotic order. this result shows that in practice ld serves to enforce data regularities on real-world dna sequences. the deeper randomisation provided by rand is perhaps surprising. it suggests each individual genome possesses highly cryptic proportional regularities not present in the population at large. we found that all populations in all species occupy a very specific zone, clearly converging at – or emerging from – a very well defined point in ce genomic space. they intersect at the point at which highly complex sequence most deeply explores the disordered space, without actually becoming chaotic. the overall uniformity of the shape of the output across all the populations/breeds of all the species, despite considerable compositional differences in both the density and functional bias of the snp chip technologies, points to the very high robustness of the result. nevertheless, snp chips characterise highly variable regions, so the translation of this output to full genome sequence remains uncertain and should be a focus of future work. we were next interested in direction of travel through this space. are we observing an emergence or a convergence from the point of minimum ce and maximum noise? our first attempt to answer this question was to examine the domestic species data. these species have a clearly identified progenitor which provides an unambiguous evolutionary sequence. however, snp ascertainment bias confounds interpretation here. what we can say though, is that life - characterised by negative entropy evolved from non-life which is usually characterised by high entropy. it is therefore tempting to assume that the more ancestral compositional states would have been more entropic. further, another source of sequence data in a range of species supports this idea. in the context of particular protein coding sequences, we have previously noted that when genome-wide codon bias is quantified informationally, it is those proteins apparently most relevant to the lineage under scrutiny that exhibit the lowest entropy. examples of these low-entropy ‘derived’ molecules include proteins influencing chloroplast physiology in plants, mitochondrial function in birds and hair formation in mammals. generalizing this broad line of reasoning is appealing as it places representatives of the modern african populations as relatively basal, which seems to be consistent with the consensus “out of africa” hypothesis of modern human evolution. in the future the hypothesis that derived genome sequences possess relatively low entropy could be validated using domestic species as a resource. one could compare the whole genome ce of the extant representative of the wild ancestor to various domestic populations. for example, we would predict the ce of the red jungle fowl genome, at an individual level, to be lower than individual genomes representing meat and egg producing domestic chickens. we would also predict population-level cehz sliding window scores to possess a more extreme distribution in the domestic breeds. some of these cehz peaks would characterise signatures of selection for egg and meat production. what else does this mean for our understanding of biological encoding systems? the phase transition between regularity and irregularity is theorised to be a high-impact zone of enormous computational power and evolutionary potential. this interests us given a genome is a computing device made of nucleic acid that is the product of evolution. the overall position of all the human populations supports a controversial concept from complex systems science that genomes are poised at or close to ‘the edge of chaos.’ this conclusion resonates closely with that of kong et al., who analysed prokaryotic and eukaryotic genomes using an novel regularity/order index called ø and based on averages of nucleotide distributions in a given sequence of pre-defined length.figure  also summarise the possible mechanistic explanations for the various trajectories taken by the populations and individuals through information space, based on considerations of both the implications of our data modelling coupled with the real world mammalian genomes. we see different spatial impacts of ld and extent of outbreeding depending on the particular population under consideration. the meaning of ce in the context of population genetics theory to finish, it is appropriate to more directly connect our ce work to existing population genetics theory, whose goal is to study the frequency and interaction of alleles and genes in populations. in population genetics theory, various evolutionary processes, particularly natural selection, drift, mutation and gene flow are explored to make inference about population history. the hardy-weinberg principle says that the frequency of alleles will remain constant in the idealised absence of selection, mutation, migration and drift and this provides a theoretical expectation against which population level deviations from equilibrium can be quantified and subsequently interpreted. in information theory terms, the point of equilibrium corresponds to maximum entropy, and extent of dis-equilibrium reflects differing amounts of negentropy. at a population level, nearby pairs of alleles have a high tendency to be correlated with each other. in genetic ‘hitchhiking’ an allele at one locus rises to high frequency in a population because it is linked to an allele under selection at a nearby locus, not because it has been selected itself. the same phenomenon applies to genes under runaway sexual selection. clearly, this phenomenon culminates in population-level homogeneity in allele combinations because of genomic similarity between individuals. adding further dynamism, these population-level patterns are gradually broken by the individual cellular/molecular process of genetic recombination, but at a slow rate. this ebb and flow of allele pattern formation and destruction among individuals can be exploited to detect the action of natural selection via selective sweeps, and to view the impact of migrations and founder effects. for example, it is well known that there is higher ld in asian populations, presumably due to the founder effects that occur during migrations limiting the number of haplotypes. ld is often viewed by a decay plot e.g., where it can be shown that deviation from equilibrium is considerably stronger for nearby loci. these decay plots are relatively extreme for africans due to faster ld decay and correspondingly smaller haplotype blocks than in the comparison asian and european populations. a number of existing metrics for selection are based on considerations of local decay of haplotypes. what does this mean for the various ce metrics and what are the phenomena that serve to underpin the patterns quantified by ce? whole genome ce is computed on an isolated individual basis. the coordinates of the population cluster describes the data at the population level. however, given this is fundamentally an individual-level metric, its relationship to ld might not be straightforward. for example, other sources of compositional regularity may apply including segmental duplications and g motifs and structures. it is also true in theory, that one can achieve the same compression efficiency for different reasons, but in practice we find that the accurate phylogeographic population-level clustering implies it is only similar related genome compositions that are awarded similar ce scores. also, we know that the rand modelling procedure serves to break ld and reduces ce. based on this reasoning, it is tempting to speculate that individuals with high ce presumably belong to populations that have even higher ld. this conclusion is clearly consistent with the population-level ce ranking we observe in figures , that mirrors known differences in ld between human populations, that is the africans showing the least ld and the asians the most ld, with the europeans intermediate. next we will consider the relationship of this thinking to the particular genomic regions identified by the sliding window cehz. from our informational perspective, remnant population-level patterns can clearly be quantified by cehz, and contrasted across populations, no matter how cryptic or complex the genomic composition may be at an individual level. a detailed specific example is given by the ceu and gih skin lightening signature of selection that resides over slc24a. at this stage, a confident determination of cehz’s exact biological origin – i.e. is there a particular compressible pattern diagnostic of natural selection versus genetic drift versus a founder effect? – is not possible. that being said, there are clearly numerous reliable patterns present at very specific genomic regions in one population, but not another. many of these have not been described before including those specifically overlying known functionally important parts of the genome, such as protein-coding genes, non-coding rna and so on. these new discoveries may reflect the fact that the mathematical nature of the population-level patterns we have highlighted did not have to be specified a priori, unlike fst which is more tightly expressed. the guilt-by-association heuristic tells us there is some bona fide population-level meaning in those regions. it is our contention that a post-publication community effort and a range of techniques will be required to ascribe functional significance or not on a case-by-case basis. to expedite this process, we have uploaded the cehz tracks onto the ucsc genome web browser. slower ld decay in asian populations seems consistent with our finding that the asians possess extreme outlier peaks in cehz reflecting high homogeneity in certain regions not observed in the other populations. it is worth pointing out that direct comparisons of two specified loci between populations are not apparent in decay plots, as all conceivable pairs are simultaneously plotted. by contrast, one strength of the cehz sliding window approach is we maintain the identity of the genomic region such that the population contrasts are directly comparable, and therefore biological interpretation can conveniently be made on a fine-grained regional basis. an example would be the european and gujarati indian selection events around the slc24a gene. finally, population genetic diversity has been quantified by allelic diversity – namely, the proportion of all copies of a gene made up of a particular variant. the genomes consortium showed that ceu, jpt and yri possess many snps displaying substantial absolute differences in allele frequency, and that this ability to differentiate populations decays rapidly as one increases physical distance from genic snps. our observations are consistent with some of these findings, namely the whole genome discrimination determined by ce, the concordance of some ceh peaks over genic regions in particular, and the elevation of african ce when examining coding snps only. caveats ce operates by exploiting regularities within a sequence regardless of the origin of the sequence. ce is not based on any theory of segregation inheritance, nor does it require knowledge of ancestry to phase the genotypes. in light of the strong correlation between fst and ce we conclude that ce accurately estimates genetic relatedness among populations without recourse to additional sources of information. the same conclusion is reached when ce is used a sliding window approach to capture genes under selection. because ce is a hypothesis-free pattern recognition method that detects regularities in segments of the genome, it is more in the spirit of the various haplotype-based methods, rather than single marker methods of population differentiation. the main weakness we have identified is - like ehh and fst - it does not allow for population stratification. further work is required to formalise other strengths and weaknesses relative to existing methods. our implementation of ce requires the use of the gzip tool which incorporates the deflate algorithm. this is included in all unix environments. however, other compression tools exist and could be used. also, from the computational perspective, the sequential use of gzip requires a great deal of parsing arguments and i/o operations. this is not an issue when compressing a whole matrix comprising genotype sequences from individuals within a population. nevertheless, if we were to program the deflate algorithm and perform ce analyses entirely in memory then the computation efficiency of ce analyses would be greatly improved.  we have exploited the pattern recognition qualities of information compression efficiency to assess genome patterns within and between genomes. this approach recreates established phylogeography and highlights known signatures of selection. some new regions with high population level scores overlying functional apparatus such as non-coding rna have also been identified. these regions are not simple runs of homozygosity so direct assessments of this nature cannot identify them. rather they are compositionally complex regions shared by individuals of a given population. we hypothesise some of these regions to be previously unidentified signatures of selection. 
single nucleotide polymorphism microarray data, a proxy for genome composition, contains patterns in allele order and proportion. closer inspection reveals that these prioritised genomic regions do not correspond to simple runs of homozygosity but rather compositionally complex regions that are shared by many individuals of a given population. a high resolution ce ‘sliding window’ scan across the human genome, organised at the population level, revealed genes known to be under evolutionary pressure. ce analysis of other mammals results in segregation by breed or species, and is sensitive to admixture and past effective population size. ce allows one to clearly visualise the evolution of individual genomes and populations through a formal, mathematically-rigorous information space. unlike fst, ce analyses do not require ab initio population comparisons and are amenable to the hemizygous x chromosome. these patterns can be quantified by compression efficiency.
 genomic information allows population relatedness to be inferred and selected genes to be identified. single nucleotide polymorphism microarray data, a proxy for genome composition, contains patterns in allele order and proportion. these patterns can be quantified by compression efficiency. in principle, the composition of an entire genome can be represented by a ce number quantifying allele representation and order.  we applied a compression algorithm to genome-wide high-density snp data from human, cattle, sheep, dogs and mice samples. all human ethnic groups can be clustered by ce and the clusters recover phylogeography based on traditional fixation index analyses. ce analysis of other mammals results in segregation by breed or species, and is sensitive to admixture and past effective population size. this clustering is a consequence of individual patterns such as runs of homozygosity. intriguingly, a related approach can also be used to identify genomic loci that show population-specific ce segregation. a high resolution ce ‘sliding window’ scan across the human genome, organised at the population level, revealed genes known to be under evolutionary pressure. these include slc24a, herc, lct and edar. we also identified a set of previously unidentified loci with high population-specific ce scores including the chromatin remodeler scmh in africans and eda2r in asians. closer inspection reveals that these prioritised genomic regions do not correspond to simple runs of homozygosity but rather compositionally complex regions that are shared by many individuals of a given population. unlike fst, ce analyses do not require ab initio population comparisons and are amenable to the hemizygous x chromosome.  we conclude with a discussion of the implications of ce for a complex systems science view of genome evolution. ce allows one to clearly visualise the evolution of individual genomes and populations through a formal, mathematically-rigorous information space. overall, ce makes a set of biological predictions, some of which are unique and await functional validation. information compressionphylogeographyselection signatures 