DNA Fingerprinting in APL

by Ian Clark

Transcribed from the printed issue; not yet reviewed. Read it in the PDF of the issue, page 38

Symbolic Modelling¶

I’m sure I’m not the only one who subscribes to lots of worthy periodicals which pile up unread. But two which get scanned from cover to cover (besides VECTOR of course) are New Scientist and School Science Review. What I like about the latter are the short practical articles which bring mysterious fashionable subjects to life with classroom demonstrations a four-year old could understand. Like Groucho Marx I miss having a four-year-old on standby, so School Science Review is the next best thing.

A recent issue contained a marvellous exposition of DNA Fingerprinting by Elizabeth Burns [1]. This sparked an idea of my own. Burns clearly explains the ‘cookery’ of the whole business. With its intricate procedures it’s like the early days of photography, but the simple principle shines through the author’s account.

But how do you explain this principle to a class if you’ve not got the apparatus for agarose gel electrophoresis, the expensive enzymes, the radioactive tracers and the X-ray film? You could use charts and diagrams, but these really serve to mystify the whole thing. By that I don’t mean they make it hard for the class to understand, but they move it out of the real world into the fairy world of coloured shapes and arrows.

Or you could use a computer running APL. For some people that’s just another fairy world, but others appreciate having an ‘abstraction’ that’s concrete enough to play with. There’s not one but three or four independent bodies of literature dealing with this sort of thing, but I’m deliberately not using the terminology of any of them. Back in the 70s there were people who called it Simulation and Gaming, but that’s not serious enough for today. What should we call it? The mathematics of genetic engineering? Mathematical modelling? Too frightening. It’s not really mathematics, more like numerical engineering. The numbers aren’t really important either. So it’s symbolic engineering. Perhaps there’s nothing wrong with Gaming after all. So here’s my DNA fingerprinting game.

Junk DNA¶

Everyone knows that DNA is the machine-code for a wet computer. The Human Genome is written in DNA. It codes for all our proteins, notably enzymes, little molecular nuts, bolts and spanners which build us up from basic nutrients and keep us ticking over.

But during your lifetime and mine, perhaps only 10% of it ever gets used to create proteins, or expressed. What does the remaining 90% do? Nothing (not, at least, during an individual’s lifetime), except to take part in chromosome replication and slow down cell-division so that we don’t grow up too fast. But replication isn’t a perfect process and since it doesn’t do anything it soon gets in a mess. Just like some of my APL workspaces! In fact unlike the 10% of functional ‘genes’, or exons (which have to be replicated dead right, or you’re dead in the water before you start) the 90% of ‘junk DNA’, or introns, are highly variable and particular to you, the individual, like your fingerprints. That’s why DNA fingerprinting works. Only identical twins have the same DNA fingerprint. Non-identical twins show up quite different patterns.

We now know almost everything about the DNA ‘wet computer’, but only at the machine code level. It’s as if aliens get hold of the complete works of Shakespeare. They quickly discover the punctuation and the letters of the alphabet, and recognise all the permissible combinations of characters into words and sentences. They classify the Bard’s complete vocabulary of 10,000 or so words, and discern the correct usage of verbs, nouns and prepositions. But the remorseless tragedy of Romeo and Juliet, or why Hamlet does the weird things he does, completely escapes them. ‘What does it all mean?’ they’ll ask. But until they can observe real people going about their lives and connect it in detail with their syntactic knowledge of Shakespeare’s works they’ll be none the wiser.

Sample data¶

Consider the following character matrix, taken from the workspace DNAFING whose functions are listed in the appendix:

[1]  Warning to Children
[2]  by Robert Graves
[3]
[4]  Children, if you dare to think
[5]  Of the greatness, rareness, muchness,
[6]  Fewness of this precious only
[7]  Endless world in which you say
[8]  You live, you think of things like this:
[9]  Blocks of slate enclosing dappled
[10] Red and green, enclosing tawny
[11] Yellow nets, enclosing white
[12] And black acres of dominoes,
[13] Where a neat brown paper parcel
[14] Tempts you to untie the string.
[15] In the parcel a small island,
[16] On the island a large tree,
[17] On the tree a husky fruit.
[18] Strip the husk and pare the rind off:
[19] In the kernel you will see
[20] Blocks of slate enclosed by dappled
[21] Red and green, enclosed by tawny
[22] Yellow nets, enclosed by white
[23] And black acres of dominoes,
[24] Where the same brown paper parcel -
[25] Children, leave the string alone!
[26] For who dares undo the parcel
[27] Finds himself at once inside it,
[28] On the island, in the fruit,
[29] Blocks of slate about his head,
[30] Finds himself enclosed by dappled
[31] Green and red, enclosed by yellow
[32] Tawny nets, enclosed by black
[33] And white acres of dominoes,
[34] With the same brown paper parcel
[35] Still untied upon his knee.
[36] And if he then should dare to think
[37] Of the fewness, muchness, rareness,
[38] Greatness of this endless only
[39] Precious world in which he says
[40] He lives - he then unties the string.

I reproduce Robert Graves’ poem [2] in full because it sums up the whole DNA business for me, on a variety of levels. The level which matters here is that we’re going to use it in a ‘symbolic model’ of DNA fingerprinting.

Three blocks of text, lines [9] to [14], [20] to [25], [29] to [35], are repetitions, right? Wrong. There are significant differences. Let’s construct char vectors s1 s2 and s3 out of them like this:

      s1
blocks of slate enclosing dappled/red and green, enclosing tawny/yellow nets
      , enclosing white/and black acres of dominoes,/where a neat brown pape
      r parcel/tempts you to untie the string./
      s2
blocks of slate enclosed by dappled/red and green, enclosed by tawny/yellow
      nets, enclosed by white/and black acres of dominoes,/where the same br
      own paper parcel -/children, leave the string alone!/
      s3
blocks of slate about his head,/finds himself enclosed by dappled/green and
      red, enclosed by yellow/tawny nets, enclosed by black/and white acres
      of dominoes,/with the same brown paper parcel/still untied upon his kn
      ee./

Let’s imagine they are DNA samples taken from 3 suspects. Now what about the scene-of-crime sample, sx? Run the function: secret (see Appendix) to select sx from one of s1 s2 s3 at random. Now the deed is done! (Don’t peep).

Burns [1] describes the chemistry of digesting a blood clot and precipitating the DNA. A series of restriction endonucleases (or restriction enzymes) are then added. Each restriction enzyme is able to find its own special short sequence of DNA codons and attach itself to the DNA strand at that position, whereupon it actually snips the strand there. A codon is a ‘letter’ in the DNA ‘alphabet’. There are precisely 64 possible distinct codons. Remarkably this is the same order of magnitude as most human language alphabets. Using poetic verses for strands, and letters for codons, we can illustrate this process by applying the function: restrict to s1 …

      s1 restrict 'in'
blocks of slate enclosin*g dappled/red and green, enclosin*g tawny/yellow ne
      ts, enclosin*g white/and black acres of domin*oes,/where a neat brown
      paper parcel/tempts you to untie the strin*g./

The arg: 'in' models a particular restriction enzyme which searches out all occurrences of the substring: 'in' and snips the strand immediately after it. Only we don’t snip z physically. Instead we insert an asterisk at the snipping site. The function: do applies a series of such restrictions to its argument z (representing the DNA strand) so that more and more asterisks appear:

      z←z restrict'in'
      z←z restrict'the'
      z←z restrict'os'
      z←z restrict'of'
      z←z restrict'you'
      z
blocks of* slate enclos*in*g dappled/red and green, enclos*in*g tawny/yellow
      nets, enclos*in*g white/and black acres of* domin*oes,/where a neat b
      rown paper parcel/tempts you* to untie the* strin*g./

Function: do now models the chopping of the strand by counting the number of characters between successive asterisks…

      i←(z='*')/⍳⍴z ⍝positions of '*'
      i←i-0,¯1↓i     ⍝lengths of chopped strings
      i
10 14 3 32 3 28 3 27 7 48 14 7

Each number in i represents a chopped strand of a particular length. Thus there are strands of 3 codons, 7 codons, 10, 14, etc.

Now electrophoresis simply applies an electrostatic field which drags the DNA strands along a ribbon of gel from the cathode (-) a little pool of DNA at one end, towards the anode (+). After a set time interval each strand has travelled a distance which depends on its length. Simple as that.

However, because DNA itself is not coloured, and there’s so little of it in the gel anyway, a complex process using X-ray film and a radioactive probe which sticks preferentially to DNA is now used to ‘develop’ the chromatogram, as it were, and ‘print’ it onto a piece of nylon fabric. This process, called Southern blotting, shows up each clump of chopped strands of a given length as a dark band. To minimise calibration problems, samples to be compared with each other are processed in parallel on the same gel plate.

The function: do models the ribbon of gel (the chromatogram) as a string (z again) of w periods '.'. Then it sets z[i] to a fat blobby character to represent the dark bands caused by pieces of length i[1] i[2] etc.

      z←w⍴'.'        ⍝the fresh chromatogram strip
      z[i]←'□'       ⍝add the dark bands
      z
..□...□..□...□............□□...□...............□....................

We have grossly simplified things. You have to imagine the pool of DNA to be at the right hand end of z, not the left, because shorter strands diffuse further through the gel in a given time. The physical mechanism is complex. DNA strands are negatively charged, but shorter strands happen to have a greater charge/mass ratio, which is what basically determines the distance they travel. But at the level of our model, this doesn’t matter.

Here is a sample forensic analysis, sx being the scene-of-crime sample and s1 s2 s3 taken from suspects. We first ‘do’ sx by itself, then in comparison with each suspect sample in turn…

      do sx
......□..□...□□...............□□...□..........□.....................
      do s1 ⋄ do sx
..□...□..□...□............□□...□...............□....................
......□..□...□□...............□□...□..........□.....................
      do s2 ⋄ do sx
......□..□...□□...............□□...□..........□.....................
......□..□...□□...............□□...□..........□.....................
      do s3 ⋄ do sx
......□..□...□...□........□...□□...□................................
......□..□...□□...............□□...□..........□.....................

from which we see that the best match with the unknown sample sx is s2.

Interestingly the scene-of-crime sample need only be a partial strand of the culprit’s DNA. Try chopping a length off the front and back of sx:

      sx←10↓¯15↓sx
      do s1 ⋄ do sx
..□...□..□...□............□□...□...............□....................
......□.....□.□...............□□...□..........□.....................
      do s2 ⋄ do sx
......□..□...□□...............□□...□..........□.....................
......□.....□.□...............□□...□..........□.....................
      do s3 ⋄ do sx
......□..□...□...□........□...□□...□................................
......□.....□.□...............□□...□..........□.....................

Sample s2 still gives the best match with sx, with 6 of the 7 sx bands lining up, as opposed to 2 coinciding bands with s1 and 4 with s3. In a real example, there would of course be many more bands and a few more coincidences. The court evidence (if it was going to be disputed) would be presented in much the same way as with a traditional scene-of-crime fingerprint.

Burns concludes her article by revealing that DNA fingerprinting is not only a forensic tool in criminal investigation, but is also useful in settling paternity disputes and tracing patterns of migration and evolutionary trees in biology, due to the DNA becoming more similar the closer two individuals are related. Or even two species. Few animals carry so much junk DNA in their chromosomes as we do, so the DNA from different but related species is not that dissimilar. Studies like this are revising considerably our view of the living world based on 19th century taxonomy.

However a computer programmer may see other possibilities in the do procedure. It avoids the labour of comparing two sequences of symbols (bytes) for (long) common substrings by systematic search. Yes, it still does string-search, but only using 2- to 4-byte strings, so the whole process needn’t take much longer than calculating a check-total. How about trying it with the object code of different release levels of a given program? How about using it on a memory dump to detect the presence of a given code-section by its characteristic bands, maybe a computer virus?

As a class exercise, try generating a random string of characters and apply do to see its pattern of bands, or ‘fingerprint’. Experiment with different ‘restriction enzymes’. Build a ‘family tree’ by swapping a pair of adjacent characters chosen at random to form a ‘child’ from a ‘parent’ string. Now mix the samples up and see if the class can reconstitute the family tree, or at least the degree of kinship, from the do-fingerprints.

References¶

Burns, E., DNA fingerprinting: a detective story. School Science Review, 77 (279), Dec. 1995, 29-35. ISSN 0036-68911
Graves, R., Warning to Children. The Penguin Book of Contemporary Verse, 1962, 128. Penguin Books Ltd.

Appendix¶

These fns are written for Dyalog APL, but will translate without trouble into an ISO standard APL (e.g. I-APL), except for the ‘string-search’ function, ss. Dyalog APL has an auxiliary processor XUTILS for useful service functions, ss being one of them. If you don’t want to use it, a replacement ss is offered below. I-APL users will have to write their own which does not use Find (⍷). It’s easy if you limit yourself to 2-char args of: restrict. Contact the author in case of difficulty, from whom workspace DNAFING is available free of charge for Dyalog APL.

    ∇ secret
[1]  ⍝assigns sx at random to one of: s1 s2 s3
[2]   sx←⍎'s',⍕?3
[3]  ⍝⍝...optional partial sample...
[4]  ⍝⍝ sx←10↓¯15↓sx
    ∇

    ∇ z←z restrict str
[1]  ⍝restriction enzyme, splits after seq: str
[2]   z←ss z str(str,'*')
    ∇

    ∇ z←do z;i;w
[1]  ⍝analyse sample: z
[2]   w←⎕PW ⍝length of chromatogram
[3]  ⍝Apply the following restriction enzymes
[4]  ⍝(These put '*' after their target sequence)
[5]   z←z restrict'in'
[6]   z←z restrict'the'
[7]   z←z restrict'os'
[8]   z←z restrict'of'
[9]   z←z restrict'you'
[10] ⍝Now model the chopping of the string at each '*'...
[11]  i←(z='*')/⍳⍴z ⍝positions of '*'
[12]  i←i-0,¯1↓i     ⍝lengths of chopped strings
[13]  i←w⌊i          ⍝limit i to max length of strip
[14]  z←w⍴'.'        ⍝the fresh chromatogram strip
[15]  z[i]←'□'       ⍝add the dark bands
    ∇

    ∇ z←ss u;x;y;v
[1]  ⍝string rearch/replace (c/f Dyadic XUTILS auxproc)
[2]   z x y←3↑u                    ⍝string,target,replacement
[3]   →0↓⍨1∊v←x⍷z                  ⍝quit if target is absent
[4]   v←¯1+v⍳1                     ⍝displacement to target
[5]   z←(v↑z),y,ss((v+⍴x)↓z)x y ⍝patch in the replacement
    ∇

    ∇ go
[1]   secret
[2]   'scene of crime...'
[3]   do sx
[4]   'suspect s1 vs sx...'
[5]   do s1 ⋄ do sx
[6]   'suspect s2 vs sx...'
[7]   do s2 ⋄ do sx
[8]   'suspect s3 vs sx...'
[9]   do s3 ⋄ do sx
    ∇