For clarity, the ordering of shustrings along the DNA molecule is unique, for any set of shustrings.

From the viewpoint of an assembled genome this seems trivial. Any short unique substring must be in sequence with all other short unique substrings.

Problems may occur when genome rearrangements occur (espcially reversals) and one organisms chromosome is compared to another organisms rearranged chromosome. In that case no such guarantee exists anymore even if the set of short unique substrings is the same.

From the viewpoint of an unassembled set of reads without a reference genome, there may be many ways to reach a viable assembly which all lead to different sequence of shustrings due to the large number of repeats in genomes.

By definition, shustrings in long repeat areas of the molecule will themselves be very long, indeed. I think the strong point of my claim is that genome assembly becomes a matter of finding all the shustrings. Also, it is obvious that the set of shustrings for any chromosome will be different, generally, from the set of shustrings for any other chromosome. So, crossover events will lead to the selection of a different set of shustrings that will correspond to the resulting DNA molecule.

This question is motivated by an observation, made clear upon examination of the combinations one may make over a short string.

For the four residues {A C G T}, it is possible to represent each one in a sequence of four exactly three different ways:

ACGT......ACTG......AGCT

Careful review will show that all three orderings are distinct from one another.

(Note: We consider the sequence to be equivalent to the mathematical notion of necklace, and so one might expect N!/N combinations - 4!/4, or

6 combination, but three are reversals of the other three in a one-to-one mapping between elements of the set. We disallow reversals.}

If one looks at the 16 pairs of nucleic acid residue {AA AC AG AT CA CC CG ... TG TT}, it happens that these may be represented each one time within a string of 16 nucleotide loci. Interestingly enough, there are some 164,888 permutations, with some duplication and reversals. Elimination of duplications and reversals reduces the number substantially but it is not one. Indeed, it is not anywhere close to three.

Each of the pairings given is a shustring of the sequence. So, the answer is no, there is generally no unique ordering to a set of shustrings.

Important now is the influence of ordering (redundancy) of the DNA molecule to the length of shustrings.

Interesting, however, I do not understand the definition of a shut string.

For the four residues {A C G T}, it is possible to represent each one in a sequence of four exactly three different ways: ACGT......ACTG......AGCT

Can you explain?

If one looks at the 16 pairs of nucleic acid residue {AA AC AG AT CA CC CG ... TG TT}, it happens that these may be represented each one time within a string of 16 nucleotide loci.

Do you mean to say that all of these pairs can occur within 16 positions? Are you looking for a shortest common super string (and eventually the number of SCSSs from a given set of strings)?

Best regards.

Interesting that you see, by your own calculation, that within any sequence of four nucleotides (repeats not allowed) there are only three microstates in which the sequence can be found; the entropy of the sequence is 1 in 3; it is not 1 in 4 ^ 4 (1 in 256).

If you don't want to call it entropy, fine. We will call it disorder instead.

The shustrings of this four loci sequence are A, C, G and T. That is to say, it takes just one symbol to uniquely identify each locus of the sequence. For instance, there are not two A residues, and so I need not have (at minimum) two symbols needed in order to discriminate between two loci.

In the case of the sequence

AACCAGGTCTGCGATT

It is easy to verify that the sequence AA is found at locus 1 and no where else in this 16-mer. Indeed, each of the two-mers is found at the correspondingly listed locus:

AA 1

AC 2

AG 5

AT 14

CA 4

CC 3

CG 12

CT 9

GA 13

GC 11

GG 6

GT 7

TA 16

TC 8

TG 10

TT 15

This is to say, each locus is uniquely identified by a two-symbol shustring (shortest unique substring). Hence, this sequence has the highest possible disorder; no other 16-mer sequence is more disordered than is this 16-mer sequence, although it happens that the number of equivalently disordered sequences is rather large - 82,944 of them.

Consider that the 16-mer AAAAAAAAAAAAAAAA has no disorder. Nor do the other three mono-nucleotide residue 16-mers. Further, the 16-mer CAAAAAAAAAAAAAAA can be rotated to 16 different positions (the location of the C in the sequence can change) and yet there is no way to discriminate between any two such rotations (this is especially true for the Necklace interpretation). This tells me that 1 in 16! is not the best expression of entropy for a symbol sequence; the shustrings are a much better expression of sequence disorder.

All other things being equal, the shorter the shustrings of a sequence, the more the sequence is disordered.

Also, with the above equation, we can generally determine the greatest disorder possible for any sequence.

NB - I am not looking for Shortest Common Super String (though I am looking up that topic to learn more about it).

My best wishes to you, as well.

wrb