Home News About Us Contact Contributors Disclaimer Privacy Policy Help FAQ

Quick Search
My eDoc
Session History
Support Wiki
Direct access to
document ID:

          Display Documents

ID: 336031.0, MPI für molekulare Genetik / Department of Computational Molecular Biology
Integer linear programming approaches for non-unique probe selection.
Authors:Klau, Gunnar W.; Rahmann, Sven; Schliep, Alexander; Vingron, Martin; Reinert, Knut
Place of Publication:Amsterdam et al
Date of Publication (YYYY-MM-DD):2007-04-01
Title of Book:Discrete Mathematics and Data Mining II - DM & DM II
Start Page:840
End Page:856
Full Name of Book-Editor(s):M.H.G. Anthony, E. Boros, P.L. Hammer and A. Kogan
Title of Series:Discrete Applied Mathematics
Full Name(s) of Series Editor(s):Endre Boros
Copyright:© 2008 Elsevier B.V. All rights reserved
Review Status:not specified
Audience:Experts Only
Abstract / Description:In addition to their prevalent use for analyzing gene expression, DNA microarrays are an efficient tool for biological, medical, and industrial applications because of their ability to assess the presence or absence of biological agents, the targets, in a sample. Given a collection of genetic sequences of targets one faces the challenge of finding short oligonucleotides, the probes, which allow detection of targets in a sample by hybridization experiments. The experiments are conducted using either unique or non-unique probes, and the problem at hand is to compute a minimal design, i.e., a minimal set of probes that allows to infer the targets in the sample from the hybridization results. If we allow to test for more than one target in the sample, the design of the probe set becomes difficult in the case of non-unique probes.

Building upon previous work on group testing for microarrays we describe the first approach to select a minimal probe set for the case of non-unique probes in the presence of a small number of multiple targets in the sample. The approach is based on an integer linear programming formulation and a branch-and-cut algorithm. Our implementation significantly reduces the number of probes needed while preserving the decoding capabilities of existing approaches.
Free Keywords:Integer linear programming; Microarray; Probe; Oligonucleotide; Design; Group testing
Comment of the Author/Creator:Corresponding author. Mathematics in Life Sciences, Free University Berlin, Arnimallee 3, D-14195 Berlin, Germany.

1 Note that, instead of modifying the objective function by making the virtual probes expensive, we could also attack this problem in a two-step process: first, minimize the number of virtual probes, and then add the corresponding variables to the master ILP and solve it using the original objective function.
2 In fact, this restricts the set of feasible solutions too much. The problem formulation only requires that S≠T, not that S∩T=empty set. In the next section we show how to formulate the S≠T requirement by introducing additional variables. For the sake of clarity, we stick to S∩T=empty set for the moment.
3 The error rates f0 and f1 should not be confounded with the prevalences fi despite the similar notation.
External Publication Status:published
Document Type:InBook
Communicated by:Martin Vingron
Affiliations:MPI für molekulare Genetik
External Affiliations:Mathematics in Life Sciences, Free University Berlin, Arnimallee 3, D-14195 Berlin, Germany;
2.DFG Research Center MATHEON “Mathematics for Key Technologies”, Berlin, Germany;
3.Algorithms and Statistics for Systems Biology, Genome Informatics, Technische Fakultät, Bielefeld University, D-33594 Bielefeld, Germany;
4.Algorithmic Bioinformatics, Free University Berlin, Takustr. 9, D-14195 Berlin, Germany.
Full Text:
Sorry, no privileges
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.