A Genome Puzzle

[superprismatic]

In sequencing DNA, technicians break up long molecules into

smaller pieces because it is easier to sequence small segments

than long ones. They must then reconstruct the target molecule

by fitting the small segments together using overlaps as a guide.

The small segments are sequenced beginning at either end in a

random fashion. So, for example, the segment ATACAG may also

be sequenced as GACATA.

In this puzzle, I have chopped up many identical 50-long sequences

into pieces of lengths 5, 6, 7, and 8. 30 of these pieces are:

ATACAG

TGACAT

GTCTTA

GTCGAGA

AACGA

CAAGG

CAGTGTGA

GTGGTGT

CCGATGAC

AGACAA

TGTGA

ATACAGTG

CTGTG

ACATA

GTGTCG

TACAGT

GTCTTAG

CATAA

GGTGG

GACTCCAG

TGTGA

CCAGTG

TGTGACA

GTGACATA

TGTGGT

ATTCTGA

TGAATACA

TAGCCG

TGTGACCT

CCTCA

I have insured that these 30 pieces completely cover the 50-long

sequence with which I started. Can you find that sequence?

[bonanova]

I like this.

A one dimensional jigsaw puzzle.

I'll give it a look this weekend.

[bonanova]

I gave it a try. Too many options to sort out. That is to say I could not program it.

[harey]

Still unsolved... I tried to omit chunks that are contained in other chunks (i.e. TGTGA is there twice and is contained in TGTGACA). I hoped that with the reminder I would be able to build longer chunks. Still too many combinations.

How is it done in praxis?

[plasmid]

Biologists don't tackle the question quite like it was posed in the OP.

If you read a DNA sequence like ATATCAGG, the read in the opposite direction wouldn't be GGACTATA. Nucleotides have a directionality; the "preceding" nucelotide would be attached to the 5' carbon of the nucleotide you're looking at, and the "following" nucleotide would be attached to the 3' carbon, and all (or nearly all) of our techniques start from the 5' end and work toward the 3' end. So this would look unambiguously like 5'-ATATCAGG-3'.

The tricky part is that DNA is double stranded, where each A is paired to a T on the opposite strand and each C to a G. And the strands run in opposite directions. So for the above sequence, you would have the two strands

5'-ATATCAGG-3'
...||||||||...
3'-TATAGTCC-5'

If you turn the complementary strand to show it in the conventional 5' to 3' orientation it would be 5'-CCTGATAT-3'. And there's generally no way to tell if you're looking at the strand of interest or its complementary strand.