de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Book Chapter

Efficient Computational Design of Tiling Arrays Using a Shortest Path Approach.

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons50523

Schliep,  Alexander
Dept. of Computational Molecular Biology (Head: Martin Vingron), Max Planck Institute for Molecular Genetics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons50394

Krause,  Roland
Dept. of Computational Molecular Biology (Head: Martin Vingron), Max Planck Institute for Molecular Genetics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)
There are no public fulltexts available
Supplementary Material (public)
There is no public supplementary material available
Citation

Schliep, A., & Krause, R. (2007). Efficient Computational Design of Tiling Arrays Using a Shortest Path Approach. In S. H. Raffaele Giancarlo (Ed.), Algorithms in Bioinformatics (pp. 383-394). Berlin / Heidelberg: Springer.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0010-82E1-1
Abstract
Genomic tiling arrays are a type of DNA microarrays which can investigate the complete genome of arbitrary species for which the sequence is known. The design or selection of suitable oligonucleotide probes for such arrays is however computationally difficult if features such as oligonucleotide quality and repetitive regions are to be considered. We formulate the minimal cost tiling path problem for the selection of oligonucleotides from a set of candidates, which is equivalent to a shortest path problem. An efficient implementation of Dijkstra’s shortest path algorithm allows us to compute globally optimal tiling paths from millions of candidate oligonucleotides on a standard desktop computer. The solution to this multi-criterion optimization is 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. Solutions for the basic formulation can be obtained more efficiently from Monge theory.