Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Home
Search
Quick Search
Advanced
Fulltext
Browse
Collections
Persons
My eDoc
Session History
Login
Name:
Password:
Documentation
Help
Support Wiki
Direct access to
document ID:


          Institute: MPI für molekulare Genetik     Collection: Department of Computational Molecular Biology     Display Documents



  history
ID: 404604.0, MPI für molekulare Genetik / Department of Computational Molecular Biology
Efficient Algorithms for the Computational Design of Optimal Tiling Arrays
Authors:Schliep, Alexander; Krause, Roland
Language:English
Date of Publication (YYYY-MM-DD):2008-10-01
Title of Journal:IEEE/ACM Transactions on Computational Biology and Bioinformatics
Volume:5
Issue / Number:4
Start Page:557
End Page:567
Copyright:© 2008 IEEE. All rights reserved.
Review Status:not specified
Audience:Experts Only
Abstract / Description: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 trade offs between hybridization parameters, probe quality and tiling density easily.
Free Keywords:Biology and genetics
Graph Theory
External Publication Status:published
Document Type:Article
Communicated by:Martin Vingron
Affiliations:MPI für molekulare Genetik
Identifiers:URL:http://www2.computer.org/portal/web/csdl/doi/10.11...
The scope and number of records on eDoc is subject to the collection policies defined by each institute - see "info" button in the collection browse view.