Better genechip microarray layouts by combining probe placement and embedding.
The microarray layout problem is a generalization of the border length minimization problem, and asks to distribute oligonucleotide probes on a microarray and to determine their embeddings in the deposition sequence in such a way that the overall quality of the resulting synthesized probes is maximized. Because of its inherent computational complexity, it is traditionally attacked in several phases: partitioning, placement, and re-embedding. We present the first algorithm, Greedy+, that combines placement and embedding and that results in improved layouts in terms of border length and conflict index (a more realistic measure of probe quality), both on arrays of random probes and on existing Affymetrix GeneChip arrays. We also present a detailed study on the layouts of the latest GeneChip arrays, and show how Greedy+ can further improve layout quality by as much as 12% in terms of border length and 35% in terms of conflict index.
de Carvalho
Sérgio A
SA
Computational Methods for Emerging Technologies, Genome Informatics, Technische Fakultät, Bielefeld University, D-33594 Bielefeld, Germany. Sergio.Carvalho@cebitec.uni-bielefeld.de
Rahmann
Sven
S
D000465:Algorithms; D019295:Computational Biology / Q000379:methods*; D015342:DNA Probes / Q000235:genetics; D004867:Equipment Design; D020224:Expressed Sequence Tags; D020869:Gene Expression Profiling; D008969:Molecular Sequence Data; D020411:Oligonucleotide Array Sequence Analysis / Q000379:methods*; D015345:Oligonucleotide Probes; D016415:Sequence Alignment / Q000295:instrumentation / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*
D015342:DNA Probes; D015345:Oligonucleotide Probes