Maximum Search Using P Systems

Maximum Search Using P Systems Federico FONTANA, Giuditta FRANCO University of Verona Department of Computer Science strada Le Grazie, 14 37134 Verona, Italy E-mail: {fontana,franco}@sci.univr.it Abstract. Several algorithms of maximum search are investigated and evaluated in different types of P systems, namely using priorities, multiple nested membranes and linked transport. The proposed solutions are expected to find application in a wide range of problems. In particular, the authors are currently working on modeling an algorithm for DNA sequence alignment using P systems. 1 Introduction The capability of P systems to execute in polynomial time programs that, otherwise, need exponential time when executed using traditional computing resources, makes these systems especially eligible for dealing with NP-complete problems [10, 9]. This is the case of the algorithms for aligning sequences of symbols. Such algorithms must deal with the pair and multiple sequence alignment problem [4]. At an abstract level they can be seen as procedures for finding the optimal alignment between a pair or a multiple set of strings [7]. Though, at an application level, they have found major diffusion among the most popular biological database search programs [8, 2]. In principle it is easy to figure out the best alignment: it is sufficient to construct and then score all possible gapped alignments between two (or more) DNA sequences. This corresponds to generate the entire tree of the alignments, then to label every leaf with the related score: the higher the score, the better the alignment [5]. The procedure of sequence alignment becomes much more parsimonious, if the optimality is dynamically checked out step by step. Instead of generating all possible gapped alignments between two or more sequences and, finally, determining the best one, the dynamic approach asks to evaluate at every time step some (partial) highest scoring alignments, possibly leading to the (final) optimal score: this approach, corresponding to pruning the tree of the alignments, dramatically reduces the number of computations needed to achieve the final, optimal gapped alignment. P systems can be in principle accommodated for generating the whole tree of the alignments in polynomial time. Though, exploiting the parsimony coming from the dynamic programming strategy results in a more efficient use of the resources provided by the membranes. The key point of this strategy consists in computing the maximum score between several partial alignments competing to form the final optimal one: only the 152 xxxxxxxx 12345678 1 2 3 4 5 6 7 Figure 1: “Horizontal” and “vertical” approach to the maximum search. highest-scoring of them will be eligible to be included in the final alignment. A similar problem has been dealt with in the context of rectangular pictures tiling using P systems [3]. From the point of view of membrane computing, we can model this stage of the procedure as a search for the greatest multiplicity of Nsymbols. Literature concerned with a similar issue includes the modeling of sorting algorithms [1]. This paper, then, focuses on the problem of maximum search using membrane systems, and leaves the modeling of the rest of the DNA sequence alignment procedure to a forthcoming research. 2 Non Deterministic, Maximally Parallel Maximum Search It is known that the maximum search between Nnumbers can be easily carried out in linear time on a serial machine, by performing successive comparisons of value pairs [4]. If multiple (parallel) computing resources come into play, then at every computation step we can compare more than one pair simultaneously–though, in principle our processing unit might be able to test triples or n-uples. Whatever the number of processing units and their capability to perform multiple tests simultaneously, at the end of every computation step we will have several relative maxima at hand. At this point the maximum must be searched again on a reduced set of numbers, until reducing this set to a single value. We call this kind of approach to the problem horizontal. Alternatively, we should be able to count at least up to the maximum: during this counting up, we should evaluate the input values (possibly all of them at the same time) just until they become smaller or equal than the value counted out. This value (i.e., the maximum) should finally be sent to the output. We call this second kind of approach to the problem vertical. We can cast the above considerations in the framework of a P system containing N symbols, that selects the symbol having the largest number of occurrences and sends out this number (thus solving a problem of maximum search) possibly along with the symbol itself (thus solving, in addition, a problem of maximum value search). The horizontal approach calls for a procedure that works on the symbols, whereas the vertical approach calls for a procedure working on the symbol occurrences (refer to figure 1). We will model both the horizontal and vertical maximum search, and discuss the efficiency and complexity of the procedure under several types of membrane systems, 153 namely using multiple priorities on rules, multiple membranes, and linked transport. In the following, we will indicate with |x|the number of copies of x. 3 Maximum Search with Priority In the most simple case we can determine the maximum between two symbols x1and x2, each one present in the skin membrane with its own number of copies, by considering the following construct [11]: V={x1, x2, x0}, T ={x0}, w =x1x2, R={r1:x1x2→x0 out, r2:x1→x0 out, x2→x0 out}, ρ ={r1> r2} It is straightforward to see that the number of copies of symbols x0coming out from this simple membrane system is the maximum between |x1|and |x2|, but the information on the maximum value is lost. To preserve the information on the maximum value it is sufficient to change the rules having priority r2in x1→x10 out, x2→x20 out, after substitution of x0with x0 1, x0 2in Vand T. After this change the maximum is figured out as |x0 1|+|x0 2|and the presence of x0 2in the environment signals that it is |x0 2|>|x0 1|. In general, we can extend the same reasoning to Nsymbols by repeatedly comparing pairs of symbols until the final one goes out of the skin membrane. For the sake of simplicity we can consider Nto be a power of 2—it is anyway possible to add “ghost” symbols in one copy in the membrane to achieve this condition, the maximum being unaffected by this operation. The corresponding construct is the following one: V={x1, x2, . . . , xN, x0 1, x0 2, . . . , x0 N/2, x00 1, x00 2, . . . , x00 N/4, . . . , x(log N)}, T={x(log N)}, w =x1x2. . . xN, R=                                                  r1:x1x2→x0 1, x3x4→x0 2, . . . xN−1xN→x0 N/2, r2:x1→x0 1, x3→x0 2, . . . xN−1→x0 N/2, x2→x0 1, x4→x0 2, . . . xN→x0 N/2, r0 1:x0 1x0 2→x00 1, x0 3x0 4→x00 2, . . . x0 N/2−1x0 N/2→x00 N/4, r0 2:x0 1→x00 1, x0 3→x00 2, . . . x0 N/2−1→x00 N/4, x0 2→x00 1, x0 4→x00 2, . . . x0 N/2→x00 N/4, · · · r(log N−1) 1:x(log N−1) 1x(log N−1) 2→x(log N) out , r(log N−1) 2:x(log N−1) 1→x(log N) out , x(log N−1) 2→x(log N) out                                                  ,(1) ρ={r1> r2> r0 1> r0 2> . . . > r(log N−1) 1> r(log N−1) 2} where log is the logarithm with basis 2. The system behaves as follows: rules having priority r1consume all the symbol pairs x1x2,x3x4and so on, that are initially present in the membrane, producing symbols 154 x0 1, x0 2, . . . , x0 N/2. At the following time step such rules cannot be applied, and rules with priority r2turn all the remaining initial symbols (actually, those which cannot take part in a couple) into symbols of type x0 i. At the third time step rules having priority r1and r2 cannot be applied any longer (all the initial symbols have disappeared), so the rules with priority r0 1are applied to the new pairs x0 1x0 2,x0 3x0 4and so on. Rules having priority r0 2are applied at the fourth time step to the symbols of type x0 ithat cannot be paired, and so on until the last symbol is sent out of the skin in a way that |x(log N)|= max{x1, x2, . . . , xN} The number of symbols in the multiset is halved every two time steps, after the application of the rules with priority r(i) 1and r(i) 2. Then, the proposed system computes the maximum in 2 log Ntime steps making use of N+N/2 + N/4 + . . . + 2 + 1 = 2N−1 symbols, (N/2 + N) + (N/4 + N/2) + . . . + (1 + 2) = (N−1) + (2N−2) = 3N−3 rules, and 2 log Npriorities. That is, the maximum search is computed in logarithmic time using one membrane with priorities. This system then requires a linear number of symbols and rules. We can save resources if we do not make use of symbols other than the initial ones. In this case we can maintain the correct evolution in the system by producing a different symbol from each pair. The new rules are contained in the following set: R=                                                        r1:x1x2→x1, x3x4→x3, . . . xN−1xN→xN−1, r2:x2→x1, x4→x3, . . . xN→xN−1, r0 1:x1x3→x1, x5x7→x5, . . . xN−3xN−1→xN−3, r0 2:x3→x1, x7→x5, . . . xN−1→xN−3, · · · r(i) 1:x1x2i+1 →x1,· · · xN−2i+1+1xN−2i+1 →xN−2i+1+1, r(i) 2:x2i+1 →x1,· · · xN−2i+1 →xN−2i+1+1, · · · r(log N−1) 1:x1xN/2+1 →x1out, r(log N−1) 2:xN/2+1 →x1out                                                        (2) using the same priority set ρseen in (1). Now we make use of Nsymbols and 2N−1 rules, again with 2 log Npriorities (and consequent computation steps). We now wonder whether increasing the parallelism in the comparisons improves the system performance or not. The answer is that it does not, as long as we have to compare every possible combination of symbols during the production of new symbols. To have an 155 idea of it, consider the case of three symbols to compare. In that case we can define the following construct: V={x1, x2, x3, x0}, T ={x0}, w =x1x2x3, R=   r1:x1x2x3→x0 out, r2:x1x2→x0 out, x2x3→x0 out, x1x3→x0 out, r3:x1→x0 out, x2→x0 out, x3→x0 out    ,(3) ρ={r1> r2> r3} From this it descends that if we have Nsymbols, with Nbeing a power of 3, then 3 log3N steps are needed to find the maximum. More in general, we will need KlogKNtime steps to maximize between Nsymbols using K-symbol parallel comparisons (again providing Nto be a power of K, eventually adding “ghost” symbols). The function KlogKNhas an absolute minimum in correspondence of K=e. In practice, simple and efficient implementations of the algorithm can be in principle realized by setting K= 2 or K= 3. It is interesting to calculate the figures of complexity in the case when one N-symbol comparison is performed by the system at once. This means that we have to consider all possible combinations of N, N −1, . . . , 2,1 symbols. In this case the maximum is searched in NlogNN=Nsteps, using N+ 1 symbols (or Nif we prefer to send out one of the initial symbols at our choice, hence avoiding the use of x0), provided the existence of N X i=1 µN i¶= 2N−1 (4) rules. On the other hand, N-symbol comparisons allow for a straightforward implementation of a maximum value search algorithm. In this case it is sufficient to substitute the lowest priority rules with the following ones: rN:x1→x1out, x2→x2out, . . . , xN→xN out in a way that the presence of the symbol xioutside the skin membrane signals that it has maximal numeracy, and the maximum is equal to |x0|+|xi|. If we want to account for the more general case of multiple maximum values then a more elaborate strategy must be implemented, for example by sending out at every computation, along with x0, additional symbols related to the tuples being processed during that computation. 4 Maximum Search with Multiple Membranes Similarly to what we have done with priorities we can define a construct analogous to (1) using the rules expressed by (2), this time using logKNnested membranes when K-symbol parallel comparison is implemented. In the case K= 2 we have the following construct (in an attempt to simplify the notation, we have labeled the membranes using a reverse order instead of increasing their numerical value while moving from the outside toward 156 the inside): V={x1, x2, . . . , xN}, T ={x1}, µ= [log N[log N−1. . . [2[1]1]2. . . ]log N−1]log N, w1=x1x2. . . xN, wi=λ , i = 2, . . . log N, Ri=   r1:x1x2i−1+1 →x1··· xN−2i+1xN−2i−1+1 →xN−2i+1 r2:x1→x1δ, ··· xN−2i+1 →xN−2i+1δ x2i−1+1 →x1δ, ··· xN−2i−1+1 →xN−2i+1δ    ,(5) i= 1,2, . . . , log N−1 Rlog N=   r1:x1xN/2+1 →x1out r2:x1→x1out xN/2+1 →x1out    , ρi={r1> r2}, i = 1,2, . . . , log N The evolution mechanism using this construct is the following: •pairs x1x2, x3x4, . . . are consumed by the rules with priority r1in membrane 1. After the application, at the next time step, of the rules having priority r2, membrane 1 dissolves setting the symbols x1, x3, . . . free to float in membrane 2. Each of those symbols is present in a number of copies equal to the relative maximum related to the pair the symbol itself comes from; •the same operations happen in membrane 2, this time applied to the pairs x1x3, x3x5, . . .. Half of the previous rules are needed to perform the same kind of processing occurred in membrane 1, to select new relative maxima from the existing pairs; •an identical processing happens in membrane 3, 4, and so on. Finally, in the skin membrane (labeled log N) the absolute maximum is computed, and sent out as |x1|. Compared to the construct (1), the implementation using multiple membranes again needs 3N−3 rules with Nsymbols, to compute the result in 2 log Ntime steps. Implementing a single N-symbol parallel comparison reduces the number of nested membranes to one, hence leading to a P system that is identical to the one seen in the case of N-symbol parallel comparison using multiple priorities on the rules. 5 Maximum Search with Linked Transport Linked transport can realize the maximum search, provided that a sufficient amount of substances are present in the environment in order to enable the needed exchange of molecules (symbols) via antiport rules. Apart from this technical aspect, the algorithmic mechanism of “vertical” symbol selection is the same as the one seen in the previous sections. In the easiest case the idea is to select symbols from pairs, by exchanging molecules with the environment. Once the symbols that are present in fewer copies have been sent out, 157 the same selection is performed over new pairs until one symbol is left in the membrane. V={x1, x2, . . . , xN, x0 1, x0 2, . . . , x0 N/2, x00 1, x00 2, . . . , x00 N/4, . . . , x(log N), y1, y2, . . . , yN, y0 1, y0 2, . . . , y0 N/2, y00 1, y00 2, . . . , y00 N/4, . . . , y(log N−1) 1, y(log N−1) 2, b1, . . . , bN/2, b0 1, . . . , b0 N/4, . . . , b(log N−1) 1, c1, . . . , cN/2, c0 1, . . . , c0 N/4, . . . , c(log N−1) 1, d1, . . . , dN/2, d0 1, . . . , d0 N/4, . . . , d(log N−1) 1, a0 1, . . . , a0 N/2, a00 1, . . . , a00 N/4, . . . , a(log N) 1} T={x(log N)}, w =x1x2. . . xN,(6) R=                                                                                                                                                (x1,out; b1y1,in) (x3,out; b2y3,in) . . . (xN−1,out; bN/2yN−1,in), (x2,out; b1y2,in) (x4,out; b2y4,in) . . . (xN,out; bN/2yN,in), (y1y2,out; x0 1,in) (y3y4,out; x0 2,in) . . . (yN−1yN,out; x0 N/2,in), (b1,out; c1d1,in) (b2,out; c2d2,in) . . . (bN/2,out; cN/2dN/2,in), (c1y1,out; x0 1,in) (c2y3,out; x0 2,in) . . . (cN/2yN−1,out; x0 N/2,in), (c1y2,out; x0 1,in) (c2y4,out; x0 2,in) . . . (cN/2yN,out; x0 N/2,in), (d1,out; a0 1,in) (d2,out; a0 2,in) . . . (dN/2,out; a0 N/2,in), (a0 1x0 1,out; b0 1y0 1,in) (a0 3x0 3,out; b0 2y0 3,in) . . . (a0 N/2−1x0 N/2−1,out;b0 N/4y0 N/2−1,in), (a0 2x0 2,out; b0 1y0 2,in) (a0 4x0 4,out; b0 2y0 4,in) . . . (a0 N/2x0 N/2,out; b0 N/4y0 N/2,in), (y0 1y0 2,out; x00 1,in) (y0 3y0 4,out; x00 2,in) . . . (y0 N/2−1y0 N/2,out; x00 N/4,in), (b0 1,out; c0 1d0 1,in) (b0 2,out; c0 2d0 2,in) . . . (b0 N/4,out; c0 N/4d0 N/4,in), (c0 1y0 1,out; x00 1,in) (c0 2y0 3,out; x00 2,in) . . . (c0 N/4y0 N/2−1,out; x00 N/4,in), (c0 1y0 2,out; x00 1,in) (c0 2y4,out; x0 2,in) . . . (c0 N/4y0 N/2,out; x00 N/4,in), (d0 1,out; a00 1,in) (d0 2,out; a00 2,in) . . . (d0 N/4,out; a00 N/4,in), · · · (a(log N−1) 1x(log N−1) 1,out; b(log N−1) 1y(log N−1) 1,in) (a(log N−1) 2x(log N−1) 2,out; b(log N−1) 1y(log N−1) 2,in) (y(log N−1) 1y(log N−1) 2,out; x(log N),in) (b(log N−1) 1,out; c(log N−1) 1d(log N−1) 1,in) (c(log N−1) 1y(log N−1) 1,out; x(log N),in) (c(log N−1) 1y(log N−1) 2,out; x(log N),in) (d(log N−1) 1,out; a(log N) 1,in) (a(log N) 1x(log N),out)                                                                                                                                                Despite the number of rules, the system evolution is quite simple: •the initial symbols xiare exchanged with identical numbers of copies of symbols yi, 158 respectively. Meanwhile, the “synchronization” symbols b1, . . . , bN/2are imported from the environment (note that |bi|=|xi|+|xi+1|>max{|xi|,|xi+1|}); •the pairs x1x2, . . . , xN−1xNare exchanged with the symbols x0 1, . . . , x0 N/2. In parallel, symbols biare exchanged with new control symbols ciand di, respectively; •for each i= 1, . . . , N/2, the symbols yi,yi+1 which could not be paired are carried out by ciand exchanged with additional x0 i. Now, x0 icontains the information on the relative maximum related to the pair (yi, yi+1). In parallel, the synchronization symbol diis exchanged with a0 i, which enables the processing of the new level of pairs (i.e., x0 1x0 2, . . . , x0 N/2−1x0 N/2) to start. The horizontal lines drawn between the braces of Rseparate the computation steps in groups, each related to the parallel processing of a level of pairs. In the final step the symbol x(log N)is sent out of the skin membrane, and the maximum can thus be read as |x(log N)|. The number of steps needed to figure out the result is 3 log Nplus the last (symport) transport. The symport/antiport rules involved in the process are 7(N/2 + N/4 + . . . + 1) + 1 = 7N−6. The system needs (2N−1) + (2N−2) = 4N−3 informative symbols and 4(N/2 + N/4 + . . .) = 4N−4 carrier and “synchronization” symbols. Note that the process ends leaving a certain amount of “garbage”, in the form of symbols of type aand c. In fact, the number of copies of such symbols left inside the membrane does not equal the number of copies of the initial symbols. Strategies to get rid of this garbage can be anyway implemented [?]. Once again, higher-degree parallel comparisons can be chosen [?]. In particular, we give the construct performing N-symbol parallel comparison (again, horizontal lines in R separate successive computation steps). V={x, x1, . . . , xN, y1, . . . , yN, a1, . . . , aN+1, b0, . . . , bN, A1, . . . , AN}, T={x}, w =x1x2. . . xN,(7) R=                                            (x1,out; b0A1y1,in) (x2,out; b0A2y2,in) . . . (xN,out; b0ANyN,in), (y1y2. . . yN,out; x, in), (b0,out; a1b1,in), (a1y2. . . yN,out; x, in) (a1y1y3. . . yN,out; x, in) . . . (a1y1. . . yN−1,out; x, in), (b1,out; a2b2,in), · · · ³¡N i¢combinations of yicarried out by ai;x, in´ (bi,out; ai+1bi+1,in), · · · (aNA1y1,out; x, in) (aNA2y2,out; x, in) . . . (aNANyN,out; x, in), (bN,out; aN+1,in), (aN+1x, out)                                            The system first exchanges xiwith yirespectively preserving the number of copies, furthermore acquires the synchronizing symbol b0. Next it exchanges with xas many N-uples of symbols yias possible, meanwhile substituting b0with b1along with acquiring the carrier symbol a1. All the remaining steps consist in exchanging (via the carrier) combinations of symbols yiwith x, meanwhile updating the sync and carrier symbols through rules of the type (bi,out; ai+1bi+1,in). During the last step, all x’s are sent out 159 via a symport rule in a way that the maximum |x|can be read in the environment. As before, garbage is left in the membrane. Again, the N-symbol comparison allows to search the maximum value straightforwardly. In the above implementation we have in fact added the symbols A1, . . . , ANthat enter the membrane during the first computation step and turn out to be useful in the end of the computation: since at most one of the rules of the type (aNAiyi,out; x, in) will be activated in practice, then Aiwill signal that xihas the largest number of copies as long as it is sent out of the membrane. As briefly discussed in section 3, the search for the maximum value can be extended to the multiple case, by sending out additional symbols in correspondence to each rule of the type (something,out; x, in). The system implementing maximum search using linked transport with N-symbol comparison computes the result in Nsteps, plus two additional steps needed to exchange molecules respectively in the beginning and the end of the process. 2N+ 1 informative symbols and 2N+2 auxiliary symbols suffice, though—refer to (4)—(2N−1)+N+N+1 = 2N+ 2N=O(2N) rules are present in the system. Additional Nsymbols are needed to compute also the maximum value (if unique). 6 “Vertical” Approach to the Maximum Search The vertical approach consists in a parallel counting of symbols with a sort of elimination of those having a lower number of copies. The iteration of this process finally leaves a membrane which is related to the symbol with maximum number of copies, and all these copies are produced by the system and sent to the environment as output of the algorithm for maximum search. In order to compute the maximum number of copies among Ngiven elements a1, . . . , aNwe consider the following P system, in which standard evolution rules and few priorities are used. V={a1, . . . , aN, a0 1, . . . , a0 N, d1, . . . , dN}, T ={a1, . . . , aN} µ= [s[1]1[2]2. . . [N]N]s, wi=a0 iaki i, ki=|ai|, i = 1, . . . , N Ri=©r1:a0 ia0 i→a0 idi out, r2:a0 iai→a0 iai out, r3:a0 i→a0 iδª ρi={r1> r2> r3}, i = 1, . . . , N Rs=                                  a0 1a0 2. . . a0 N−2a0 N−1→a0 NinN, a0 1a0 2. . . a0 N−2a0 N→a0 N−1inN−1 . . . a0 1a0 3. . . a0 N−1a0 N→a0 2in2 a0 2a0 3. . . a0 N−1a0 N→a0 1in1 d1a1→d1a1out d2a2→d2a2out . . . dNaN→dNaN out                                  (8) The system evolution can be described by the following steps: 160