Free Trial

Safari Books Online is a digital library providing on-demand subscription access to thousands of learning resources.

Share this Page URL

Chapter 3: Computational Sequence Design... > Computational Experiments - Pg. 71

Computational Sequence Design Techniques for DNA Microarray Technologies make SB applicable to problems with thermody- namic constraints. In order to explore the solution space in a satisfactory way, we need to minimize the number of free energy evaluations necessary to understand whether the various constraints are violated or not. In our implementation, we compute only one special case of thermodynamic constraint T2 at each iteration, while we postpone the evaluation of the remaining one into a post- optimization phase. This permits to reduce the number of free energy computations, focusing on those that show to be crucial in shaping up the solutions. The resulting algorithm can be therefore sketched as follows: 1. Processing phase: Classic Seed Building algorithm where combinatorial constraints are considered together with a special case of the T2 constraint. Here each string is only checked against itself, but not against the strands already in the solution. The hope is that this particular T2 constraint is sufficient to filter out most of the unfeasible strands, and to shape up the solution in an efficient way. Post Processing phase: Starting from the so- lution obtained in the previous point, a graph is built analogously to what was done before for the Stochastic Local Search approach. At this point we know that all combinato- rial constraints and self-T2 are fulfilled, so we need to take care only of the residual T2 thermodynamic constraints. Notice that the number of free energy evaluations is of the order of O(s 2 ), where s is the number of strands produced at phase 1. This number is intuitively small if the filter provided in phase 1 is efficient. Again analogously to what was done before, it is sufficient now to run a maximum clique algorithm to retrieve the largest possible clique in the graph, which corresponds to a feasible solution for the original problem. Even when the two phase approach is ad- opted, we can say that the SB algorithm works in the feasible search space, in the sense that it only produces feasible solutions (according to the constraints considered in phase 1), that are incrementally increased during the computation. This is the main difference with respect to the Stochastic Local Search method described above. It is important to emphasize that the decom- position described above is not based on any theoretical results guarantying optimality: it is a heuristic criterion that might lead to suboptimal solutions. Everything basically depends on the filter provided by phase 1. Experimental results discussed in the next section clearly suggest that the decomposition approach is effective in practice. COMPUTATIONAL EXPERIMENTS In this section we compare the results obtained by the two meta-heuristic methods described in the previous sections. 2. Experiments Set Up The comparison between the two algorithms is based on the number of feasible strands retrieved at the end of the computation. Since SLS requires the target number of strands k as input, we pro- vide SLS with k = res(SB); k = res(SB)*1.1 and k = res(SB)*1.2, where res(SB) is the number of feasible strands retrieved by seed building. In this way we check whether SLS is able to replicate, or improve the results of SB. Notice that the final result returned by SLS is less than or equal to k by definition, since infeasible strands are deleted in the post-optimization phase, as described in the previous section. In order to run experiments, we also have to define feasible free energy values for the thermodynamic constraints T1 and T2. We used the values calculated empirically and reported in (Ghiggi, 2010), which are reported in Figure 3. Notice that the same thresholds have been used 71