Engineering a scalable placement heuristic for DNA probe arrays

ABSTRACT

Design of DNA arrays for very large-scale immobilized polymer synthesis (VLSIPS) [8] seeks to minimize effects of unintended illumination during mask exposure steps. [9, 14] formulate this requirement as the Border Minimization Problem and give methods for placement (at array sites) and embedding (in the mask sequence) of probes in both synchronous and asynchronous regimes. These previous methods do not address several practical details of the application and, more critically, are not scalable to the O(10⁸) probes contemplated for next-generation probe arrays. In this work, we make two main contributions:

• We give improved dynamic programming algorithms that perform probe embedding to minimize the number border conflicts while accounting for distance- and position-dependent border conflict weights, as well as the presence of polymorphic probes in the instance.
• We describe and experimentally validate the "engineering" of a scalable, high-quality asynchronous placement heuristic (which is moreover easily parallelizable) for DNA array design. Our heuristic is enabled by a novel approach for simultaneous re-placement and optimal re-embedding of an "independent set" of probes within a small window of the array.

.

REFERENCES

• 1: Noga Alon , Charles J. Colbourn , Alan C. H. Ling , Martin Tompa, Equireplicate Balanced Binary Codes for Oligo Arrays, SIAM Journal on Discrete Mathematics, v.14 n.4, p.481-497, 2001 [doi>10.1137/S0895480101383895]
• 2: C. J. Alpert , A. B. Kahng, Multi-way partitioning via spacefilling curves and dynamic programming, Proceedings of the 31st annual conference on Design automation, p.652-657, June 06-10, 1994, San Diego, California, United States [doi>10.1145/196244.196603]
• 3: J. J. Bartholdi and L. K. Platzman, "An O(N log N) Planar Travelling Salesman Heuristic Based On Spacefilling Curves," Operations Research Letters 1(4) (1982), pp. 121--125.
• 4: A. E. Caldwell , A. B. Kahng , I. L. Markov, Optimal partitioners and end-case placers for standard-cell layout, Proceedings of the 1999 international symposium on Physical design, p.90-96, April 12-14, 1999, Monterey, California, United States [doi>10.1145/299996.300032]
• 5: Tony F. Chan , Jason Cong , Tianming Kong , Joseph R. Shinnerl, Multilevel optimization for large-scale circuit placement, Proceedings of the 2000 IEEE/ACM international conference on Computer-aided design, November 05-09, 2000, San Jose, California
• 6: Douglass R. Cutting , David R. Karger , Jan O. Pedersen , John W. Tukey, Scatter/Gather: a cluster-based approach to browsing large document collections, Proceedings of the 15th annual international ACM SIGIR conference on Research and development in information retrieval, p.318-329, June 21-24, 1992, Copenhagen, Denmark [doi>10.1145/133160.133214]
• 7: K. Doll, F. M. Johannes, K. J. Antreich, "Iterative Placement Improvement by Network Flow Methods," IEEE Transactions on Computer-Aided Design 13(10) (1994), pp. 1189--1200.
• 8: S. Fodor, J. L. Read, M. C. Pirrung, L. Stryer, L. A. Tsai and D. Solas, "Light-Directed, Spatially Addressable Parallel Chemical Synthesis," Science 251 (1991), pp. 767--773.
• 9: S. Hannenhalli, E. Hubbell, R. Lipshutz and P. A. Pevzner, "Combinatorial Algorithms for Design of DNA Arrays," in Chip Technology (ed. J. Hoheisel), Springer-Verlag, 2002.
• 10: Dennis J.-H. Huang , Andrew B. Kahng, Partitioning-based standard-cell global placement with an exact objective, Proceedings of the 1997 international symposium on Physical design, p.18-25, April 14-16, 1997, Napa Valley, California, United States [doi>10.1145/267665.267674]
• 11: E. Hubbell and M. Mittmann, personal communication (Affymetrix, Santa Clara, CA), July 2002.
• 12: Earl Hubbell , Pavel A. Pevzner, Fidelity Probes for DNA Arrays, Proceedings of the Seventh International Conference on Intelligent Systems for Molecular Biology, p.113-117, August 06-10, 1999
• 13: Sheldon B. Akers, On the use of the linear assignment algorithm in module placement, Proceedings of the 18th conference on Design automation, p.137-144, June 29-July 01, 1981, Nashville, Tennessee, United States
• 14: Andrew B. Kahng , Ion I. Mandoiu , Pavel A. Pevzner , Sherief Reda , Alexander Zelikovsky, Border Length Minimization in DNA Array Design, Proceedings of the Second International Workshop on Algorithms in Bioinformatics, p.435-448, September 17-21, 2002
• 15: Fugen Li , G. D. Stormo, Selecting Optimum DNA Oligos for Microarrays, Proceedings of the 1st IEEE International Symposium on Bioinformatics and Biomedical Engineering, p.200, November 08-10, 2000
• 16: R.J. Lipshutz, S.P. Fodor, T.R. Gingeras, D.J. Lockhart, "High density synthetic oligonucleotide arrays," Nat. Genet. 21 (1999), pp. 20--24.
• 17: B. T. Preas and M. J. Lorenzetti, eds., Physical Design Automation of VLSI Systems, Benjamin-Cummings, 1988.
• 18: Sven Rahmann, Rapid Large-Scale Oligonucleotide Selection for Microarrays, Proceedings of the IEEE Computer Society Conference on Bioinformatics, p.54, August 14-16, 2002
• 19: R. Sengupta and M. Tompa, "Quality Control in Manufacturing Oligo Arrays: a Combinatorial Design Approach," Journal of Computational Biology 9 (2002), pp. 1--22.
• 20: L. Steinberg, "The Backboard Wiring Problem: A Placement Algorithm," SIAM Review 3(1) (1961), pp. 37--50.
• 21: K. Shahookar , P. Mazumder, VLSI cell placement techniques, ACM Computing Surveys (CSUR), v.23 n.2, p.143-220, June 1991 [doi>10.1145/103724.103725]

INDEX TERMS

Primary Classification:
  J. Computer Applications
  J.3 LIFE AND MEDICAL SCIENCES
      Subjects: Biology and genetics

Additional Classification:
  J. Computer Applications
  J.6 COMPUTER-AIDED ENGINEERING
      Subjects: Computer-aided design (CAD)

General Terms:
Algorithms, Design, Experimentation, Performance

Keywords:
DNA arrays, border minimization, probe placement