392159 Optimization of Microarray Design (Pj) (WiSe 2005/2006)

This project concerns the layout of (high-density) oligonucleotide microarrays. Microarrays are one of the most important tools for gene expression studies. The chips produced by Affymetrix are considered the industry standard. They contain more than one million spots, with each spot accommodating several million copies of a probe. Probes are typically 25 nt long and are synthesized on the chip, in parallel, with the help of a photolithographic mask.

We are interested in finding a good arrangement of the probes on the chip surface maximizing a particular quality measure. This is an interesting combinatorial problem. It can be seen as an instance of a Quadratic Assignment Problem (QAP). However, QAP is notoriously hard (an exact solution for problem sizes larger than n=10 are not computable in a reasonable time). Therefore, we need heuristic algorithms to find good (but not necessarily optimal) solutions.

The main goal of this project is thus to implement heuristic algorithms in an existing framework. Some of the concepts that might be involved are: a) string algorithms: sequence alignment, shortest common supersequence; b) dynamic programming; c) graph algorithms (TSP, perfect matching); d) greedy and partitioning heuristics.

Students will choose one or more projects during the semester (depending on their complexity). Work can be accomplished alone or in pairs. The main goal is not only to implement the algorithms but also to evaluate them.

We will be meeting once a week (at least in the beginning). Time and place are yet to be determined.

Requirements for participation, required level

As for prerequisites, you should be proficient in a high-level programming language as this project is very much focused on programming assignments. Anyone with Java, Perl or Python will benefit from reusing existing code. Experience with data structures, string algorithms, dynamic programming and graph algorithms are a plus. You should also be able to work reasonably well in English. No biology background is required.