Combinatorial algorithms for design of DNA arrays
Related Experiment Video
Updated: Sep 29, 2026

High-Density DNA and RNA microarrays - Photolithographic Synthesis, Hybridization and Preparation of Large Nucleic Acid Libraries
Published on: August 12, 2019
Sridhar Hannenhalli1, Earl Hubell, Robert Lipshutz
1Department of Mathematics, University of Southern California, Los Angeles 90089-1113, USA.
Abstract:
Optimal design of DNA arrays requires the development of algorithms with two-fold goals: reducing the effects caused by unintended illumination (border length minimization problem) and reducing the complexity of masks (mask decomposition problem). We describe algorithms that reduce the number of rectangles in mask decomposition by 20-30% as compared to a standard array design under the assumption that the arrangement of oligonucleotides on the array is fixed. This algorithm produces provably optimal solution for all studied real instances of array design. We also address the difficult problem of finding an arrangement which minimizes the border length and come up with a new idea of threading that significantly reduces the border length as compared to standard designs.
Related Concept Videos
DNA Microarrays
Maxam-Gilbert Sequencing
Challenges of the Maxam-Gilbert Method
The...
Sanger Sequencing
DNA as a Genetic Template

