Gesellschaft fr Informatik e.V.

Lecture Notes in Informatics


German Conference on Bioinformatics P-83, 11-20 (2006).

Gesellschaft für Informatik, Bonn
2006


Copyright © Gesellschaft für Informatik, Bonn

Contents

Microarray Layout as Quadratic Assignment Problem

Sérgio A. De Carvalho Jr. and Sven Rahmann

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 microarray layouts, and we show that the probe placement problem is an instance of the quadratic assignment problem (QAP), which opens up the way for using QAP heuristics. We use an existing heuristic called GRASP to design the layout of small artificial chips with promising results. We compare this approach with the best known algorithm and describe how it can be combined with other existing algorithms to design the latest million-probe microarrays.


Full Text: PDF

Gesellschaft für Informatik, Bonn
ISBN 978-3-88579-177-5


Last changed 03.11.2010 09:55:04