Search

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@cs.Helsinki.FI
Keywords: transciptional profiling; hybridization probe selection; graph algorithms; degree-contrained subgraph.

We performed a systematic analysis of gene upstream regions in the yeast genome for occurrences of regular expression-type patterns with the goal of identifying potential regulatory elements. To achieve this goal, we have developed a new sequence pattern discovery algorithm that searches exhaustively for a priori unknown regular expression-type patterns that are over-represented in a given set of sequences. We applied the algorithm in two cases, (1) discovery of patterns in the complete set of >6000 sequences taken upstream of the putative yeast genes and (2) discovery of patterns in the regions upstream of the genes with similar expression profiles. In the first case, we looked for patterns that occur more frequently in the gene upstream regions than in the genome overall. In the second case, first we clustered the upstream regions of all the genes by similarity of their expression profiles on the basis of publicly available gene expression data and then looked for sequence patterns that are over-represented in each cluster. In both cases we considered each pattern that occurred at least in some minimum number of sequences, and rated them on the basis of their over-representation. Among the highest rating patterns, most have matches to substrings in known yeast transcription factor-binding sites. Moreover, several of them are known to be relevant to the expression of the genes from the respective clusters. Experiments on simulated data show that the majority of the discovered patterns are not expected to occur by chance.

We performed a systematic analysis of gene upstream regions in the yeast genome for occurrences of regular expression-type patterns with the goal of identifying potential regulatory elements. To achieve this goal, we have developed a new sequence pattern discovery algorithm that searches exhaustively for a priori unknown regular expression-type patterns that are over-represented in a given set of sequences. We applied the algorithm in two cases, (1) discovery of patterns in the complete set of >6000 sequences taken upstream of the putative yeast genes and (2) discovery of patterns in the regions upstream of the genes with similar expression profiles. In the first case, we looked for patterns that occur more frequently in the gene upstream regions than in the genome overall. In the second case, first we clustered the upstream regions of all the genes by similarity of their expression profiles on the basis of publicly available gene expression data and then looked for sequence patterns that are over-represented in each cluster. In both cases we considered each pattern that occurred at least in some minimum number of sequences, and rated them on the basis of their over-representation. Among the highest rating patterns, most have matches to substrings in known yeast transcription factor-binding sites. Moreover, several of them are known to be relevant to the expression of the genes from the respective clusters. Experiments on simulated data show that the majority of the discovered patterns are not expected to occur by chance.

An on-line algorithm is presented for constructing the suffix tree for a given string in time linear in the length of the string. The new algorithm has the desirable property of processing the string symbol by symbol from left to right. It always has the suffix tree for the scanned part of the string ready. The method is developed as a linear-time version of a very simple algorithm for (quadratic size) suffixtries. Regardless of its quadratic worst case this latter algorithm can be a good practical method when the string is not too long. Another variation of this method is shown to give, in a natural way, the well-known algorithms for constructing suffix automata (DAWGs).