Priority-driven Re-embedding Optimization

In this section we present a new heuristic post-placement optimization algorithm, called Priority-driven Re-embedding. Our approach is based on the same observation stated for the PivotPartitioning, namely, the fact that while some probes have an astonishing number of possible embeddings (up to several millions on a typical Affymetrix chip), others may have only a few or even only one valid embedding into the deposition sequence.

Our assumption is that those with a greater number of embeddings can better adapt to their neighbors, while those with only a limited number of embeddings are less flexible and should be re-embedded first. The idea is that we should use these probes with less degree of freedom to drive the re-embedding of their neighboring spots.

Our algorithm can be described as follows. First, we find a set of spots whose probes have only one or a limited number of embeddings. We mark these spots as finished and add their non-empty immediate neighbors to a priority queue of pending spots whose order is determined by the number of embeddings their corresponding probes have. Then, we retrieve (and remove) the first spot from the queue (the one whose probe has the least number of embeddings) and use the OSPE algorithm to re-embed its probe optimally. Finally, we mark the spot as finished and add its immediate neighbors to the queue. The algorithm repeats until the queue is fully emptied. Whenever an empty spot is reached, it is immediately marked as finished and, of course, not added to the queue.

Sometimes the layout of a chip contains “islands” of probes surrounded by empty spots. In such cases, it is necessary to do a full scan on the chip looking for non-finished spots. If any is found, it is added to the queue and processed as described above.

When computing the optimum embedding with the OSPE algorithm, we can consider all neighbors of a spot or only those which have already been marked as finished. Our experiments showed that the latter approach is more efficient. The reason may be that, by using the OSPE algorithm we always decrease the number of conflicts towards a local optimum and, a re-embedding that does not consider the neighboring probes may be a bad decision that the algorithm will never recover from. Moreover, by considering all neighbors, the algorithm can be executed several times in succession, with further reduction of conflicts.

We have also explored two variants in the ordering of the priority queue. The first one retrieves probes with the greatest number of finished spots (instead of the least number of embeddings). The intuition is that these spots also have a lesser degree of freedom since they have to adapt to a greater number of neighboring probes and, thus, should be re-embedded first. In particular, a spot with 4 finished immediate neighbors should be immediately re-embedded. Another possibility is to order the queue based on a combination of number of embeddings and number of finished neighbors.

Experiments have shown that the three variants produce on average the same reduction in conflicts. Sometimes, when the goal is to minimize border length, a priority based on the number of neighbors gives a small upper hand. If the goal is to reduce the conflict indices, it appears that the combined priority has a small advantage.

Our experiments also showed that, surprisingly, the reduction in conflicts produced with the Priority-driven optimization is only a bit better than the simpler Sequential optimization, with the disadvantage of much higher running times.

The conclusion is that the order in which the probes are re-embedded play a fairly insignificant role in the final result, and the local optimum reached in the end is only slightly higher or lower than those found with a different ordering.

Back to MicroarrayDesignAlgorithms