Two-dimensional Gray-Code-based Partitioning

The inspiration for this approach comes from the work of Feldman and Pevzner on uniform arrays – arrays with the complete set of probes of a given length. They proved that a placement of such an array based on a two-dimensional Gray code has an optimal border length. However, uniform arrays are of restricted interest. Moreover, their work was based on synchronous embeddings – i.e. the deposition sequence is cyclical and a probe must synthesize one (and only one) base per cycle.

Our approach, on the other hand, does not need any of the above assumptions to work. Given a set of probes, we examine their given embeddings into the deposition sequence (if no embedding is available we can quickly compute, for instance, a left-most embedding) and count how many of them are masked and how many are unmasked at the first masking step. We can then partition the chip into two horizontal bands in such a way that they can accommodate each sub-set of probes, assigning, for instance, masked probes to the top partition and unmasked probes to the bottom partition. This procedure can be repeated recursively by partitioning each sub-set of embeddings based on the next masking steps and partitioning the chip likewise, alternating vertical and horizontal partitions. Assignments of sub-sets of probes to sub-regions obey a two-dimensional gray code in such a way that masked sub-regions are placed next to other masked sub-regions in an attempt to minimize conflicts.

This strategy has proved to produce layouts that have extremely low conflicts. However, it cannot optimize the complete set of masks because at some point the regions become too small to be sub-divided, leaving the last masks with high levels of conflicts. In our experience, this algorithm needs, more than any other partitioning approach, to be combined with another placement algorithm that is able to optimize those masks that have not been optimized.

However, we believe that it has a great advantage when the goal is to minimize the conflict index of the spots. The reason is that, instead of examining the first masks, we can drive the partitioning of the chip based on the state of their embeddings at the middle masking steps, going towards both ends of the deposition sequence. This will result in a layout with extremely low conflicts in the middle masks where it has greater impact for the conflict index.

Back to MicroarrayDesignAlgorithms