Tell me more ×
Biology Stack Exchange is a question and answer site for biology researchers, academics, and students. It's 100% free, no registration required.
up vote 9 down vote favorite
2

What length are the shortest strings of DNA not present in any known person's genome, and what are they?

And is there a database online by which I could find this out?

share|improve this question
2  
Just for my personal curiosity... why? Anyway, the fact that not everyone's genome has been sequenced may pose a problem – nico Jul 31 '12 at 12:59
3  
I was about to write a description of how to find this out yourself but after closer reflection, this sounds hard. Essentially you’d have to build a dynamic programming solution but the solution will still have an exponential runtime with a huge exponent in the length of the result string (which we don’t know). – Konrad Rudolph Jul 31 '12 at 13:55
I would love to see an actual algorithm for this. The answers so far are tempting but remain quite theorethical – nico Aug 1 '12 at 5:52
@KonradRudolph can you turn that into an answer and expand on it? Sounds interesting but I'd love to know why it would be that hard and what that solution would look like. – Richard Smith Aug 1 '12 at 11:52
1  
@Richard Actually, Ilmari’s algorithm would work in linear time. My approach was approaching the problem the other way round because I assumed generality, whereas Ilmari (correctly) assumes that we can give an upper bound on the length of the non-present infix, which allows the usage of look-up tables. My approach would have iterated over the whole search space of all possible k-tupes for k=2… (which is exponential) and check whether each of those exists a pre-built index of the genome. – Konrad Rudolph Aug 1 '12 at 14:17

2 Answers

up vote 7 down vote

The human genome contains less than 416 base pairs, so, even after including a factor of 2 for the two strands and another to allow for some genetic variation, there must certainly exist some 17-base string not found in either strand of the genome.

Now, 417 bits is two gigabytes, which fits easily within the memory of a typical desktop computer these days, so a simple and efficient algorithm for finding such a string would be to set up an array of 417 bits, initialize them all to zero, and then simply iterate over the entire genome (including all known variations), taking each 17-base subsequence (and its complement), mapping them to base-4 integers and setting the bits in the array at the positions given by those integers to one.

Once you're done, any remaining zero bits will correspond to strings not found in the genome. More to the point, the longest consecutive block of zero bits will give you the shortest base string not present in the genome.

share|improve this answer
simply iterate over the entire genome (including all known variations): simply is not really the word I would have used but still... – nico Aug 1 '12 at 5:49
@Ilmari: What you find with your method is those 17-sequences not in one human genome. But the question was about any known person's genome. – rwst Aug 1 '12 at 8:01
@rwst: The method I described can just as easily process multiple genomes, or fragments of genomes, and find those k-mers which are not present in any of them. I'm sure there are other complications one would need to deal with to apply it to actual genome data, but this should not be a major one. – Ilmari Karonen Aug 1 '12 at 14:14
@nico There are special data structures for this which do make it as simple as iterating over a single string (except that for each position you don’t have a single 17-mer starting there, but a list of 17-mers). – Konrad Rudolph Aug 1 '12 at 14:22
this is a good answer - there are certainly some 17mers that do not show up in the human genome. its certainly not possible to say that a given 17mer doesn't show up in any human genome, at least until we have sequenced every cell in every human being's bodies (non germline mutations happen too often). That sounds hard. – shigeta Aug 1 '12 at 16:01
up vote 4 down vote

This actually wouldn't be too difficult to find. A common algorithm in genome assembly first takes stretches of DNA and finds all the substrings of length k that are present. (These are known as k-mers and the algorithm then builds the assembly based on how k-mers overlap.) So, given a genome(s) it's not that difficult to find all the k-mers of a certain length.

As Ilmari's answer points out, there are definitely 17-base k-mers that don't exist in a string of DNA the size of the human genome. Given the amount of repetitive content present in actual genomes, the actual shortest string will almost certainly be less than 17 base pairs.

share|improve this answer
Even if you give such a string you will never be 100% sure that you covered all human genomes, as asked. – rwst Aug 1 '12 at 14:58

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.