Abstract
The production of commercial DNA microarrays is based on a light-directed chemical synthesis driven by a set of masks or micromirror arrays. Because of the natural properties of light and the ever shrinking feature sizes, the arrangement of the probes on the chip and the order in which their nucleotides are synthesized play an important role on the quality of the final product. We propose a new model called conflict index for evaluating the layout of microarrays. We also present a new algorithm, called Pivot Partitioning, that improves the quality of layouts, according to existing measures, by over 6% when compared to the best known algorithms.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Binder, H., Preibisch, S.: Specific and nonspecific hybridization of oligonucleotide probes on microarrays. Biophysical Journal 89, 337–352 (2005)
de Carvalho Jr., S., Rahmann, S.: Microarray Layout as a Quadratic Assignment Problem (submitted, 2006)
Çela, E.: The Quadratic Assignment Problem: Theory and Algorithms. Kluwer, Dordrecht (1998)
Chase, P.: Subsequence numbers and logarithmic concavity. Discrete Mathematics 16, 123–140 (1976)
Fodor, S., Read, J., Pirrung, M., Stryer, L., Lu, A., Solas, D.: Light-directed, spatially addressable parallel chemical synthesis. Science 251, 767–773 (1991)
Hannenhalli, S., Hubell, E., Lipshutz, R., Pevzner, P.: Combinatorial algorithms for design of DNA arrays. Advances in Biochemical Engineering / Biotechnology 77, 1–19 (2002)
Kahng, A., Mandoiu, I., Pevzner, P., Reda, S., Zelikovsky, A.: Border Length Minimization in DNA Array Design. In: Guigó, R., Gusfield, D. (eds.) WABI 2002. LNCS, vol. 2452, p. 435. Springer, Heidelberg (2002)
Kahng, A., Mandoiu, I., Pevzner, P., Reda, S., Zelikovsky, A.: Engineering a scalable placement heuristic for DNA probe arrays. In: Proc. 7th Int’l Conf. on Computational Molecular Biology RECOMB 2003, pp. 148–156 (2003)
Kahng, A., Mandoiu, I., Reda, S., Xu, X., Zelikovsky, A.: Evaluation of placement techniques for DNA probe array layout. In: Proc. the IEEE/ACM Conf. on Computer-Aided Design, pp. 262–269 (2003)
Rahmann, S.: The shortest common supersequence problem in a microarray production setting. In: Proc. 2nd European Conf. on Computational Biology ECCB 2003. Bioinformatics, 19(suppl. 2), ii156–ii161 (2003)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2006 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
de Carvalho, S.A., Rahmann, S. (2006). Improving the Layout of Oligonucleotide Microarrays: Pivot Partitioning. In: Bücher, P., Moret, B.M.E. (eds) Algorithms in Bioinformatics. WABI 2006. Lecture Notes in Computer Science(), vol 4175. Springer, Berlin, Heidelberg. https://doi.org/10.1007/11851561_30
Download citation
DOI: https://doi.org/10.1007/11851561_30
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-39583-6
Online ISBN: 978-3-540-39584-3
eBook Packages: Computer ScienceComputer Science (R0)