De Bruijn sequences are maximally disordered. Yet, they are computable. This implies that de Bruijn sequences retain yet a hint of order. Ordered objects like crystals have a regular structure that imposes order on placement of atoms (for instance), and yet there remains separation between those elements, and so a bit of disorder remains (we understand the physical implications). So, why is it that we find no object that is purely disordered, or purely ordered? Can a reader give a counter-example, physical or mathematical?
I gave a good example Peter, but you seem to have missed it.
And, de Bruijn sequences are a rather well defined concept.
And, the notion of maximal disorder is not hard to grasp.
If you have not some mastery over de Bruijn sequences, you should perhaps not be addressing this question.
De Bruijn sequences are special cases of permutation, where (in the case of the digits, for instance) the digits of adjacent values in the permutation repeat, such that they may be overlayed. Further, the length of the de Bruijn sequence is always the same as the value that is permuted.
But, consider this other question: What would be the yield (the output of the program) for a data compression utility, where that utility always provides the maximal possible compression? In particular, what could be said about the sequence of bytes within the resultant, compressed file?
Finally, I have posted many other questions, several of which address the details of a de Bruijn sequence.
To give a specific example, consider these symbols {A C G T} and all the three-mers:
AAA AAC AAG AAT
ACA ACC ACG ACT
AGA AGC AGG AGT
ATA ATC ATG ATT,
etc.
These can be arranged in many permutations, like
AAA TTT CCC GGG AGG GTT AGC ...
but here, we do not see overlay to be possible.
Now, for this permutation,
AAA AAC ACA CAA AAG AGA GAA AAT ATA TAC ...
we see that each pair allows for overlay of two symbols.
Hence,
AAA
...AAC
......ACA
.........CAA
...
The issue is, when you compute the entropy for such objects (de Bruijn sequences), the result is always maximal. Hence, de Bruijn sequences are maximally disordered.
Yet, they are totally computable.
It seems that I can find no object that is totally disordered, or totally ordered. This is to suggest that the continuum that is order-disorder has vacuous endpoints.
Peter, the fact is that for the 3-mer example that I gave, none of the LAST symbols (letters) is freely chosen; they are all constrained.
Further, take any standard NIST tool, apply it to a de Bruijn sequence, and observe the result.
Finally, any competent gene jockey knows the term k-mer; I think it needs no explanation.
Peter, I am not a competent mathematician, and often seek to obtain mathematical expertise from others. Nevertheless I do hold some rather interesting mathematical proofs, by demonstration. In particular, a specific, well defined (and recognised by others) example of a machine zygote.
Your unfamiliarity with genetics is not my problem; k-mer is jargon, 'tis true but, every geneticist knows what I mean when I use a term of that nature.
Further, if you knew a little bit more about genetics, and in particular the process of assembly, where genomes are derived, you would well understand the value of de Bruijn sequences - they tend to drive such assembly processes. Indeed, I learned about de Bruijn sequences by study of genetics.
The only benefit you are offering is the information content computation.
I will give you two hints.
One I think was made obvious by my use of "etc." in earlier post, but since you seem to need it, all combinations of length three are employed as "tiles" in the construction of a de Bruijn sequence; the probability of occurrence for all tiles (3-mers) is 1. Since there are a total of 64 such 3-mers (tiles), the length of the total sequence is 64 symbols.
Two, de Bruijn sequences have some rather interesting properties. I invite you to examine them.
Peter, from this Wikipedia article:
https://en.wikipedia.org/wiki/De_Bruijn_sequence
we see that the number of de Bruijn sequences B(k,n) is given by the equation:
((k!)^ (k^(n-1)))/k^n
It might also help you to know that de Bruijn sequences are considered bracelets; they wrap upon themselves.
100! is roughly 9.3E157
B(10,2) is roughly 3.9E65
Only a rather select subset of all permutations are de Bruijn.
Peter, the question has everything to do with order and disorder, and the relationship between the two. De Bruijn sequences are just an example of a sequence that is maximally disordered (this is why it works for genome assembly). Yes, B(4,3) is 64 symbols long, and it is a bracelet (a linear form of torus). And, I will not copy to these discussions, pages from Wikipedia that you can easily find yourself. Yet, I will give you this:
"Do you mean that if one starts counting ANYWHERE in the sequence and wraps at the end, then every 3-mer still appears exactly once?"
The answer is yes, and if you read the Wikipedia article on the topic, you would already know that.
One example of disorder is the brevity of a Fully Qualified Name. It is hard to distinguish one hydrogen atom from another, and one would be required to give such distinction in order to confidently communicate to another the identity of a specific such hydrogen atom, regardless of its location within the universe.
For a human context example, consider 1600 Pennsylvania Avenue. Those 24 characters (spaces included) are sufficient to identify a particular building that is located on the surface of the Earth. Yet, the identity of the average building that is located on Earth's surface requires a much longer list of symbols to specify it, within that human context.
In a similar way, for a de Bruijn sequence, the length of the Fully Qualified Names of all loci is a constant, n; i.e. B(k,n).
Peter,
Meanwhile, others, have recommended the question. So much for your counsel.
Peter, if you already know these things, then you are not acting in good faith from the start.
It has not gotten you, and similarly any other person, anywhere. Congratulations on your choice of a technique that is without utility.
My suggestion is that the interval, from (strictly and maximally) ordered to (strictly and maximally) disordered is open, not closed.
.
one small point : from Ramsey theory it follows that any " ordered structure" must happen (with a precise probability) in any random string of sufficient length (very rough wording of nice technical theorems, my apologies)
.
maybe it has something to do with the initial question ...
.
(sorry to interrupt you, by the way 😇)
.
.
another random thought : if i were given an infinite string and if i were told that this string does not contain some kind of pattern, then i would conclude that this string is not (Martin-Löf) random ...
randomness is not absence of "patterns" ; on the contratry, all paterns must be present but just with the right frequency !
.
Peter, the proper computational answer is to search, as belief systems do have their faults. De Bruijn sequences are maximally disordered, and yet, that disorder is the yield of a rather strict ordering process. Somehow, it seems this is a fundamental point, and the target of the originally posted question is to understand this expected fundamental point.
Fabrice, I suspect that all patterns that are other than a de Bruijn sequence per se, are instead decrepit de Bruijn sequences that have been corrupted to various degrees. Truly random sequences will never be as disordered as a de Bruijn sequence. You can check this with a shustring analysis on the sequence.
If you can generate long de Bruijn sequences from a short program then such sequences are not random from the algorithmic randomnes point of view (Kolmogorov)
Fabrice: Sure, computation generated sequences are by Kolmogorov and others not random. But, the fact is, you never have a sequence long enough to be random; i.e. all finite sequences are less than truly random. Further, all such sequences are computable. I can easily produce a sequence that has the same characters (such as are measured by shustrings) as the RAND Corporation's One Million Random Digits with 100,000 Normal Deviates by starting with a de Bruijn sequence and then degrading it to a sufficient degree.
- Badges
- Science topic
- Similar topics
- Mathematics