Genesis Machines by Martyn Amos

Author:Martyn Amos
Language: eng
Format: epub
Publisher: Atlantic Books
Published: 2014-02-23T16:00:00+00:00

Figure 5.1: Lipton’s graph representation for a three-bit binary string

Each node has two edges emanating from it, labelled either 1 or 0 (the edges leading out of node C lead to a ‘dummy’ node, which just acts like a railway buffer to end the paths). Any three-bit string can be represented by a path built by taking one of the two possible paths at each node, the value of each bit being defined by the label of the edge that is taken at each step. For example, if we only ever take the ‘top’ path at each branch, we encode the string 111, and if we only ever take the ‘bottom’ path, we end up with 000. A path that goes ‘top, bottom, top’ encodes the string 101, ‘top, top, bottom’ encodes 110, and so on.

The beauty of this encoding is that, just like Adleman’s approach, you only have to generate one sequence for each node (including the dummy node) and one for each edge (of course, you have trillions of copies of each sequence, but that’s not the same as having trillions of sequences!). If you get the Watson–Crick encoding right, random paths through the graph form spontaneously, just like in Adleman’s Hamiltonian Path experiment. Lipton didn’t actually perform any lab work – he was simply showing, in principle, how SAT might be solved using DNA – but his reasoning was sound. Using this approach, Lipton believed he could be confident of starting off with a tube containing all possible binary strings of a given length. Each strand in the tube would encode a possible assignment of values for a set of variables. The next stage was to weed out those assignments that did not result in satisfaction of the formula to be solved.

Because the general form of a SAT formula is a set of clauses combined with the AND operation, it follows that each clause must be satisfied: if evaluating only a single clause results in a value of 0, then the whole formula evaluates to 0, and the formula is not satisfied. Because the variables in each clause are separated by the OR operation, it only takes a single variable to take the value 1 for the whole clause to be satisfied. Lipton’s algorithm was very straightforward: he would proceed one clause at a time, looking at each component of it in turn, and keeping only the strands encoding a sequence of bits that satisfied that particular clause. The ‘winning’ strands would then go forward to the next clause, where the process would repeat, until there were no more clauses to examine. At the end of this procedure, if Lipton had any strands left in his tube, then he would know with certainty that the formula was satisfiable, since only strings satisfying every clause would have made it through the successive filters. It’s a bit like the TV show Pop Idol, where you start with a large pool of candidates. Some fail at the first hurdle (that

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.