William, what you are looking for is covered by information theory. Specifically, you have just defined entropy. What you call "minimal redundancy" is usually called "maximal entropy", equal to total randomness of a signal source (such signal cannot carry any information, btw). For a short review see http://www.clcbio.com/wp-content/uploads/2012/10/BriefReviewOfMolecularInformationTheory-1.pdf One of the open problems, I think, is to figure out the entropy rate of natural DNA. Finding it would probably equal to a full understanding of how all the information is coded in the molecule. See for example http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.30.8851 or http://diyhpl.us/~bryan/papers2/DNA/bits/Estimating_DNA_sequence_entropy.pdf

Given that one half of any strand of DNA can be paired with its complement by action of polymerase, I think it a bit of a stretch to assert that a maximal entropy string of nucleic acid residues represents no information.

Also, is it a proven fact that no nucleotide sequence of maximal disorder can serve to yield an RNA transcript?

i hesitate to jump in here, not being an expert in information theory, but it strikes me that the 'pairing' phenomenon seems analogous to the seeds used in pseudo-random number generation. A sequence may be pseudo-random, but encodes at least one quantum of information - the seed, or in the case of DNA sequences, the fact that it can pair with its reverse complement.

I believe it is not true that a pseudo-random sequence can't code for an mRNA (lot's of double-negatives in there!). The redundancy in the genetic code ought to go some of the way to allow coding of amino acids whilst maximising non-redundancy, and given that this is possible, then if there is a selective advantage in doing so, I'm sure it could be found somewhere.

Do you suspect a selective advantage in non-redundancy? I can imagine non-redundancy would be useful in simplifying error checking and correction machinery.

I am afraid you might be mixing apples and oranges in some of the examples.

For example, a 100 bp "plus" strand, of course, carries tons of information about the "minus" strand. Accordingly, it is also an example of extremely low entropy, since it is the only strand out of 4^100 that has the quality of being complementary.

You may have millions of random sequences, but the plus-minus pairs will be far from random, out of the zillion pairs you could form, only the half-million complementary ones are to form pairs.

The question about transcripts would go something like "How useful would a gene be to the host if it produced a different transcript everytime it was transcribed?" Because only then would it be a truly random-sequence transcript.

As for the seeds and pseudorandom sequences, I think it might be somewhat related to the problem of estimating the true entropy rate of natural DNA. We know the entropy is lower than our estimates, but without the knowledge of how information is coded in the sequence, it seems random to us. You could compress a pseudorandom sequence into the seed and the algorithm that generated the sequence, if you only knew which algorithm was used and how many other possibilities there were.

Johnathan: I got started with this analysis on the notion that one can define a genome by the sequences not present; what remains is present. I was surprised to see that even short (5 to 6 nucleotide residues) can be found missing in genome the size of Arabidopsis thaliana. Turning this around, if it happens that most short sequences (say 20 to 30 residues) are found represented but a few times (one to ten) then they will serve well as flags for the assembly of genome fragments. So, it became clear that I needed to understand the sequence in general, and how measures of entropy are for such sequences quantised, not continuous. When one takes effort to obtain the measures, one finds that A. thaliana at 31Mbp exhibits unique sequences of length 12 and 13 quite often. See the attachments for two graphs of the shustring length distribution.

That's an interesting plot. I wonder whether there is something about 12/13 mers that allows them to undergo selection for uniqueness. Uniqueness would be advantageous in preventing mispairing of chromatids, it would be interesting to see how those unique kmers are distributed among the chromosomes, and whether they are enriched in non- or coding regions - I could imagine a pattern of unique 12/13mers functioning as a scaffold for pairing. It also occurs to me that this is just over the 10-11bp repetitive pattern found for nucleosome positions, but that might be a red herring.

So, the table is:

n...............||S^n||

1.................4

2.............. 16

3.............. 64

4............ 256

5...........1024 also called K

and for each 5 nucleotides, the pattern repeats, with each repetition adding a new K, as in

6..............4K

7............16K

8............64K

9..........256K

10......1024K also KK or K^2 or M

with 15 being 1K^3 or G

Now, we see that for 31Mbp, we should expect 12 or 13 residues for unique locus identification, assuming no redundancy. If you add redundancy, you get shorter shustrings and longer shustrings. I should think that the graph may well be a solid measure of overall sequence redundancy; the graph looks ripe for statistical and geometric analysis, eh?

Also, in my last post, I had expected to attach two graphs; the user interface would not allow such multiple attachments. So, the intended second graph is attached.

Notice the twin peak of 39,900 bp. The graph attached next is a shustring analysis of one of those two peaks. Notice that they are not internally of a highly repetitive nature. There is some repetition and there is some non-repetition. The meta-level pattern of four peaks does suggest some higher-order structure to the sequence; perhaps a key to the chromosome pairing that you suggest.

These peaks are just next to the centromere.

A y-axis log10 plot of the data given in the first plot above is shown here.

Matej:

It will help me for you to be a little more detailed, explicit in your arguments.

It is minimally true that there are 108K different 16-mer sequences on four symbols that correspond to solutions S^2; out of the possible 4K^3 16-mer sequences, only 108K are of minimal redundancy, and all of them are of exactly equivalent redundancy.

The difference in information representation, between transcription processes and complementary pairing serve as two examples of semiosis in biology; meaning is always context dependent - in this case it depends upon the operator set applied to the information source.

Most important about the above mentioned 39,900bp subsequence is the set of measures I obtained from an NCBI BLAST. These are the data:

Arabidopsis thaliana chromosome 1, complete sequence

73682 7.975e+05 100% 0.0 100% CP002684.1

Arabidopsis thaliana chromosome 2, complete sequence

7513 6.717e+05 78% 0.0 100% CP002685.1

Arabidopsis thaliana chromosome 3, complete sequence

7276 5.759e+05 96% 0.0 100% CP002686.1

Arabidopsis thaliana chromosome 4, complete sequence

6082 1.524e+06 85% 0.0 99% CP002687.1

Arabidopsis thaliana chromosome 5, complete sequence

7520 1.766e+06 76% 0.0 100% CP002688.1

So, what insight might you offer regarding this repetitive region of 39,900 bp that happens to be found in four out of the five A. thaliana chromosomes with a 100% identity and 0 expectation via NCBI BLAST, and nearly so strong a score for chromosome IV? I realise that the A. thaliana genome is reputed to have much architectural change in the recent past but, would one still expect such identity of a subsequence across the whole set of chromosomes?

Also, I don't seem to find these correspondences to be mapped among the duplications shown in this image from Nature:

http://www.nature.com/nature/journal/v408/n6814/fig_tab/408796a0_F4.html

Dear colleagues, this paper (http://www.biomedcentral.com/1471-2105/6/123) shows similar distribution of shustrings as William's graphs (no surprise here), but it also shows distributions in randomized sequences (see Fig.5 in the paper). If you look at the difference, the peak at 11-13bp is expected in randomized sequence as well. There does not have to be anything functional or biological about that peak. The main difference is the asymmetric "tail" on the right. This tail must be caused by repetitive sequences, where you need a lot of nucleotides to finally arrive at a unique string. Maybe that is is the only biology reflected in the shape of the curve? Other ideas? In any case, thanks for this interesting topic.

I am familiar with the Haubold et al. paper, and with a paper by Gräf et al. "Optimized design and assessment of whole genome tiling arrays" These seem to be the only other papers to address the topic.

I really would like some feedback from those well familiar with the meaning of the above statistics.

Is it common to see such mappings of long sequences without so much as a single nucleotide residue of alteration?

William, my guess is this is caused by LTR retrotransposons. I looked up the region you reported and there seem to be exactly five regions marked as "transposable elements". Their similarity depends on their age, if they are recently copied, it could be easily close to 100%. Certain families of LTR retrotransposons, such as Copia, are known to preferentially target centromeres, which you mentioned as well (http://www.ncbi.nlm.nih.gov/pubmed/22431508).

Oh, forgot the attachment

Excellent! Thanks.

So, you might like to see the full log by log graph of the shustrings for chr I.

After much cogitation and the kind replies, and especially upon review of a paper by Ilie and Smyth "Minimum Unique Substrings and Maximum Repeats?" it occurs to me that the method employed by my algorithm is to compute the lexicographical ordering and use that do elucidate shustring length. There is no need to compute the suffix array in order to find shustrings.

More specifically, since the generation of the Suffix Array occurs by means of the computation of the lexicographical ordering of strings, it is possible therefore to generate the shustrings while generating the Suffix Array, and so one need not post Suffix Array generation then consult that Suffix Array in order to generate the shustrings.

Nota Bene - It takes at least as much work to generate the Suffix Array as does it take to generate the shustrings. Using the Suffix Array to generate shustrings therefore necessarily results in twice as much computation as is needed to generate shustrings without use of the Suffix Array.