Efficient selection of unique and popular oligos for large EST databases.
BACKGROUND
Expressed sequence tag (EST) databases have grown exponentially in recent years and now represent the largest collection of genetic sequences. An important application of these databases is that they contain information useful for the design of gene-specific oligonucleotides (or simply, oligos) that can be used in PCR primer design, microarray experiments and genomic library screening.


RESULTS
In this paper, we study two complementary problems concerning the selection of short oligos, e.g. 20-50 bases, from a large database of tens of thousands of ESTs: (i) selection of oligos each of which appears (exactly) in one unigene but does not appear (exactly or approximately) in any other unigene and (ii) selection of oligos that appear (exactly or approximately) in many unigenes. The first problem is called the unique oligo problem and has applications in PCR primer and microarray probe designs, and library screening for gene-rich clones. The second is called the popular oligo problem and is also useful in screening genomic libraries. We present an efficient algorithm to identify all unique oligos in the unigenes and an efficient heuristic algorithm to enumerate the most popular oligos. By taking into account the distribution of the frequencies of the words in the unigene database, the algorithms have been engineered carefully to achieve remarkable running times on regular PCs. Each of the algorithms takes only a couple of hours (on a 1.2 GHz CPU, 1 GB RAM machine) to run on a dataset 28 Mb of barley unigenes from the HarvEST database. We present simulation results on the synthetic data and a preliminary analysis of the barley unigene database.


BACKGROUND
Available on request from the authors.
Zheng
Jie
J
Department of Computer Science and Engineering, University of California, Riverside, CA 92521, USA.
Close
Timothy J
TJ
Jiang
Tao
T
Lonardi
Stefano
S
D000465:Algorithms; D001483:Base Sequence; D015342:DNA Probes / Q000737:chemistry / Q000235:genetics*; D030561:Databases, Nucleic Acid; D020224:Expressed Sequence Tags; D008969:Molecular Sequence Data; D009841:Oligonucleotides / Q000235:genetics*; D010363:Pattern Recognition, Automated / Q000379:methods; D016415:Sequence Alignment / Q000379:methods*; D017422:Sequence Analysis, DNA / Q000379:methods*
D015342:DNA Probes; D009841:Oligonucleotides