Genomic analysis is a gaining prominence, specifically in the areas of forensics and drug discovery. DNA microarrays are the devices employed for performing the genomic analysis. Border minimization problem (BMP) is a well-known optimization problem in the automated design of DNA microarrays. The problem of BMP can be considered from two perspectives, namely placement and embedding. This paper presents a comparative study of different techniques reported in the literature for BMP and current open challenges. © 2014 by the IETE.

Veezhinathan Kamakoti

Department of Computer Science and Engineering

Biochips

Combinatorial optimization

microarrays

AUTOMATED DESIGN

Comparative studies

DNA MICRO-ARRAY

GENOMIC ANALYSIS

Minimization problems

Optimization problems

PLACEMENT

QUADRATIC ASSIGNMENT PROBLEMS

Genes

IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

A Review of Algorithms for Border Length Minimization Problem

IETE Technical Review (Institution of Electronics and Telecommunication Engineers, India)

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 themanufacture of microarrays. From themanufacturing 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. © 2013 ACM.

ACM Journal on Emerging Technologies in Computing Systems

A novel algorithm for fast synthesis of DNA probes on microarrays

The problem of placement is well known in Computer Aided Design (CAD) of VLSI Chips, DNA Micro arrays and Microfluidic biochips. Because of the similarity of the placement problem across diverse domains a generalization of the same is reported in the literature. The generalized placement problem is an instance of the classical Quadratic Assignment Problem (QAP). In this paper, we present a new randomization based heuristic algorithm for QAP. The key to success of the proposed technique is a novel probability distribution that is employed by the heuristics to generate the necessary randomization. We show through simulation results that the proposed algorithm finds competitive solutions comparable with one of the best heuristics reported in literature, while consuming significantly smaller amount of CPU time. © 2011 IEEE.

Proceedings - 2011 International Symposium on Electronic System Design, ISED 2011

Towards quick solutions for generalized placement problem

IETE Technical Review

Power Factor Improvement and Voltage Harmonics Reduction in Pulse Width Modulation AC Chopper Using Bee Colony Optimization

Journal	Data powered by TypesetIETE Technical Review (Institution of Electronics and Telecommunication Engineers, India)
Publisher	Data powered by TypesetTaylor and Francis Ltd.
ISSN	02564602
Open Access	No