And we are back on the slow crawl toward eventually explaining what I do, out here in the darker recesses of my lab tucked in the remote Kansai countryside.

Aside from breeding deadly mutant monkeys to serve in my army of evil minions when I kickstart the world-domination part of my plot, that is.

Before I go any further, let me remind the casual reader that: 1) it is most likely nice and sunny out there where you live and you would be considerably better off looking at squirrels running through the trees 2) if you have even the slightest inkling of formal mathematical/computer science training, you will be better served foregoing this edulcorated version in favour of one of the 10 million tutorials and entries on bioinformatics available throughout the internets (Wikipedia being a good place to start). The entry written henceforth is geared at some hypothetical grandparents who would care to know what the fuss with modern Science is all about (for instance mine, were they not already perfectly content in the sole knowledge that the good Lord has put all these tiny amino-acids together in the best possible way of all worlds and that modern genetics is the work of the Devil¹I know: one is not supposed to capitalise the name of God’s evil nemesis, but I am going on the assumption that Satan is a vindictive bastard and one can never be too prudent in courting the good graces of major players of the afterworld.).

In last month’s episode, we laboriously learnt that Biology abounds with really, really, tough problems. Two major points were:

1. For all practical matters, NP-Complete problems are all in the same bag: finding a way to solve one efficiently would mean you can solve any other in roughly the same order of time.

2. Once you have proved that a problem is NP-Complete, trying to find an exact solution for a real-life set of data, is about as meaningful as trying to take down the Everest with a toothpick. There are however plenty of ways to find an approximate solution. Proving NP-Completeness is your cue to start looking for approximation algorithms; and thus the fun begins.

Today, instead of going straight onto the myriad fun ways in which mathematicians solve biology problems, and which one of those I am actually connected to, another digression and an illustration everyone has heard of: genome sequencing.

Full genome sequencing (mapping the entire DNA of a given organism) is one of the earliest application of modern bioinformatics techniques, a seminal example: it starts off as a rather straightforward bio-chemistry problem, soon runs into pesky matters of size, complexity and intractability, goes through a difficult phase of alcohol and substance abuse, but is ultimately saved by the power of Love and Mathematics.

Before I go into the gory details, allow me to dissipate a common misconception about DNA sequencing: it is nowhere as easy as you might have been led to believe by your TV (most people’s preferred source of Science™ facts). Hearing of “DNA tests”, “DNA crime database” and other everyday life DNA-related techniques might make it sound like sequencing is as easy as sending your saliva swab to the lab and waiting a couple days for the results. In reality, despite serious advances, actual full genome sequencing is still a multi-year, multi-million-dollar affair. When people talk about DNA in a forensics or medical context, they are usually looking at a single base nucleotide, located at a precise location on one gene, out of the entire genome. Even cases that require a larger sample of such observations (e.g. DNA matching, when it actually uses sequencing altogether) are still somewhere in the lower hundreds (if that). That’s a mere 100 bases to look at, against 100+ million for the first organism fully sequenced, 10 years ago (make that 3 billions for humans). Quite a difference in scale. And, of course, this is one of those problems where solving twice the size requires much more than twice the time (hopefully by now, this does not surprise you, otherwise you might want to go back and read episode 1 again).

OK, let’s start:

The Easy Part

Long before full-genome sequencing arose, there have been many efficient methods to map small fragments of DNA. How small depends a lot on how efficient, how fast and how reliable you want the result, but 100 bases is a good figure to go with (could be 100 or 1000: it would not matter much when compared to aforementioned billions bases of the human genome). The methods used to do small-scale sequencing are quite nifty, but since they merely rely on boring²just kidding, fellow biologist friends: keep looking after those test tubes and churning out my data. kthxbye. bio-chemistry stuff, I will let you google around (Wikipedia’s entry on the topic is not the greatest introduction, for once). For our sake, let’s just say we have biological tools that can accurately map segments of DNA of 100 bases (or smaller) in a fairly short time with near-perfect accuracy.

Other magical tools that we have at our disposal in our bio-chemistry toolbox allow us to somewhat painlessly:

1. replicate a sequence (of any length) an arbitrary number of times.

2. cut sequences in smaller bits at arbitrary positions: usually upon encountering a specific pattern in the sequence and with a certain frequency rate (e.g.: upon encountering the pattern ‘CCCGGG’ anywhere in the sequence, the cut will occur 1 out of 6 times).

3. work on a subsequence at a specific position (as if it was cut from the rest): provided you have an exact pattern where you want to do it (and the pattern is long enough to be unique in the sequence), you can isolate a subsequence from the rest with absolute precision and accuracy. However, engineering such an artificial cut is infinitely more complex, long and costly as using some of the “ready-made” cutters of 2.

The same with more science and less words, you ask? Sure, here you go: DNA primers, DNA polymerase, PCR, restriction enzymes, kangaroos³Have fun with your friends: can you spot the famous Australian marsupial among these terms related to DNA engineering?.

For the sake of keeping things simple (ha!) we will blatantly ignore the fact that DNA is not a single strand, but two complementary sequences tied together that need to be periodically pried apart or rebuilt during these operations. In the end, it does not matter much to the problem at hand.

Equipped with such tools, how should we go about processing entire chromosomes (usually north of 10k bases for simple organisms, 50 million for humans)?

The Straightforward Method (aka The Doomed Approach)

“Primer walking” is a (comparatively) simple method that more or less consists of focussing on segments small-enough to fit our small-scale sequencing method: start at a given position (see tool 3. above), map a few hundred bases, use the chunk just mapped to find the next starting position, lather, rinse, repeat.

There are two major problems with this method: As mentioned, “starting at a specific position” on a sequence is a very ad hoc and therefore costly (in money, in time…) operation. That operation furthermore requires knowing where to start, which means having processed the previous segment (so we can use the end of this segment as the pattern to start at in the following step).

The entire process therefore requires sequentially executing a series of operations, each of which requires a certain time. Surprisingly no NP-Completeness or exponentials involved here: only a very, very long task with no way to parallelize, which is only theoretically better. In practice, this makes this method viable (albeit slow and costly) for sequences of up to 10,000 or so bases.

On longer sequences, and particularly on our friendly multi-billion genomes, that would be a Fail.

The Smart Way (aka The One That Gives Headaches)

From the above, it seems obvious the only way to stand a chance at decoding entire genomes in less than a lifetime is to tackle many small segments, possibly all of them, at the same time. And this is exactly what shotgun sequencing does: after making a good number of copies of the original sequence, we sic a bunch of ready-made sequence cutters on them. The resulting mixture is a horrible mess of small fragments, that are small enough to be each sequenced easily. Which is great, except you then have no idea how to put them back together so as to get the bigger picture.

Not clear? Need another silly analogy? Sure:

Imagine you have a (very very long) text printed on a piece of paper: make a dozen photocopies and leave them in a room with your 5-year-old nephew and a good pair of scissors (arranging the pages in such a way that each is cut separately, in its own unique way). Put all the resulting confetti in a bag, shake a few times.

Now put the original text back together. Go ahead, I’ll wait.

Funny enough, this is near-exactly what DNA sequencing entails: once the first phase of sequencing is done, you are given a large bag of short strings (long sequences of ‘A’, ‘G’, ‘T’ and ‘C’ instead of common words in our analogy, but the same for every other purpose). You are looking for the text that is made of these strings in a specific order (and repeated over, as many times as there were initial copies). An “easier” problem is to find any text on which you could fit each little fragments (with lots of overlap, since there are many copies, each cut a different way) without worrying too much about whether this text really is your original. In practice, to get the real solution, all you have to do is find the shortest such text⁴the only reason this is not 100% true is the pesky problem of highly repetitive sequences. Something unlikely to arise in a real book, but very common in some DNA.: the one where you have no “superfluous” bits of text (not covered by any fragment) and as much overlap as possible (ideally in such a way that each bit of text is covered exactly as many times as there were original copies).

This problem is known as the shortest common superstring. And guess what: remember that little list I mentioned last week? Yea, bummer.

Given a candidate, merely verifying whether you have found the true Shortest Common Superstring is an NP-Complete problem. Finding that string from scratch, belongs to an even harder class of problems known as “NP-Hard” (where, as the name lets on, real badass NP problem kids hang out). Given the size of your data (millions of tiny fragments), finding an exact solution is obviously not gonna happen in this lifetime. Neatly enough, solving this problem turns out to be exactly the same as solving a particular brand of Traveling Salesman Problem (remember?). But as I mentioned last week: where standard algorithm fail and exact solution cannot be found, it is usually still possible to find a decent approximation in a fraction of the time. Sometimes this solution even turns out to be the exact solution, or so close that it doesn’t matter. This is the case here.

And excited as I am sure you were all, to jump into the actual mathematics of solving this particular problem, a sense of human decency and the already astronomical word count on this entry conjointly force me to skip to the end and suggest that the morbidly obsessed bravest among you peruse their local Google to look for some fascinating readings on reducing Shortest Common Superstring to Asymmetric Traveling Salesman Problem and/or finding approximation algorithms for the Shortest Common Superstring problem.

One of the trick behind Shotgun Sequencing, beside the actual approximation algorithm used to rebuild the original sequence, is the clever use of statistical redundancy to reach a guaranteed level of accuracy. That’s how we are able to say with certainty that the accuracy for the current Human Genome project is “no more than 1 error every 100,000 bases on average” (which sounds an awful lot better than “fuck if we know, but we dang sure hope it’s enough to tell it apart from them monkey DNA”).

The thankfully brief conclusion

And there we are, I have exposed, in nearly less time than it takes to kill a grizzly with a feather⁵Pro tip: go for that spot under their foot, grizzlies are extremely ticklish there., how Mathematics and Algorithmic can save the day in Genetics and help ensure that we will all have a bright future made of beautiful blond, three-eyed babies.

Of course, given that Shotgun Sequencing in its earliest incarnation, dates back about 40 years, there is very little left to be done for young upcoming bioinformaticians in this particular direction. And none of my work has anything to do with common sequencing problems.

But next week month soon, I will maybe talk of more recent challenges in bioinformatics, perhaps even some of mine!⁶… in part 205 to 300 of this entrancing 1400-part series!