Tiling: Design of Tiling Arrays
The representation of a genome by oligonucleotide probes is a prerequisite for the analysis of many of its basic properties, such as transcription factor binding sites, chromosomal breakpoints, gene expression of known genes and detection of novel genes, in particular those coding for small RNAs. An ideal representation would consist of a high density set of oligonucleotides with similar melting temperatures that do not cross-hybridize with other regions of the genome and are equidistantly spaced. The implementation of such design is typically called a tiling array or genome array.
We formulate the minimal cost tiling path problem for the selection of oligonucleotides from a set of candidates. Computing the selection of probes requires multi-criterion optimization, which we cast into a shortest path problem. Standard algorithms running in linear time allow us to compute globally optimal tiling paths from millions of candidate oligonucleotides on a standard desktop computer for most problem variants. The solutions to this multi-criterion optimization are spatially adaptive to the problem instance. Our formulation incorporates experimental constraints with respect to specific regions of interest and tradeoffs between hybridization parameters, probe quality and tiling density easily.
For further information contact Alexander Schliep (alexander@schlieplab.org). This project is connected to the following projects: Tileomatic.
Team
Members: Alexander Schliep, Christoph Hafemeister. Collaborators: Roland Krause (University of Luxembourg), Jörg Schreiber (Max Planck Institute for Infection Biology, Department of Immunology), Tino Polen (Regulatory Switches and Synthetic Biology Group, Institute of Biotechnology 1, Forschungszentrum Jülich).
Publications
Hafemeister. Efficient Computation of Probe Qualities. Master's Thesis, Freie Universität Berlin, May 2008. Schliep et al.. Efficient algorithms for the computational design of optimal tiling arrays. IEEE/ACM Transactions on Computational Biology and Bioinformatics 2008, 557–567. Macula et al.. New, improved, and practical k-stem sequence similarity measures for probe design. J. Comput. Biol. 2008, 15, 525–534. Schliep et al.. Efficient Computational Design of Tiling Arrays Using a Shortest Path Approach. In Algorithms in Bioinformatics, Springer Berlin / Heidelberg, Volume 4645/2007, 383–394, 2007.