The search for shortest unique substrings (shustrings) of the genome is an important problem, for in some sense it is the mix of these shustrings that defines the phenotype of an organism. A related question concerns the set of shustrings that *is not* found within any genome, for the presence of these may correspond to specific detrimental consequence in organisms. So, my question addresses both the issue of any prior review (there has been) and any discussion of justification for the observance of non-representation of these shustrings within organisms. The shorter the length of such sequences, the more important would be any corresponding justification, I should think.
So, if one finds that the shortest non-represented shustring is of the order of eight or fewer nucleotides, this would be significant. For eight loci, we have only 64K possible combinations. As the human genome is 4KKK (four billion) loci long, we should find each of the 64K combinations represented at least 4KKK / (8 * 64K) times, or more than 7000 times on average, without considering overlaps; just each eight loci as a tile, and the genome as a list of tiles. Yes, I am assuming a high entropy genome, and the repetition counts would be much less for some, and much greater or other, shustrings in the case of lower entropy genomes. Nevertheless, I suspect that one might find some common subset of shustrings that are not represented in nature.
It is actually quite easy to determine the non-represented shustrings.
You might find the following paper interesting: Hampikian G, Andersen T: Absent sequences: nullomers and primes.
Pacific Symposium on Biocomputing 2007, 12:355-366.
Thank you much for this paper, as it is keenly directed to my question.
Very interesting question. A quick search yielded these papers:
Nullomers: really a matter of natural selection? C Acquisti, G Poste, D Curtiss, S Kumar - PloS one, 2007 -
On finding minimal absent words. AJ Pinho, PJSG Ferreira, SP Garcia
Efficient computation of absent words in genomic sequences
J Herold, S Kurtz, R Giegerich
Forbidden penta‐peptides
T Tuller, B Chor, N Nelson - Protein Science, 2007
Minimal absent words in prokaryotic and eukaryotic genomes
Best regards
SO... WTF ARE THEY (absent oligonucleotides)? It would be nice to have an answer here as it is hard to access the papers listed above.
Dr. Konopka:
Ultimately, nullomers are short sequences of nucleotides that are not represented within a DNA molecule. For a long sequence drawn on a small alphabet, such as DNA, there are many, many short sub-sequences that are not represented; I will forward to you in a subsequent message an analysis of the shustrings and nullomers of the RAND million random digits.
I am especially interested in particularly short nullomers; why are they not conserved in the genetic record. Please consider this graph, derived from shustring analysis of the Vibreo cholera genome.
wrb
- Badges
- Science topic
- Similar topics
- Bioinformatics
- Bioinformatics and Computational Biology