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?
Biology Stack Exchange is a question and answer site for biology researchers, academics, and students. It only takes a minute to sign up.Sign up to join this community
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.
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.