Skip Navigation

This Article
Right arrow FREE Full Text (Print PDF) Freely available
Right arrow FREE Full Text (Screen PDF)
Right arrow Alert me when this article is cited
Right arrow Alert me if a correction is posted
Services
Right arrow Email this article to a friend
Right arrow Similar articles in this journal
Right arrow Similar articles in PubMed
Right arrow Alert me to new issues of the journal
Right arrow Add to My Personal Archive
Right arrow Download to citation manager
Right arrowRequest Permissions
Google Scholar
Right arrow Articles by Kivioja, T.
Right arrow Articles by Ukkonen, E.
Right arrow Search for Related Content
PubMed
Right arrow PubMed Citation
Right arrow Articles by Kivioja, T.
Right arrow Articles by Ukkonen, E.
Social Bookmarking
Add to CiteULike   Add to Connotea   Add to Del.icio.us  
What's this?

Bioinformatics Vol. 18 no. 90001 2002
Pages S199-S206
© 2002 Oxford University Press

Assigning probes into a small number of pools separable by electrophoresis

Teemu Kivioja 1, Mikko Arvas 2, Kari Kataja 2, Merja Penttilä 2, Hans Söderlund 2 and Esko Ukkonen 1

1 Department of Computer Science, University of Helsinki, Teollisuuskatu 23, Helsinki, PO Box 26, FIN-00014, Finland
2 VTT Biotechnology, VTT Technical Research Centre of Finland, Tietotie 2, Espoo, PO Box 1500, FIN-02044, Finland

Received on January 24, 2002 ; revised on March 20, 2002 ; accepted on March 20, 2002

Motivation: Measuring transcriptional expression levels (transcriptional profiling) has become one of the most important methods in functional genomics. Still, new measuring methods are needed to obtain more reliable, quantitative data about transcription on a genomic scale. In this paper we concentrate on certain computational optimization problems arising in the design of one such novel method. From a computational point of view the key feature of the new method is that the hybridized probes are distinguished from each other based on their different size. Therefore the probes have to be assigned into pools such that the probes in the same pool have unique sizes different enough from each other. Identification of expressed RNA is given by probe pool and probe size while quantification is given by the label of the probe, e.g. fluorescence intensity.

Results: We show how to computationally find the probes and assign them into pools for a whole genome such that (i) each gene has a specific probe suitable for amplification and hybridization, and (ii) the expression level measurement can be done in a minimal number of pools separable by electrophoresis in order to minimize the total experiment cost of the measurement. Our main result is a polynomial-time approximation algorithm for assigning the probes into pools. We demonstrate the feasibility of the procedure by selecting probes for the yeast genome and assigning them into less than 100 pools. The probe sequences and their assignment into pools are available for academic research on request from the authors.

Contact: Teemu.Kivioja{at}cs.Helsinki.FI

Keywords: transciptional profiling; hybridization probe selection; graph algorithms; degree-contrained subgraph.


Add to CiteULike CiteULike   Add to Connotea Connotea   Add to Del.icio.us Del.icio.us    What's this?




Disclaimer:
Please note that abstracts for content published before 1996 were created through digital scanning and may therefore not exactly replicate the text of the original print issues. All efforts have been made to ensure accuracy, but the Publisher will not be held responsible for any remaining inaccuracies. If you require any further clarification, please contact our Customer Services Department.