A Tissue P System and a DNA Microfluidic Device for Solving the Shortest Common Superstring Problem

A Tissue P System and a DNA Microfluidic Device for Solving the Shortest Common Superstring Problem Lucas LEDESMA, Daniel MANRIQUE Alfonso RODR´ IGUEZ-PAT ´ ON, Andr´es SILVA Universidad Polit´ecnica de Madrid Facultad de Inform´atica Campus de Montegancedo s/n Boadilla del Monte – 28660 Madrid, Spain E-mail: [email protected] Abstract. This paper describes a tissue P system for solving the Shortest Common Superstring Problem in linear time. This tissue P system is well suited for parallel and distributed implementation using a microfluidic device working with DNA strands. The tP system is not based on the usual brute force generate/test technique applied in DNA computing, but builds the space solution gradually. The possible solutions/superstrings are build step by step through the parallel distributed combination of strings using the overlapping concatenation operation. Moreover, the DNA microfluidic device solves the problem autonomously, without the need of external control or manipulation. 1 Introduction A microfluidic device, microflow reactor or, alternatively, “lab-on-a-chip” (LOC) are different names of micro devices composed basically of microchannels and microchambers. These are passive fluidic elements, formed in the planar layer of a chip substrate, which serve only to confine liquids to small cavities. Interconnection of channels allows the formation of networks along which liquids can be transported from one location of the device to another, where controlled biochemical reactions take place in a shorter time and more accurately than in conventional laboratories. There are also 3D microfluidic systems with a limited number of layers. See [18, 16] for an in-depth study of microflow devices. The process of miniaturization and automation in analytical chemistry was an issue first addressed in the early 1980s, but the design (year 1992) of the device called “Capillary electrophoresis on a chip” [10] was the first important miniaturized chemical analysis system. Though still in its infancy, the interest in this technology has grown explosively over the last few years. Microelectromechanical (MEMS) technologies are now being widely applied to microflow devices to fabricate microchannels in different substrate materials, integrate electrical function into microfluidic devices, and develop valves, pumps, and sensors. A thorough review of many different microfluidic devices for nucleic acid analysis (for example, chemical amplification, hybridization, separation, and detection) is presented in [16]. 281 These microfluidic devices can implement a dataflow-like architecture for processing DNA (see [6] and [12]) and could be a good support for the distributed biomolecular computing model called tissue P systems (or tP systems for short) [11]. The underlying computational structure of tP systems are graphs or networks of connected processors that could easily be translated to microchambers (cells or processors) connected with microchannels. There are several previous works on DNA computing using microfluidic systems [6, 12, 4, 8, 9]. One [8] describes the design of a linear time DNA algorithm for the Hamiltonian Path Problem (HPP) suited for parallel implementation using a microfluidic system (this bioalgorithm shares some features with the algorithm for the Shortest Common Superstring Problem presented in this paper). This algorithm [8] builds the space solution gradually. The possible solutions/paths are built step by step by exploring the graph according to a breadth-first search so that only the paths that represent permutations of the set of vertices, and which, therefore, do not have repeated vertices (a vertex is only added to a path if this vertex is not already present) are extended. This simple distributed DNA algorithm has only two operations: concatenation (append) and sequence separation (filter). The HPP is resolved autonomously by the system, without the need for external control or manipulation. In another paper, Gehani and Reif [6] study the potential of biomolecular microflow computation, describe methods to efficiently route strands between chambers, and determine theoretical lower bounds on the quantities of DNA and the time needed to solve a problem in the microflow biomolecular model. Two other works [12, 4] solve the Maximum Clique Problem with microfluidic devices. This is an NP-complete problem. McCaskill [12] takes a brute-force approach codifying every possible subgraph in a DNA strand. The algorithm uses the so-called Selection Transfer Modules (STM) to retain all possible cliques of the graph. The second step of McCaskill’s algorithm is a sorting procedure to determine the maximum clique. By contrast, Chiu et al. [4] describes a novel approach that uses neither DNA strands nor selection procedures. Subgraphs and edges of the graph are hard codified with wells and reservoirs, respectively, connected by channels and containing fluorescent beads. The readout is a measure of the fluorescence intensities associated with each subgraph. The weakness of this latter approach is an exponential increase in the hardware needed with the number of vertices of the graph. Finally, Livstone and Landweber [9] propose the application of microreactors to implement Boolean functions AND and OR (connecting microreactors in series and in parallel) but without finding a possible implementation for the NOT function. 1.1 The Problem The problem chosen for our work is the Shortest Common Superstring Problem (SCSP). The input for this problem is a finite set of nstrings xiand an integer K. The output of the problem is “yes”, if there exists a superstring of length at most Kand “no” otherwise. A superstring over the given set is a string that contains all the strings in the set as substrings (a formal definition of the problem is given later in section 2). There are several reasons for the choice of the SCSP. First, the problem is NP-complete [5]. This means that large instances of the SCSP cannot be solved efficiently by electronic computers because running time escalates exponentially as problem size grows. Second, being strong related to DNA sequencing methods like SBH (sequencing by hybridization), this problem is of biological interest. The aim of the SBH technique is to reconstruct the sequence of a long DNA strand from the knowledge of the sequence of its short overlapping 282 substrings or fragments. Microarray chips technology was first developed [3] for this purpose. The computational problem often used to model this process of DNA fragment assembly is SCSP. A more detailed information about the relation of SBH to SCSP is given in [1], and a novel and promising application of SBH to resequencing is described in [15]. Third, SCSP is also applied in data compression schemes. 2 The Shortest Common Superstring Problem In this section we give a formal definition of the problem. Input: Alphabet Σ, finite set S={x1, x2, . . . , xn},n≥1, of strings from Σ∗, and a positive integer K. Question: Is there a string w∈Σ∗with length |w| ≤ Ksuch that each string xi∈S, 1≤i≤n, is a substring of w, i.e., for all i, 1 ≤i≤n,w=uixivi, where ui,vi∈Σ∗? The problem remains NP-complete even if the cardinality of Σ is 2. 3 Previous Work The only previous solution to the Shortest Common Superstring Problem in the DNA computing field is [7]. This DNA algorithm follows a brute-force approach: Step 1. Encode all the strings {xi, x2, . . . , xn}of the set Sin DNA strands. Step 2. Generate all possible DNA strands wof length kbetween max{|xi|,1≤i≤n} and Kusing T, G, A residues only. Step 3. Let x1be a string of S. For the string population generated in Step 2, select only those strands that contain x1as a substring. From the newly obtained string population, select only those strings that contain x2∈Sas substring, etc. Repeat this step for each xi∈S, 1 ≤i≤n. Step 4. If, after step 3, there is any strand wremaining (which means that wcontains all xi∈S, 1≤i≤n, as substrings), say “yes”, otherwise say “no”. This algorithm builds Pk=K k=max{|xi|} 3kdifferent DNA strands encoding candidate solutions and then retains only those strings that contain all the xias substrings. For example, for a set S={x1, x2, . . . , xn}where max{|xi|} = 4 and for K= 25 we would need to generate 34+35+...+325 = 1.27×1012 DNA strands. And for the same set, if we choose K= 37, we would need to generate 34+ 35+. . . + 337 = 6.75 ×1017 DNA strands. This exponential increase in molecular resources places an obvious in practice upper limit on this approach. Remember that around 1018 DNA strands can be handled in a test tube. 4 A Tissue P system for the SCSP 4.1 Overlapping Concatenation Before presenting the tP system, we explain the notation used in this paper. Given two strings xand yin Σ∗, the overlapping concatenation between them, denoted by x¯y, will be described as follows: 283 x¯y=   x, if x=x0 1yx0 2, where x0 1and x0 2∈Σ∗, y, if y=y0 1xy0 2, where y0 1and y0 2∈Σ∗, x0uy0,where x=x0u,y=uy0and |u|is the longest overlap. From the above definition it follows that: for every x,x¯x=xand for every x,y, |x¯y|=|x|+|y|−|u|=|x·y|−|u|. If u=λ, then the overlapping concatenation is the usual concatenation: x¯y=x·y. •Example 1: Given Σ1={a, b, c, d, r}, and the strings x=abraca,y=cadabra ∈Σ∗ 1, x¯y=x0uy0=abracadabra, where x0=abra,y0=dabra andu=ca. •Example 2: Given Σ1={a, b, c, d, r}, and the strings x=abracadabra,y=acada ∈ Σ∗ 1,x¯y=x0 1yx0 2=abracadabra, where x0 1=abr,x0 2=bra. The operation ¯is extended naturally to the languages L1and L2: L1¯L2={x¯y|x∈L1∧y∈L2}. The overlapping concatenation operation described above models the parallel DNA overlapping assembly operation. This operation has been used previously in DNA computing (see [13]) to generate DNA data pools and in combinatorial chemistry (see [17]). Here it will be used to implement the proposed tP system using DNA microfluidic devices. 4.2 Tissue P Systems We briefly and informally review the bioinspired computational model called tP system. A detailed description is given in [11] and in [14]. A tP system is a network of finite automata-like processors, dealing with multisets of symbols, according to local states (available in a finite number for each “cell”), communicating through these symbols, along channels (“axons”) specified in advance. Each cell has a state from a given finite set and can process multisets of objects, represented by symbols of a given alphabet. The standard evolution rules are in the form sM →s0M0, where s, s0are states and M, M0are multisets of symbols. We can apply such a rule to only one occurrence of M(that is, in a sequential minimal way), or to all possible occurrences of M(a parallel way), or, moreover, we can apply a maximal package of rules of the form sMi→s0M0 i,1≤i≤k, that is, involving the same states s, s0, which can be applied to the current multiset (the maximal mode). Some of the elements of M0may be marked with the indication “go”, and this means that they have to immediately leave the cell and pass to the cells to which there are direct links through synapses. This communication (transfer of symbol-objects) can be done in a replicative manner (the same symbol is sent to all adjacent cells), or in a non-replicative manner; in the second case, we can send all the symbols to just one adjacent cell, or we can distribute them non-deterministically. One way to use such a computing device is to start from a given initial configuration and to let the system proceed until it reaches a halting configuration and to associate a result with this configuration. A halting computation is a computation that ends in a configuration where no rule in any cell can be used. In these generative tP systems the output will be defined by sending symbols out of the system. To this end, one cell will be designated as the output cell. 284 Within this model, we present here a tP system (working in a maximal mode and using the replicative communication mode) to solve the Shortest Common Superstring Problem. As we already mentioned, this problem involves determining whether or not, for a given set of strings S={x1, x2, . . . , xn}from Σ∗and a positive integer K, there is a string wof length |w| ≤ Kcontaining all the strings in Sas substrings. Our tP system differs from the general version of a tP system as to two features: (1) our tP system deals with strings (not symbols) that evolve through the ¯operation, and (2) our tP system does not have a single output cell (strings can be sent out from every cell of our tP system). Not only does the tP system presented solves the SCSP but it can also be used to find the minimum value of Kfor which the problem has an “yes” solution. This tP system has one cell σiassociated with each string xiof Sand the cells are fully connected. Starting from each xi, overlapping concatenations of the strings in Sgrow simultaneously in all cells, and in parallel. Strings z¯xiare produced in each cell σiand are communicated to the other cells. Strings zare the inputs of the cells and xiare the string associated with each cell σi. It is easy to see that, after n−1 steps, the strings built by the system contain as substrings the xi, for all 1 ≤i≤n. Moreover, after n−1 steps, the system has built n! superstrings zwhere: 1. Each xi, 1 ≤n≤n, appears only once in each z, 2. the n! superstrings zcorrespond to the n! parallel combinations of xi∈Susing the overlapping concatenation ¯, 3. each superstring zis sent out of the system only if its length is |z| ≤ K. Formally, the tP system proposed to solve the Shortest Common Superstring Problem for a set Sof nstrings xi∈Σ∗and a value Kis Π = (O, σ1, . . . , σn, syn), where: 1. O={[z;l]|z∈Σ∗,1≤l≤n} 2. syn ={(i, j)∈ {1,2, . . . , n}×{1,2, . . . , n} | i6=j}is the set of channels among cells; each cell is connected to every other cells. 3. σ1, σ2, . . . , σnare cells of form σi= ({s}, s, [xi;1], Pi) for each i= 1,2, . . . , n Pi:s[z;l]→s[z¯xi;l+ 1]go such that z∈Σ∗,|z|xi= 0,1≤l≤n−2, s[z, n −1] →s[z¯xi;n]out, if |z¯xi| ≤ K. The candidate superstrings zgrow simultaneously in all cells of Π, because of the max mode of using the rules (each cell has only one state, hence all rules can be used at the same time). Moreover, the rule s[z, n −1] →s[z¯xi;n]out, if |z¯xi| ≤ K, can only work after n−2 steps and only the superstrings of length less or equal to Kare sent out of the system at step n−1. It then suffices to look at the tP system after step n−1, where, if any string is sent out of the system, then the answer to the problem will be “yes”; “no” otherwise. The shortest common superstrings will be the strings sent out of the system. Furthermore, the system can be executed for different values of Kbetween max{|xi|} and P|xi|, 1 ≤i≤n, to find the minimum Kfor which there exists a superstring over S. 285 5 A DNA Algorithm Using a Microfluidic Device The tP system described above can be easily translated to a parallel and distributed DNA algorithm to be implemented in a microfluidic system. Remember that we have a set of strings S={x1, x2, . . . , xn}from Σ∗and an integer K, and we want to determine whether or not there is a superstring wwith length |w| ≤ K. Here we assume without loss of generality that no string xi∈Sis a substring of any other xj∈S. Our algorithm finds the solution to the SCSP in linear time. First, we describe the overall operation of the algorithm. The proposed algorithm constructs the n! superstrings of Scorresponding to the n! combinations of xi∈Susing the overlapping concatenation. For this purpose, the hardware of the microfluidic system consists of nnodes ni. In each node ni, in each time unit, the overlapping concatenation of the string xiassociated with the node niand the input string zis obtained, z¯xi, and then communicated to the others nodes of the microsystem. Each node niconsists of three chambers Ei,Ci, and Fi. Chamber Eiis used to extend the input strings zwhen there is overlapping between zand the xiassociated to the node ni. Chamber Ciis used to append the string xito the input string zwhen no overlapping is present. And the last chamber Fiis used: (1) to eliminate the input strings zthat have already substring xiand (2) to route the input strings zto the corresponding concatenation Cior extension Eichamber. Thus, in each node, in each step, the string associated with that node is combined with the input string using the overlapping concatenation and then communicated to the other nodes. In step n−1, the system has assembled n! superstrings corresponding to the n! possible combinations of xidescribed above. We now present the algorithm: •Coding: Each string xiis encoded with a different short single DNA strand. Each of these single strands must be carefully selected to avoid mismatch hybridizations throughout the bioalgorithm run (see [2] for DNA strands design criteria). •In parallel, in (n−1) steps, starting from each string in Sthe algorithm grows n! superstrings. The xi∈Sare combined using the overlapping concatenation ¯in all possible ways (that is, the n! ways corresponding to the n! permutations of n). •Time t=n. Read the outputs of the system. At time t=n, the n! strings assembled by the algorithm will be superstrings. Then it merely remains to choose the shortest strings and determine whether its length is less than or equal to K, in which case the answer to the problem is “yes”, otherwise the answer is “no”. Now we propose a microfluidic system to implement the DNA algorithm. The hardware of our system for a set Swith nstrings is composed of 3n+1 chambers: nfiltering chambers Fi,nappend/concatenation chambers Ci,nextension chambers Ei, and one chamber L to determine the length of the superstrings. Chamber Fi. Input: DNA strands zfrom chambers Cjand Ejwith 1 ≤i, j ≤n and j6=i. Function: Separate the input strands into three groups: (1) the first group is composed of those input strands that do not hybridize to the strand associated with xi (the strand associated with xiis the complementary strand of the strand associated with xi); (2) the second group is composed of those input strands that hybridize partially on 286 the left extreme of the strand associated with xi; (3) and the third group is composed of those input strands that fully hybridize to the strand associated with xi. Only the strands in the first two groups (1) and (2) will be valid outputs of the chamber. Those outputs will be called output1and output2respectively. The third group of strands is discarded or removed. Chambers Ci. Input: DNA strands zfrom the output1of Fi. Function: Appends the substrand associated with xito the right of each strand zin its input. Output: z¯xi=z·xi (remember that, in this case, the ¯operation is the usual concatenation, because there is no overlapping between zand xi). Chambers Ei. Input: DNA strands zfrom the output2of Fi. Function: Extends every strand zin its input to produce z¯xi, using the parallel overlapping assembly operation with xias extension pattern. Output: z¯xi. Chamber L. Inputs: DNA strands zrepresenting superstrings of Ssent out of the Ci and Eichambers in step n−1. Function: determine the length of the different z. Pattern of connectivity (layout). The output1of each chamber Fiis connected to the input of the associated Ei. The output2of each chamber Fiis connected to the input of the associated Ci. For every 1 ≤i, j ≤nand i6=j, there is a channel from the outputs of chambers Ciand Eito the input of every chamber Fj; and there is a pump that forces the flow of the liquid from Ciand Eito Fj. For simplicity’s sake, we group the chambers by their subindexes in nodes. Thus, nodeiwill be composed of chambers Fi,Ci, and Ei. The input of nodeiwill be the input of chamber Fiand the output of nodeiwill be the union of the outputs of Eiand Ci. Implementation. It is beyond the scope of this paper to give more details of the possible implementation of these microsystems. We merely indicate that the filtering, append, and extend operations are widely used in DNA computing and a detailed description of the microfluidic devices is given in [6, 16]. Working (dynamics) of the system. We assume that the operations of nodei(filter and extension or append) take one time unit. •Step 0: (t= 0) (pre-loading). –Put enough copies of the strand associated with xiinto each chamber Fi. –Put enough copies of the strand associated with xi, and enough copies of the auxiliary strands and enzymes to allow concatenation into each chamber Ci. –Put enough copies of the strand associated with xiand enough enzymes and nucleotides to allow the extension into each chamber Ei. •Steps 1 to (n−1): (from t= 1 to t= (n−1)). –Computations: For all 1 ≤i≤n, in parallel, a filtering operation in all Fi, an append operation in all Ci, and an extension operation in all Eiare performed in each step. –Movement (pumping) of strands from step tto step t+ 1. Input(Fj(t+1) ) = [ i (Output(Ci(t))∪Output(Ei(t))) 287 for all 1 ≤i, j ≤n, and i6=j. The inlet of chamber Fjin time t+ 1 is the union of the outlets of chambers Ciand Eiin time tfor all 1 ≤i, j ≤n, and i6=j. Remember that we can group the chambers in nodes, thus Input(nodej(t+1) ) = [ i Output(nodei(t)) for all 1 ≤i, j ≤n, and i6=j. The inlet of the nodejin time t+ 1 is the union of the outlets of nodes nodeiin time t. •Step t=n(readout): After step (n−1) collects the strands in the output of chambers Ciand Eiand determines their lengths. The length of the shortest output strands determines the minimum value of Kfor which there exists a superstring of S. The lengths of the strands can be calculated by gel electrophoresis with chamber L. 5.1 Example We give an example of the execution of the algorithm for a set with four strings S={x1= ABRAC, x2=ADABR, x3=DABRA, x4=RACAD}constructed from the alphabet Σ = {A, B, R, C, D}. Table 1 shows the outputs of each node in each step. After time t=3=n−1, the strands in the output of all nodes have to be collected. These strands codify the 24 superstrings corresponding to the 24 = 4! possible ways of combining through overlapping concatenation the original xistrings. The numbers that appear in front of each string are shown to ease the understanding how each string is assembled. These numbers show the order of combination of the xi; for example, in time t= 2, the output of node1 contains the string 321|DABRADABRAC=x3¯x2¯x1=DABRA ¯ADABR ¯ABRAC. The last chamber of our microfluidic device is used to determine the length of the strands using gel electrophoresis. The strings in bold are the shortest common superstring, and their length is the minimum Kfor which there exists a superstring of S. In this example K= 9 is the minimum value of Kfor which the SCSP has a “yes” solution. The number of DNA strands encoding candidate solutions constructed with our algorithm is n! = 4! = 24. To solve this example using the algorithm proposed in [7] approximately k=K=20 X k=max{|xi|}=5 3k≈5.2×1010 candidate solutions (K=|ABRAC|+|ADABR|+|DABRA|+|RACAD|= 20) would need to be generated. 6 Final Remarks It was shown in [11] that tP systems are a useful computational model for solving complex graph-related problems. This paper presents a new application of tP systems outside the graph-related problem domain with interest in the field of genomics and in data compression. The new tP system and its implementation with a DNA microfluidic system solves in linear time the Shortest Common Superstring Problem (SCSP). The algorithm for the SCSP runs autonomously, in linear time, in parallel, and without manual external intervention. There is only one previous work in the DNA computing field solving the SCSP problem [7]. Our algorithm does not follow the Adleman’s style of 288 t= 0 t= 1 t= 2 t= 3 node11|ABRAC 21|ADABRAC 321|DABRADABRAC 4321|RACADABRAC 31|DABRAC 421|RACADADABRAC 3421|DABRACADABR 41|RACADABRAC 231|ADABRAC 4231|RACADADABRAC 431|RACADABRAC 2431|ADABRACAD 241|ADABRACAD 3241|DABRADABRACAD 341|DABRACAD 2341|ADABRACAD node22|ADABR 12|ABRACADABR 312|DABRACADABR 4312|RACADABRAC 32|DABRADABR 412|RACADABRAC 3412|DABRACADABR 42|RACADADABR 132|ABRACDABRADABR 4132|RACADABRAC 432|RACADABRA 1423|ABRACADABRA 142|ABRACADABR 3142|DABRACADABR 342|DABRACADABR 1342|ABRACDABRACADABR node33|DABRA 13|ABRACDABRA 213|ADABRAC 4213|RACADADABRAC 23|ADABRA 413|RACADABRAC 2413|ADABRACAD 43|RACADABRA 123|ABRACADABRA 4123|RACADABRAC 423|RACADADABRA 1423|ABRACADABRA 143|ABRACADABRA 2143|ADABRACAD 243|ADABRACAD 1243|ABRACADABRA node44|RACAD 14|ABRACAD 214|ADABRACAD 3214|DABRADABRACAD 24|ADABRACAD 314|DABRACAD 2314|ADABRACAD 34|DABRACAD 124|ABRACADABR 3124|DABRACADABR 324|DABRADABRACAD 1324|ABRACDABRADABRACAD 134|ABRACDABRACAD 2134|ADABRACAD 234|ADABRACAD 1234|ABRACADABRA Table 1: Running of the algorithm. Output of the nodes at each step. The numbers that appear in front of each string are shown to ease the understanding of how each string is constructed. These numbers show the order of combination of the xi. The strings in time t= 3 = n−1 are the 24 = n! = 4! superstrings generated by the system. Strings in bold are the shortest common superstrings, and their minimum length (K= 9) is the minimum value of Kfor which there exists a superstring of S. 289