Лаборатория RuCTF Quals 2014. PPC 300 Write-up

timcess
, 19 March 2014

Guys, we were happy to get a Moomin's DNA! And we wonder, what substring is the origin of replication in the Moomin's DNA? Could you help us?

 

First we have idea that origin of replication is place where sequence begin repeats. And we need take 32 symbols from that place. Our script found that there are some cycles in file and (!) file consist of four concatenated identical parts. 32-length start of each cycle was not the answer. But script help us, because we can analyze not all file but only fourth part of it. After googling "origin of replication" and reading bioinformatics cources we found out that in origin of replication some string repeats very frequently and that string is some "indicator" of origin. Different genomes have different string-indicators of origin. So, we decide that our goal is the most frequent substring of length 32 in file. I decide to use suffix tree for this purpose. But it used too much memory on whole file. We can slice file on quite large pieces and calculate most frequent string in every piece. And probably we have one from two cases:

  1. String repeat frequently in small piece of file
  2. String have uniform distribution.

In both cases if right answer is more often than other string slicing would work.

split -a 10 -b 655360 word_quat
ls x* | xargs -L1 ./freq >> result

And in the last block: GGAACAAGTTACATGGGCCGAATGCTATTGTC repeat 11 times! (In other blocks every string repeats maximum two times)

freq.cpp