ILLUSTRATIVE PROBLEM DOMAINS AT THE INTERFACE OF COMPUTING AND BIOLOGY 329
ment is that sequence complexity will be highly correlated with organismal complexity. (Some advan-
tages of dealing with strings of letters as an abstraction are discussed in Section 4.4.1.)
Because information theory treats all bits as alike and of equal significance, a purely information-
theoretic view would suggest that a gene of a thousand base pairs that encode a crucial protein required
for the development of a human characteristic has the same information content (about 2,000 bits) as a
random sequence of the same length with no biological function. This view strains plausibility or,
rather, would have limited applicability to biology. Thus, the example suggests that something more is
needed.
Generally, the types of complexity measures applied to DNA sequences are defined by their rela-
tionship to the process of computation. For example, a string might be considered to be a program, an
input to a program, or the output of a program, and the resulting complexity measure might include the
size of the Turing machine that produced it, its running time, or the number of states. Each measure
captures a different sense of complexity of the DNA string and will consider different strings to be
relatively more or less complex.
One such approach is the notion of Kolmogorov (or more formally, Kolmogorov-Chaitin-
Solomonoff) complexity. Kolmogorov complexity is a measure of the extent to which it is possible to
eliminate redundancies from a bit string without loss of information. Specifically, a program is written
to generate the bit string in question. For a truly random string, the program is at least as long as the
string itself. But if there are information redundancies in the string, the string can be compressed, with
the compressed representation being the program needed to reproduce it. A string with high
Kolmogorov complexity is one in which the difference in length between the string and its program is
small; a string with low Kolmogorov complexity is one that contains many redundancies and thus for
which the generating program is shorter than the string.
However, for the purpose of analyzing overall complexity, a purely random string will have a
maximal Kolmogorov score, which is not what seems appropriate intuitively for estimating biological
complexity. In general, a desired attribute of measures of biological complexity is the so-called one-
hump criterion. A measure that incorporated this criterion would indicate a very low complexity for
both very ordered sequences (e.g., a purely repeating sequence) and very random sequences and the
highest complexity for sequences in the middle of a notional continuum, neither periodic nor random.^68
Feldman and Crutchfield further suggest that biological complexity must also be defined in a setting
that gives a clear interpretation to what structures are quantified.^69
Other measures that have been proposed include thermodynamic depth, which relates a system’s
entropy to the number of possible histories that produced its current state; logical depth, which consid-
ers the minimal running time of a program that produced a given sequence; statistical complexity
measures, which indicate the correlation among different elements of an entity’s components and the
(^68) A related phenomenon, highly investigated but poorly understood, is the ubiquity of so-called 1/f spectra in many interest-
ing phenomena, including biological systems. The term “1/f spectra” refers to a type of signal whose power distribution as a
function of frequency obeys an inverse power law in which the exponent is a small number. A 1/f signal is not random noise
(random noise would result in an exponent of zero; i.e., the power spectrum of a random noise source is flat). On the other hand,
there is some stochastic component to 1/f spectra as well as some correlation between signals at different nonadjacent times (i.e.,
1/f noise exhibits some degree of long-range correlation). Similar statistical analyses have been applied to spatial structures, such
as DNA, although power and frequency are replaced by frequency of base-pair occurrence and spatial interval, respectively (see,
for example, A.M. Selvam, “Quantumlike Chaos in the Frequency Distributions of the Bases A, C, G, T in Drosophila DNA,”
APEIRON 9(4):103-148, 2002; W. Li, T.G. Marr, and K. Kaneko, “Understanding Long-range Correlations in DNA Sequences,”
Physica D 75(1-3):392-416, 1994 [erratum:82, 217,1995]). 1/f spectra have been found in the temporal fluctuations of many biologi-
cal processes, including ion channel kinetics, auditory nerve firings, lung inflation, fetal breathing, human cognition, walking,
blood pressure, and heart rate. (See J.M. Hausdorff and C.K. Peng, “Multiscaled Randomness: A Possible Source of 1/f Noise in
Biology,” Physical Review E 54(2):2154-2157, 1996, and references therein. Hausdorff and Peng suggest that if the time scales of the
inputs affecting a biological system are “structured” and there are a large number of inputs, it is very likely that the output will
exhibit 1/f spectra, even if individual input amplitudes and time scales are loosely correlated.)
(^69) D.P. Feldman and J.P. Crutchfield, “Measures of Statistical Complexity: Why?,” Physics Letters A 238:244-252, 1997.