A Novel Algorithm for Fast Synthesis of DNA Probes on Microarrays
Article No.: 1, Pages 1 - 17
Abstract
DNA microarrays are used extensively for biochemical analysis that includes genomics and drug discovery. This increased usage demands large microarrays, thus complicating their computer aided design (CAD) and manufacturing methodologies. One such time-consuming design problem is to minimize the border length of masks used during the manufacture of microarrays. From the manufacturing point of view the border length of masks is one of the crucial parameters determining the reliability of the microarray. This article presents a novel algorithm for synthesis (placement and embedding) of microarrays, which consumes significantly less time than the best algorithm reported in the literature, while maintaining the quality (border length of masks) of the result. The proposed technique uses only a part of each probe to decide on the placement and the remaining parts for deciding on the embedding sequence. This is in contrast to the earlier methods that considered the entire probe for both placement and embedding. The second novelty of the proposed technique is the preclassification (prior to placement and embedding) of probes based on their prefixes. This decreases the complexity of the problem of deciding the next probe to be placed from that involving computation of Hamming distance between all probes (as used in earlier approaches) to the one involving searching of nonempty cells on a constant size grid array. The proposed algorithm is 43× faster than the best reported in the literature for the case of synthesizing a microarray with 250,000 probes and further exhibits linear behavior in terms of computation time for larger microarrays.
References
[1]
Akers, S. B. 1981. On the use of the linear assignment algorithm in module placement. In Proceedings of the 18th Conference on Design Automation (DAC). IEEE Press, Los Alamitos, CA, 137--144.
[2]
Alpert, C. J. and Kahng, A. B. 1993. Geometric embeddings for faster and better multi-way netlist partitioning. In Proceedings of the 30th International Conference on Design Automation (DAC). ACM, New York, NY, 743--748.
[3]
Alpert, C. J. and Kahng, A. B. 1995. Recent directions in netlist partitioning: A survey. Integr. VLSI J. 19, 1--2, 1--81.
[4]
Barone, P., Bonizzoni, P., Vedova, G. D., and Mauri, G. 2001. An approximation algorithm for the shortest common supersequence problem: An experimental analysis. In Proceedings of Symposium on Applied Computing (SAC). ACM, 56--60.
[5]
Caldwell, A. E., Kahng, A. B., and Markov, I. L. 2000. Can recursive bisection alone produce routable placements? In Proceedings of the 37th Conference on Design Automation (DAC). ACM, New York, NY, 477--482.
[6]
Cern, V. 1985. Thermodynamical approach to the traveling salesman problem: An efficient simulation algorithm. J. Optim. Theory Appl. 45, 41--51.
[7]
Chang, C.-C., Cong, J., and Xie, M. 2003. Optimality and scalability study of existing placement algorithms. In Proceedings of the Conference on Asia South Pacific Design Automation (ASPDAC). ACM, New York, NY, 621--627.
[8]
Cong, J., Romesis, M., and Xie, M. 2003. Optimality, scalability and stability study of partitioning and placement algorithms. In Proceedings of the International Symposium on Physical Design (ISPD). ACM, New York, NY, 88--94.
[9]
Cutting, D. R., Karger, D. R., Pedersen, J. O., and Tukey, J. W. 1992. Scatter/gather: A cluster-based approach to browsing large document collections. In Proceedings of the 15th Annual International ACM SIGIR Conference on Research and Development in Information Retrieval. ACM, New York, NY, 318--329.
[10]
Fiduccia, C. M. and Mattheyses, R. M. 1982. A linear-time heuristic for improving network partitions. In Proceedings of the 19th Conference on Design Automation (DAC). IEEE Press, Los Alamitos, CA, 175--181.
[11]
Hagen, L. W., Huang, D. J. H., and Kahng, A. B. 1995. Quantified suboptimality of VLSI layout heuristics. In Proceedings of the 32nd ACM/IEEE Conference on Design Automation (DAC). ACM, New York, NY, 216--221.
[12]
Hannenhalli, S., Hubbell, E., Lipshutz, R., and Pevzner, P. A. 2002. Combinatorial algorithms for design of DNA arrays. In Advances in Biochemical Engineering/Biotechnology, Springer-Verlag.
[13]
Huang, D. J.-H. and Kahng, A. B. 1997. Partitioning-based standard-cell global placement with an exact objective. In Proceedings of the International Symposium on Physical Design (ISPD). ACM, New York, NY, 18--25.
[14]
Jiang, T. and Li, M. 2002. On the approximation of shortest common supersequences and longest common subsequences. SIAM J. Comput.
[15]
Kahng, A., Mandoiu, I., Reda, S., Xu, X., and Zelikovsky, A. 2006. Computer-aided optimization of DNA array design and manufacturing. IEEE Trans. Comput.-Aided Design Integr. Circuits Syst. 25, 2, 305--320.
[16]
Kahng, A. B., Mandoiu, I., Pevzner, P., Reda, S., and Zelikovsky, A. 2003a. Engineering a scalable placement heuristic for DNA probe arrays. In Proceedings of the 7th Annual International Conference on Research in Computational Molecular Biology (RECOMB). ACM, New York, NY, 148--156.
[17]
Kahng, A. B., Mandoiu, I., Reda, S., Xu, X., and Zelikovsky, A. Z. 2003b. Evaluation of placement techniques for DNA probe array layout. In Proceedings of the IEEE.ACM International Conference on Computer-Aided Design (ICCAD). IEEE Computer Society, Los Alamitos, CA, 262.
[18]
Kahng, A. B., Mandoiu, I. I., Pevzner, P. A., Reda, S., and Zelikovsky, A. 2002. Border length minimization in DNA array design. In Proceedings of the 2nd International Workshop on Algorithms in Bioinformatics (WABI). Springer-Verlag, Berlin, 435--448.
[19]
Kasif, S., Weng, Z., Derti, A., Beigel, R., and Delisi, C. 1995. A computational framework for optimal masking in synthesis of oligonucleotide microarrays. Nucleic Acids Res. 30, 20.
[20]
Kirkpatrick, S., Gelat, C. D., Jr., and Vecchi, M. P. 1983. Optimization by simulated annealing. Science 220, 4598, 671--680.
[21]
Kozawa, T., Terai, H., Ishii, T., Hayase, M., Miura, C., Ogawa, Y., Kishida, K., Yamada, N., and Ohno, Y. 1983. Automatic placement algorithms for high packing density VLSI. In Proceedings of the 20th Conference on Design Automation (DAC). IEEE Press, Los Alamitos, CA, 175--181.
[22]
Ning, K., Choi, K. P., Leong, H. W., and Zang, L. 2005. A post processing method for optimizing synthesis strategy for oligonucleotide microarrays. Nucleic Acids Res. 33,17.
[23]
Ning, K. and Leong, H. W. 2006. Towards a better solution to the shortest common supersequence problem: The deposition and reduction algorithm. BMC Bioinform. 12, 7 Suppl. 4:S12.
[24]
Sarrafzadeh, M. and Wang, M. 1997. NRG: Global and detailed placement. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD). IEEE Computer Society, Los Alamitos, CA, 532--537.
[25]
Shahookar, K. and Mazumder, P. 1991. VLSI cell placement techniques. ACM Comput. Surv. 23, 2, 143--220.
[26]
Srinivasan, S., Kamakoti, V., and Bhattacharya, A. 2010. Theoretical lower bound on border length for synthesis of DNA probes onto a microarray. Tech. rep. TR-RISE-CSE-2010-001, Reconfigurable Intelligent Systems Engineering Laboratory, Department of Computer Science and Engineering, Indian Institute of Technology Madras, Chennai, India.
[27]
Wang, M., Yang, X., and Sarrafzadeh, M. 2000. Dragon2000: Standard-cell placement tool for large industry circuits. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD). IEEE Press, Los Alamitos, CA, 260--263.
[28]
Watson, J. D. and Crick, F. 1953. Molecular structure of nucleic acids: A structure for deoxyribo nucleic acid. Nature 171, 737--738.
[29]
Wikipedia. 2010. Photolithography.
[30]
Wolpert, D. H. and Macready, W. G. 1997. No free lunch theorems for optimization. IEEE Trans. Evol. Comput. 1, 1, 67--82.
[31]
Yuh, P. H., Yang, C. L., and Chang, Y. W. 2004. Temporal floorplanning using the T-tree formulation. In Proceedings of the IEEE/ACM International Conference on Computer-Aided Design (ICCAD). 300--305.
[32]
Yuh, P.-H., Yang, C.-L., and Chang, Y.-W. 2006. Placement of digital microfluidic biochips using the t-tree formulation. In Proceedings of the 20th Conference on Design Automation (DAC). 931--934.
Index Terms
- A Novel Algorithm for Fast Synthesis of DNA Probes on Microarrays
Recommendations
Application of Bioinformatics in the Design of Gene Expression Microarrays
ISOLA '06: Proceedings of the Second International Symposium on Leveraging Applications of Formal Methods, Verification and ValidationThe declaration that gene expression microarrays serve as invaluable tools for the global characterisation of entire genomes is widely accepted by the scientific community highly involved in microarray technology. Although microarrays have the power to ...
An Efficient Algorithm for Microarray Probes Re-annotation
Transactions on Computational Intelligence XIII - Volume 8342Systems for re-annotations of DNA microarray data for supporting analysis of results of DNA microarray experiments are becoming important elements of bioinformatics aspects of gene expression based studies. However, due to the computational problems ...
Efficient algorithm for microarray probes re-annotation
ICCCI'11: Proceedings of the Third international conference on Computational collective intelligence: technologies and applications - Volume Part IISystems for re-annotations of DNA microarray data for supporting analysis of results of DNA microarray experiments are becoming important elements of bioinformatics aspects of gene expression based studies [10]. However, due to the computational ...
Comments
Information & Contributors
Information
Published In
Copyright © 2013 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Journal Family
Publication History
Published: 01 February 2013
Accepted: 01 October 2011
Revised: 01 August 2011
Received: 01 April 2011
Published in JETC Volume 9, Issue 1
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 337Total Downloads
- Downloads (Last 12 months)6
- Downloads (Last 6 weeks)0
Reflects downloads up to 24 Dec 2024
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in