Extending the discussion of shustrings, it occurs to me that indeed this will perhaps be the best measure of sequence redundancy. If it happens that a genome of arbitrary size is of minimal redundancy, then all shustrings will be of just one or two sizes; a histogram will show just one column (or in the worst case, two columns); the line is vertical. On the other hand, a genome of arbitrary size and is totally redundant will have an horizontal line. it is between these regimes that we see this graph:
So, this call is out for opinions of others regarding the use of this curve as a formal measure of sequence redundancy.
Dear William,
Isn't shustring phenomenon a simple consequence of minimal redundancy? In fact, you can measure redundancy by Kolmogorov complexity (in practical applications just use zip program). You know that when "almost all" strings of size n have Kolmogorov complexity approx n-c for some fixed constant c. Your shustrings are those who contribute to the constant.
This point of view reminds me some old articles of Eric Rivals:
- Fast Discerning Repeats in DNA Sequences with a Compression Algorithm
É. Rivals, M. Dauchet, J-P. Delahaye, O. Delgrange
Extended abstract in the 8th Workshop on Genome and Informatics (GIW97), Tokyo, 12-13 Dec 1997
-Detection of significant patterns by compression algorithms: the case of Approximate Tandem Repeats
É. Rivals, O. Delgrange, J-P. Delahaye, M. Dauchet, M-O. Delorme, A. Hénaut, E. Ollivier
Computer Applications in BIOSciences (CABIOS) , p. 131-136, vol. 13(2), April 1997
He has also some interesting results on the distribution of the number of missing words in random texts which can be relevant to you:
-The Number of Missing Words in Random Texts
S. Rahmann, E. Rivals
Combinatorics, Probability and Computing, 12, p. 73-87, 2003
Hope this may help.
Generally, shustrings are shortest when there is minimal redundancy; maximal entropy. We may see this in a progression of S^n, n = {1, 2, 3, 4, ...} and S = {A C G T}, where the values of ||S^n|| are 4, 16, 64, 256, 1K, 4K, 16K, ... and for such systems, if entropy is maximised, then each shustring is of exactly length n; at the integral cardinal numbers, each of the elements of S^n is represented exactly once in a sequence of length ||S^n||; there are many such sequences of identical maximal entropy.
I have seen mention in several papers lament for quality in redundancy measures, usually quality that seems relevant to genetics instead of information theory. My suggestion of shustring histograms concerns this alternative expression, a sense of entropy relevant to the particulars of genetics.
Also, given that for large genomes we can expect shustrings of certain minimal lengths, we should therefore perhaps find reason to examine those few shustrings of unexpected short length (like three or four residues below the shustring with most common length), for those may indeed be subject to negative selection. For instance, in the case of a genome of one billion base pairs, it should not be surprising that shustrings of length 20 occur in greatest abundance. A shustring of just 14 or 13 base pairs will be unexpected, and serve to indicate nucleotide sequences that are selected against. Some previous researchers have reviewed this approach. The greater the difference in size between the expected length for maximal entropy and the length of the shortest shustring identified, the greater will be the selection.
- Badges
- Science topic
- Similar topics
- Computer Science and Engineering
- Bioinformatics
- Bioinformatic Tools