English
 
User Manual Privacy Policy Disclaimer Contact us
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT
  Integer linear programming approaches for non-unique probe selection.

Klau, G. W., Rahmann, S., Schliep, A., Vingron, M., & Reinert, K. (2007). Integer linear programming approaches for non-unique probe selection. In M. Anthony, E. Boros, P. Hammer, & A. Kogan (Eds.), Discrete Mathematics and Data Mining II - DM & DM II (pp. 840-856). Amsterdam et al: Elsevier.

Item is

Basic

show hide
Item Permalink: http://hdl.handle.net/11858/00-001M-0000-0010-820E-0 Version Permalink: http://hdl.handle.net/11858/00-001M-0000-0010-820F-E
Genre: Book Chapter

Files

show Files
hide Files
:
sdarticle.pdf (Any fulltext), 246KB
 
File Permalink:
-
Name:
sdarticle.pdf
Description:
-
Visibility:
Restricted (Max Planck Institute for Molecular Genetics, MBMG; )
MIME-Type / Checksum:
application/pdf
Technical Metadata:
Copyright Date:
-
Copyright Info:
eDoc_access: MPG
License:
-

Locators

show

Creators

show
hide
 Creators:
Klau, Gunnar W., Author
Rahmann, Sven1, Author              
Schliep, Alexander1, Author              
Vingron, Martin2, Author              
Reinert, Knut, Author
Affiliations:
1Dept. of Computational Molecular Biology (Head: Martin Vingron), Max Planck Institute for Molecular Genetics, Max Planck Society, ou_1433547              
2Gene regulation (Martin Vingron), Dept. of Computational Molecular Biology (Head: Martin Vingron), Max Planck Institute for Molecular Genetics, Max Planck Society, ou_1479639              

Content

show
hide
Free keywords: Integer linear programming; Microarray; Probe; Oligonucleotide; Design; Group testing
 Abstract: 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.

Details

show
hide
Language(s): eng - English
 Dates: 2007-04-01
 Publication Status: Published in print
 Pages: -
 Publishing info: -
 Table of Contents: -
 Rev. Method: -
 Identifiers: eDoc: 336031
DOI: 10.1016/j.dam.2005.09.021
 Degree: -

Event

show

Legal Case

show

Project information

show

Source 1

show
hide
Title: Discrete Mathematics and Data Mining II - DM & DM II
Source Genre: Book
 Creator(s):
Anthony, M.H.G., Editor
Boros, E., Editor
Hammer, P.L., Editor
Kogan, A., Editor
Affiliations:
-
Publ. Info: Amsterdam et al : Elsevier
Pages: - Volume / Issue: - Sequence Number: - Start / End Page: 840 - 856 Identifier: -

Source 2

show
hide
Title: Discrete Applied Mathematics
Source Genre: Series
 Creator(s):
Boros, Endre, Editor
Affiliations:
-
Publ. Info: -
Pages: - Volume / Issue: 155 Sequence Number: - Start / End Page: - Identifier: ISSN: 0166-218X