BACKGROUND
for most organisms, expressed sequence tag  datasets represent the largest collection of genetic sequences available.
as of june  <dig> more than forty organisms have more than  <dig>  ests in genbank dbest  <cit> , including barley  with over  <dig>  ests.
most ests contain only part of the transcribed sequence of a gene, generally 200– <dig> bases from one end of a cdna clone.
in order to obtain extended, and in many cases complete, transcript sequences, raw est data is processed through several steps to produce a "unigene" dataset that represents the full complexity of the initial est collection.
processing steps include removal of vector and low quality sequences followed by clustering into assemblies, from which consensus sequences are referred to as unigenes.
in the case of barley, as of february  <dig> the collection has over  <dig>  unigenes comprising a total of more than  <dig> megabases.
unigene datasets for numerous organisms can be obtained from genbank  <cit> , tigr  <cit>  and various organism-specific sources .
given a collection of unigenes, oligospawn  <cit>  serves two complementary purposes arising in the selection of oligos for overgo probes.
overgo probes, first described by ross et al.
<cit> , are produced using two oligos that are complementary to each other and anneal to form a double-stranded region.
first, oligospawn can identify short oligos that are unique to each unigene in the database.
second, it can select oligos that are popular among the unigenes.
more precisely, a unique oligo is one that appears in one unigene but does not occur  in any other, and a popular oligo is an oligo that occurs  in the largest number of unigene sequences.
typical applications of unique oligos are the design of pcr primers and the selection of probes for microarray studies.
for bac library screening, the purpose of unique oligos is to have the means to unambiguously link each probe to its specific gene-bearing bac clones  <cit> .
the associated computational problem has been studied quite extensively , but practical implementations usually are based on the "all-against-all blast" strategy and hence very slow on large datasets.
among the primer/probe design softwares, a partial list would contain primer <dig>  <cit> , oligowiz  <cit> , oligoarray  <cit> , and probemer  <cit> , soop  <cit> , and overgo maker  <cit>  among others.
in the context of bac library screening, the purpose of popular oligos is to identify the largest possible list of gene-bearing bac clones using the smallest possible number of probes .
this strategy is aligned with the desire to economize the identification of what may be only a small portion of gene-bearing fragments from an entire genome.
our interest in popular oligos arises from screening a large collection of bac clones for barley.
it has been shown previously by a number of independent methods that the expressed genes in triticeae are concentrated in a small fraction of the total genome.
in barley, this portion of the genome, often referred to as the gene-space, has been estimated to be only 12% of the total genome  <cit> .
if this is indeed true, then perhaps only 12%–20% of the clones in a typical bac library would carry expressed genes, and therefore also the vast majority of barley genes could be sequenced by focusing only on this portion of the genome.
an efficient method to reveal the portion of bac clones derived from the gene-space has the potential for tremendous cost savings in the context of obtaining the sequences of the vast majority of barley genes.
the same approach would potentially accelerate progress in many crop plants and other systems that are not being considered for whole-genome sequencing.
popular overgos might not be appropriate when the objective is to obtain gene-specific results .
however, when the objective is maximize the number of gene-bearing bacs found, then it is more cost-effective to use popular overgo rather than unique overgos.
in addition to this, one cannot hope to design unique overgos for all the unigenes because, for example, of the presence of gene families.
users must also be careful in using popular overgos in pooling strategies, since they might results in too many positives.
the computational problem arising from the selection of popular oligos is an instance of a more general class of problems, called pattern discovery.
several pattern discovery algorithms have been proposed in the literature and implemented in software tools.
a few examples are meme  <cit> , consensus  <cit> , gibbssampler  <cit>  and verbumculus  <cit>  among others.
although some of these tools are able to give very accurate results on datasets in the order of a few tens of kb, they collapse, typically for lack of primary memory, when asked to process very large datasets.
oligospawn differs from other probe-finding and pattern discovery software in several important characteristics.
the main advantages brought about by this tool are its speed and relatively low memory requirements for datasets in the range of unigenes and total bases that are typical of the entire transcribed sequence dataset from eukaryotic organisms.
both algorithms  have been carefully engineered to achieve satisfactory speeds on ordinary pcs.
although the actual time is highly dependent on the parameters on which the algorithms are run, the execution of each of the algorithms on the barley unigene dataset typically takes just a few hours on a regular pc.
the main algorithmic ideas behind the design of oligospawn were reported in previous publications  <cit> .
in this paper we report on the release of oligospawn, its usage and limitations.
in addition, we present new criteria that were carefully hand-tuned to model the hybridization process.
we also discuss in more detail the filtering steps  and we report some preliminary biological experiments.
implementation
we initially based our oligo design algorithms on the length of  <dig> bases, following the procedure of thomas et al.
<cit> , where 36-mer "overgo" probes were successfully used to screen several mammalian bac libraries.
for 36-mer overgo probes, two 22-mers create the initial template for dna synthesis, overlapping in  <dig> bases, leading to the production of a labeled probe.
overgo 36-mers probes may anneal to genomic dna segments and produce a positive hybridization signal even if the 36-mer is not perfectly matched to  <dig> consecutive bases in the target dna.
in the extreme example, an overgo probe with  <dig> consecutive perfect matches and a terminal mismatch would hybridize and produce a signal.
similarly, an oligo with  <dig> consecutive matches and  <dig> terminal mismatches would also seem likely to hybridize.
however an oligo with only  <dig> consecutive matches and  <dig> mismatches distributed evenly through the remaining  <dig> bases would have a very decreased melting temperature and would not produce a signal under standard hybridization and washing conditions.
dna sequencing primers generally are in the range of only 17– <dig> nucleotides, and a popular microarray format is based on 25-mers.
these lengths are sufficient for annealing at moderate temperatures, yet not so long that non-perfect-matches are an overriding issue.
considerations of non-perfectly-matched oligos have recently been described in the context of microarrays  <cit> .
unique oligos
in order to increase the likelihood that a 36-mer is unique in the operational sense of hybridizing to only one gene in the genome, we allow no more than  <dig> consecutive perfect matches, and we place a further requirement on the density of mismatches throughout the remainder of the 36-mer.
the unique oligo problem is to identify 36-mers in the unigenes collection such that each 36-mer occurs exactly in one unigene and does not occur exactly or approximately in any other unigene.
more specifically, based on the considerations above, we define a 36-mer p that occurs in a unigene sequence s to be unique if all the following conditions are satisfied
• for any 16-mer x that occurs exactly in p, and any 16-mer y that does not occur exactly in s, h >  <dig>
• for any 20-mer x that occurs exactly in p, and any 20-mer y that does not occur exactly in s, h >  <dig>
• for any 24-mer x that occurs exactly in p, and any 24-mer y that does not occur exactly in s, h >  <dig>
• for any 30-mer x that occurs exactly in p, and any 30-mer y that does not occur exactly in s, h >  <dig>
• for any 36-mer x that occurs exactly in p, and any 36-mer y that does not occur exactly in s, h >  <dig>
where h denotes the the number of mismatches  between two sequences x and y of equal length.
our strategy to identify unique oligos first eliminates all the 36-mers that cannot be unique.
the algorithm is based on the following observation.
assume that we have two oligos of size l, which disagree in at most d positions, that is, there are at most d mismatches.
then, they have to share a string of size l/ that contains at most one mismatch.
we call substrings of this size the seeds.
using this idea, we designed an efficient two-phase algorithm.
in the first phase, we cluster all the possible seeds from the unigenes into groups such that within each group, a seed has no more than one mismatch with the other seeds.
then, we extend the flanking regions of a seed, and check whether the extended 36-mer violates any of the above conditions.
if so, the extended 36-mer is not unique.
observe that we only need to compare 36-mers within a group because any two 36-mers extended from seeds in different groups are different enough that the conditions above would be immediately satisfied.
popular oligos
the popular oligo problem is the problem of finding all the 36-mers that appear  in a sufficiently large number of unigene sequences.
more precisely, we say that a 36-mer x matches another 36-mer y, if the following condition is true
• x and y share a consecutive perfect match of  <dig> nucleotides, called a core, and
• either one of the following two conditions is satisfied
- h <  <dig>  or
- h =  <dig>  and
* for any pair x', y' of 25-mers obtained by extending the core, h <  <dig>  and
* for any pair x", y" of 30-mers obtained by extending the core, h <  <dig>
since popular oligos are not required to appear exactly in the unigene sequences, it would be too computationally expensive to find them by exhaustive enumeration.
however, we can reduce the search space using the same idea as in the algorithm for unique oligos, except that here the role of seeds is played by the cores.
first, we determine the popularity of the cores  in the unigene dataset.
a critical parameter here is the core threshold tc, which is the minimum number of unigenes in which the core should appear exactly to be declared popular .
second, each popular core is extended to a 36-mer.
then, each group of 36-mer is hierarchically clustered.
based on the clustering tree, we compute the common oligos shared by the 36-mers by performing set intersection.
these common oligos become candidate popular oligos.
both algorithms combine heuristics and well-established algorithmic and data structuring techniques such as hashing, approximate string matching, and clustering.
a more detailed explanation can be found in  <cit> .
an outline of the popular oligo algorithm is illustrated in figure  <dig>
filtering unsuitable candidates
for both unique and popular oligos, we apply a filtering phase to discard unsuitable oligos based on gc content, melting temperatures, self-annealing of 36-mers, low-complexity, and the presence of repetitive regions.
all these parameters can be adjusted by the user .
the melting temperature tm is calculated using the formula in  <cit>  as implemented in primer <dig>  <cit> .
self-annealing of oligos is determined by performing an end-free sequence alignment between the 22-mer prefix and the reverse complement of the 22-mer suffix of an oligo.
an oligo is discarded if the alignment score is higher than a predetermined threshold.
we use the program dust  <cit>  to determine low-complexity regions in oligos.
finally, oligospawn filters out those popular oligos that have significant matches against repeat database, e.g., triticeae repeat sequence database  in the case of barley, or any other repeat database provided by the user.
platforms and web interface
the software oligospawn was developed using the gnu c++ compiler under the linux operating system.
the executable for linux/i <dig> can be downloaded from the oligospawn website.
the source code is also available from the same website under the gpl licence.
any platform for which gnu c++ is available  would be able to compile and run the stand-alone software.
the web server is running at  <cit>  and it was developed using php  <cit> , which is an open-source scripting language.
the web server has been tested with netscape, mozilla, safari, and internet explorer.
figure  <dig> shows a screen shot of the web interface for the popular oligo tool, whereas figure  <dig> shows how the output is displayed.
for technical reasons, the web server does not allow inputs larger than  <dig> megabases.
if the dataset is bigger, we suggest the user either to install the software locally or to get in touch with one of the authors of this paper.
usage
the large majority of parameters on the website are self-explanatory .
one of the parameters for the popular oligo, however, deserves a special discussion.
the parameter is the threshold tc on the popularity of the cores.
if one sets this parameter to a value v, he should expect each oligo produced by the tool to hit v or more unigenes of the dataset.
although this property is not guaranteed, it should help the intuition in setting tc.
the ideal output of the popular oligo tool is a set of oligos of the minimum cardinality that maximizes the number of unigenes hit by at least one oligo.
as reported in  <cit>  decreasing the parameter tc has the effect of increasing both the number of oligos in the pool and the number of covered unigenes.
however, by doing so the running time grows considerably.
more importantly, the ratio of covered unigenes to oligos  decreases as the threshold decreases.
for a unigene set containing a few tens of thousands of unigenes we suggest that users start with a value of tc around  <dig>  and then progressively decrease tc until the desired coverage is attained.
if tc is low , the running time could be in the order of a few tens of hours on a regular pc for a large unigene datasets .
since the other parameters  control the selection of the candidates, the stricter is their range, the faster the software will run.
if the range is too small, it is possible that no oligo will be reported.
users who choose to install the software locally will find a readme file in the archive explaining the compilation, installation and usage procedures.
the two programs can be invoked as follows
pop0ligo.exe unigene.fasta
uniq0ligo.exe unigene.fasta
the options for the two linux executables are reported in table  <dig>  for example
$ pop0ligo.exe unigene.fasta -c  <dig> -g  <dig> -g  <dig> -m  <dig> -m  <dig> -r trep.fasta
will compute the popular oligos for the unigenes contained in the file unigene.fasta with tc=  <dig>  gc content between 45% and 55%, and melting temperature between 50°c and 80°c.
the program will discard any oligo that matches a sequence in trep.fasta.
the executable uniq0ligo.exe has a special option -t that allows the user to choose how many unique oligos to report for each unigene.
if several oligo candidates are available for one unigene the program will report the requested number spread evenly across that unigene.
the same parameters in table  <dig> can be found on the web server.
RESULTS
in order to test and evaluate oligospawn, oligos were designed from the unigene set assembly #  <dig> of harvest:barley  <cit> .
popular 36-mer oligos were generated by an older version of the software oligospawn with threshold tc =  <dig>  gc content in the range 45–56%.
since the older version of oligospawn did not yet offer filtering against repeat databases this process was supplemented by some manual actions, as follows.
oligos matching repetitive dna and rrna were filtered out with blast searches  against trep and the tigr gramineae repeat databases   <cit> .
following this search, 36-mers with  <dig> or more consecutive matches to repetitive sequences were discarded.
out of  <dig> initially proposed popular oligos, a total of  <dig> were discarded by this method.
all these filtering step are now included in oligospawn .
the popular 36-mers were also "blasted"  against the swissprot  <cit>  and nr protein databases for annotation purposes.
the 36-mers with nine of twelve possible amino acids identical to the subject sequence were chosen for further testing.
out of the initial  <dig> popular 36-mers analyzed,  <dig> passed this criterion.
finally, popular oligos classified as transcription and signal transduction components, a total of  <dig> out of these  <dig>  were used for probing the morex barley bac library  <cit> .
overgo hybridization
overgo labeling and hybridization was done essentially as described by ross et al.
<cit> .
briefly, probes were radioactively labeled individually with 32p-datp and 32p-dctp.
for background detection, a 36-mer representing the escherichia coli genome was also labeled  <cit> .
hybridization using a mixture of all  <dig> probes was then performed on high-density filters of the  <dig> × morex barley bac library  <cit> , followed by washing and exposure to autoradiography film  <cit> .
an average of  <dig> bag clones per filter  were scored as positive, yielding a total of about  <dig>  positive bac clones from only  <dig> popular overgos.
screening with  <dig> unique overgos would be expected to identify only about  <dig> total clones .
therefore, the  <dig> popular oligos described above netted about  <dig> times as many positive clones as would unique oligos.
results with other sets of popular oligos not described in this manuscript have given comparable results.
therefore, we conclude that the popular oligo algorithm provides a substantial gain of efficiency in probing bac genomics libraries for gene-containing clones.
the number of positive bac clones identified with various pools sizes of unique oligos has consistently been in the range of  <dig> to  <dig> bacs per unique oligo.
for example, pools of  <dig> unique oligos repeatedly provide about  <dig>  to  <dig>  positive bac addresses.
furthermore, checking the sequences of unique oligos with blast has consistently provided assurance that our unique oligo algorithm indeed is as selective as it is intended to be.
CONCLUSIONS
the development of oligospawn spanned a period of more than two years for conception, design, optimization, tuning, and several cycles of changes in the criteria used to model the hybridization of short oligos.
before oligospawn the problem of finding popular oligos from typically large unigene datasets, as exist for barley and several other organisms, could not be solved efficiently using standard desktop computers.
furthermore, most of the commonly used pattern discovery algorithms are not scalable to this level and therefore could not solve this problem using any computer configuration.
although oligospawn uses several heuristics to speed up the computation and therefore cannot guarantee the optimality of the probe it produces, the experiments on the screening of the bac clone library for barley have demonstrated its effectiveness.
one major limitation of oligospawn is that the length of the oligos is currently fixed at  <dig> bases.
it is straightforward to extend the algorithms to accommodate oligo lengths that are not too far from  <dig> bases, and we are currently working on extending the software to allow the user to specify the oligo length .
availability and requirement
project name: oligospawn
project homepage:
operating system: linux
programming languages: c++, php
licence: gnu gpl
any restriction to use by non-academics: no
authors' contributions
js and tc designed the specification of the overgos and the criteria to model the hybridization.
jz, tj and sl designed the two algorithms.
jz wrote and tested the software oligospawn.
js and km performed the overgo labeling and hybridization experiments.
all authors read and approved the final manuscript.

 for most organisms, expressed sequence tag datasets represent the largest collection of genetic sequences available. as of june more than forty organisms have more than ests in genbank dbest, including barley with over ests. most ests contain only part of the transcribed sequence of a gene, generally 200– bases from one end of a cdna clone. in order to obtain extended, and in many cases complete, transcript sequences, raw est data is processed through several steps to produce a "unigene" dataset that represents the full complexity of the initial est collection. processing steps include removal of vector and low quality sequences followed by clustering into assemblies, from which consensus sequences are referred to as unigenes. in the case of barley, as of february the collection has over unigenes comprising a total of more than megabases. unigene datasets for numerous organisms can be obtained from genbank, tigr and various organism-specific sources. given a collection of unigenes, oligospawn serves two complementary purposes arising in the selection of oligos for overgo probes. overgo probes, first described by ross et al., are produced using two oligos that are complementary to each other and anneal to form a double-stranded region. first, oligospawn can identify short oligos that are unique to each unigene in the database. second, it can select oligos that are popular among the unigenes. more precisely, a unique oligo is one that appears in one unigene but does not occur in any other, and a popular oligo is an oligo that occurs in the largest number of unigene sequences. typical applications of unique oligos are the design of pcr primers and the selection of probes for microarray studies. for bac library screening, the purpose of unique oligos is to have the means to unambiguously link each probe to its specific gene-bearing bac clones. the associated computational problem has been studied quite extensively, but practical implementations usually are based on the "all-against-all blast" strategy and hence very slow on large datasets. among the primer/probe design softwares, a partial list would contain primer, oligowiz, oligoarray, and probemer, soop, and overgo maker among others. in the context of bac library screening, the purpose of popular oligos is to identify the largest possible list of gene-bearing bac clones using the smallest possible number of probes. this strategy is aligned with the desire to economize the identification of what may be only a small portion of gene-bearing fragments from an entire genome. our interest in popular oligos arises from screening a large collection of bac clones for barley. it has been shown previously by a number of independent methods that the expressed genes in triticeae are concentrated in a small fraction of the total genome. in barley, this portion of the genome, often referred to as the gene-space, has been estimated to be only 12% of the total genome. if this is indeed true, then perhaps only 12%–20% of the clones in a typical bac library would carry expressed genes, and therefore also the vast majority of barley genes could be sequenced by focusing only on this portion of the genome. an efficient method to reveal the portion of bac clones derived from the gene-space has the potential for tremendous cost savings in the context of obtaining the sequences of the vast majority of barley genes. the same approach would potentially accelerate progress in many crop plants and other systems that are not being considered for whole-genome sequencing. popular overgos might not be appropriate when the objective is to obtain gene-specific results. however, when the objective is maximize the number of gene-bearing bacs found, then it is more cost-effective to use popular overgo rather than unique overgos. in addition to this, one cannot hope to design unique overgos for all the unigenes because, for example, of the presence of gene families. users must also be careful in using popular overgos in pooling strategies, since they might results in too many positives. the computational problem arising from the selection of popular oligos is an instance of a more general class of problems, called pattern discovery. several pattern discovery algorithms have been proposed in the literature and implemented in software tools. a few examples are meme, consensus, gibbssampler and verbumculus among others. although some of these tools are able to give very accurate results on datasets in the order of a few tens of kb, they collapse, typically for lack of primary memory, when asked to process very large datasets. oligospawn differs from other probe-finding and pattern discovery software in several important characteristics. the main advantages brought about by this tool are its speed and relatively low memory requirements for datasets in the range of unigenes and total bases that are typical of the entire transcribed sequence dataset from eukaryotic organisms. both algorithms have been carefully engineered to achieve satisfactory speeds on ordinary pcs. although the actual time is highly dependent on the parameters on which the algorithms are run, the execution of each of the algorithms on the barley unigene dataset typically takes just a few hours on a regular pc. the main algorithmic ideas behind the design of oligospawn were reported in previous publications. in this paper we report on the release of oligospawn, its usage and limitations. in addition, we present new criteria that were carefully hand-tuned to model the hybridization process. we also discuss in more detail the filtering steps and we report some preliminary biological experiments. implementation we initially based our oligo design algorithms on the length of bases, following the procedure of thomas et al., where 36-mer "overgo" probes were successfully used to screen several mammalian bac libraries. for 36-mer overgo probes, two 22-mers create the initial template for dna synthesis, overlapping in bases, leading to the production of a labeled probe. overgo 36-mers probes may anneal to genomic dna segments and produce a positive hybridization signal even if the 36-mer is not perfectly matched to consecutive bases in the target dna. in the extreme example, an overgo probe with consecutive perfect matches and a terminal mismatch would hybridize and produce a signal. similarly, an oligo with consecutive matches and terminal mismatches would also seem likely to hybridize. however an oligo with only consecutive matches and mismatches distributed evenly through the remaining bases would have a very decreased melting temperature and would not produce a signal under standard hybridization and washing conditions. dna sequencing primers generally are in the range of only 17– nucleotides, and a popular microarray format is based on 25-mers. these lengths are sufficient for annealing at moderate temperatures, yet not so long that non-perfect-matches are an overriding issue. considerations of non-perfectly-matched oligos have recently been described in the context of microarrays. unique oligos in order to increase the likelihood that a 36-mer is unique in the operational sense of hybridizing to only one gene in the genome, we allow no more than consecutive perfect matches, and we place a further requirement on the density of mismatches throughout the remainder of the 36-mer. the unique oligo problem is to identify 36-mers in the unigenes collection such that each 36-mer occurs exactly in one unigene and does not occur exactly or approximately in any other unigene. more specifically, based on the considerations above, we define a 36-mer p that occurs in a unigene sequence s to be unique if all the following conditions are satisfied • for any 16-mer x that occurs exactly in p, and any 16-mer y that does not occur exactly in s, h > • for any 20-mer x that occurs exactly in p, and any 20-mer y that does not occur exactly in s, h > • for any 24-mer x that occurs exactly in p, and any 24-mer y that does not occur exactly in s, h > • for any 30-mer x that occurs exactly in p, and any 30-mer y that does not occur exactly in s, h > • for any 36-mer x that occurs exactly in p, and any 36-mer y that does not occur exactly in s, h > where h denotes the the number of mismatches between two sequences x and y of equal length. our strategy to identify unique oligos first eliminates all the 36-mers that cannot be unique. the algorithm is based on the following observation. assume that we have two oligos of size l, which disagree in at most d positions, that is, there are at most d mismatches. then, they have to share a string of size l/ that contains at most one mismatch. we call substrings of this size the seeds. using this idea, we designed an efficient two-phase algorithm. in the first phase, we cluster all the possible seeds from the unigenes into groups such that within each group, a seed has no more than one mismatch with the other seeds. then, we extend the flanking regions of a seed, and check whether the extended 36-mer violates any of the above conditions. if so, the extended 36-mer is not unique. observe that we only need to compare 36-mers within a group because any two 36-mers extended from seeds in different groups are different enough that the conditions above would be immediately satisfied. popular oligos the popular oligo problem is the problem of finding all the 36-mers that appear in a sufficiently large number of unigene sequences. more precisely, we say that a 36-mer x matches another 36-mer y, if the following condition is true • x and y share a consecutive perfect match of nucleotides, called a core, and • either one of the following two conditions is satisfied - h < or - h = and * for any pair x', y' of 25-mers obtained by extending the core, h < and * for any pair x", y" of 30-mers obtained by extending the core, h < since popular oligos are not required to appear exactly in the unigene sequences, it would be too computationally expensive to find them by exhaustive enumeration. however, we can reduce the search space using the same idea as in the algorithm for unique oligos, except that here the role of seeds is played by the cores. first, we determine the popularity of the cores in the unigene dataset. a critical parameter here is the core threshold tc, which is the minimum number of unigenes in which the core should appear exactly to be declared popular. second, each popular core is extended to a 36-mer. then, each group of 36-mer is hierarchically clustered. based on the clustering tree, we compute the common oligos shared by the 36-mers by performing set intersection. these common oligos become candidate popular oligos. both algorithms combine heuristics and well-established algorithmic and data structuring techniques such as hashing, approximate string matching, and clustering. a more detailed explanation can be found in. an outline of the popular oligo algorithm is illustrated in figure filtering unsuitable candidates for both unique and popular oligos, we apply a filtering phase to discard unsuitable oligos based on gc content, melting temperatures, self-annealing of 36-mers, low-complexity, and the presence of repetitive regions. all these parameters can be adjusted by the user. the melting temperature tm is calculated using the formula in as implemented in primer. self-annealing of oligos is determined by performing an end-free sequence alignment between the 22-mer prefix and the reverse complement of the 22-mer suffix of an oligo. an oligo is discarded if the alignment score is higher than a predetermined threshold. we use the program dust to determine low-complexity regions in oligos. finally, oligospawn filters out those popular oligos that have significant matches against repeat database, e.g., triticeae repeat sequence database in the case of barley, or any other repeat database provided by the user. platforms and web interface the software oligospawn was developed using the gnu c++ compiler under the linux operating system. the executable for linux/i can be downloaded from the oligospawn website. the source code is also available from the same website under the gpl licence. any platform for which gnu c++ is available would be able to compile and run the stand-alone software. the web server is running at and it was developed using php, which is an open-source scripting language. the web server has been tested with netscape, mozilla, safari, and internet explorer. figure shows a screen shot of the web interface for the popular oligo tool, whereas figure shows how the output is displayed. for technical reasons, the web server does not allow inputs larger than megabases. if the dataset is bigger, we suggest the user either to install the software locally or to get in touch with one of the authors of this paper. usage the large majority of parameters on the website are self-explanatory. one of the parameters for the popular oligo, however, deserves a special discussion. the parameter is the threshold tc on the popularity of the cores. if one sets this parameter to a value v, he should expect each oligo produced by the tool to hit v or more unigenes of the dataset. although this property is not guaranteed, it should help the intuition in setting tc. the ideal output of the popular oligo tool is a set of oligos of the minimum cardinality that maximizes the number of unigenes hit by at least one oligo. as reported in decreasing the parameter tc has the effect of increasing both the number of oligos in the pool and the number of covered unigenes. however, by doing so the running time grows considerably. more importantly, the ratio of covered unigenes to oligos decreases as the threshold decreases. for a unigene set containing a few tens of thousands of unigenes we suggest that users start with a value of tc around and then progressively decrease tc until the desired coverage is attained. if tc is low, the running time could be in the order of a few tens of hours on a regular pc for a large unigene datasets. since the other parameters control the selection of the candidates, the stricter is their range, the faster the software will run. if the range is too small, it is possible that no oligo will be reported. users who choose to install the software locally will find a readme file in the archive explaining the compilation, installation and usage procedures. the two programs can be invoked as follows pop0ligo.exe unigene.fasta uniq0ligo.exe unigene.fasta the options for the two linux executables are reported in table for example $ pop0ligo.exe unigene.fasta -c -g -g -m -m -r trep.fasta will compute the popular oligos for the unigenes contained in the file unigene.fasta with tc= gc content between 45% and 55%, and melting temperature between 50°c and 80°c. the program will discard any oligo that matches a sequence in trep.fasta. the executable uniq0ligo.exe has a special option -t that allows the user to choose how many unique oligos to report for each unigene. if several oligo candidates are available for one unigene the program will report the requested number spread evenly across that unigene. the same parameters in table can be found on the web server.  in order to test and evaluate oligospawn, oligos were designed from the unigene set assembly # of harvest:barley. popular 36-mer oligos were generated by an older version of the software oligospawn with threshold tc = gc content in the range 45–56%. since the older version of oligospawn did not yet offer filtering against repeat databases this process was supplemented by some manual actions, as follows. oligos matching repetitive dna and rrna were filtered out with blast searches against trep and the tigr gramineae repeat databases. following this search, 36-mers with or more consecutive matches to repetitive sequences were discarded. out of initially proposed popular oligos, a total of were discarded by this method. all these filtering step are now included in oligospawn. the popular 36-mers were also "blasted" against the swissprot and nr protein databases for annotation purposes. the 36-mers with nine of twelve possible amino acids identical to the subject sequence were chosen for further testing. out of the initial popular 36-mers analyzed, passed this criterion. finally, popular oligos classified as transcription and signal transduction components, a total of out of these were used for probing the morex barley bac library. overgo hybridization overgo labeling and hybridization was done essentially as described by ross et al.. briefly, probes were radioactively labeled individually with 32p-datp and 32p-dctp. for background detection, a 36-mer representing the escherichia coli genome was also labeled. hybridization using a mixture of all probes was then performed on high-density filters of the × morex barley bac library, followed by washing and exposure to autoradiography film. an average of bag clones per filter were scored as positive, yielding a total of about positive bac clones from only popular overgos. screening with unique overgos would be expected to identify only about total clones. therefore, the popular oligos described above netted about times as many positive clones as would unique oligos. results with other sets of popular oligos not described in this manuscript have given comparable results. therefore, we conclude that the popular oligo algorithm provides a substantial gain of efficiency in probing bac genomics libraries for gene-containing clones. the number of positive bac clones identified with various pools sizes of unique oligos has consistently been in the range of to bacs per unique oligo. for example, pools of unique oligos repeatedly provide about to positive bac addresses. furthermore, checking the sequences of unique oligos with blast has consistently provided assurance that our unique oligo algorithm indeed is as selective as it is intended to be.  the development of oligospawn spanned a period of more than two years for conception, design, optimization, tuning, and several cycles of changes in the criteria used to model the hybridization of short oligos. before oligospawn the problem of finding popular oligos from typically large unigene datasets, as exist for barley and several other organisms, could not be solved efficiently using standard desktop computers. furthermore, most of the commonly used pattern discovery algorithms are not scalable to this level and therefore could not solve this problem using any computer configuration. although oligospawn uses several heuristics to speed up the computation and therefore cannot guarantee the optimality of the probe it produces, the experiments on the screening of the bac clone library for barley have demonstrated its effectiveness. one major limitation of oligospawn is that the length of the oligos is currently fixed at bases. it is straightforward to extend the algorithms to accommodate oligo lengths that are not too far from bases, and we are currently working on extending the software to allow the user to specify the oligo length. availability and requirement project name: oligospawn project homepage: operating system: linux programming languages: c++, php licence: gnu gpl any restriction to use by non-academics: no authors' contributions js and tc designed the specification of the overgos and the criteria to model the hybridization. jz, tj and sl designed the two algorithms. jz wrote and tested the software oligospawn. js and km performed the overgo labeling and hybridization experiments. all authors read and approved the final manuscript. 
oligospawn is a suite of software tools that offers two complementary services, namely the selection of "unique" oligos each of which appears in one unigene but does not occur in any other and the selection of "popular" oligos each of which occurs in as many unigenes as possible. the algorithms we designed are highly efficient and capable of processing unigene datasets of sizes on the order of several tens of mb in a few hours on a regular pc. in this paper, we describe the functionalities of oligospawn and the computational methods it employs, and we report on experimental results for the overgo probes designed with it. the software has been used to design overgo probes employed to screen a barley bac library.
 expressed sequence tag datasets represent perhaps the largest collection of genetic information. ests can be exploited in a variety of biological experiments and analysis. here we are interested in the design of overlapping oligonucleotide probes from large unigene datasets.  oligospawn is a suite of software tools that offers two complementary services, namely the selection of "unique" oligos each of which appears in one unigene but does not occur in any other and the selection of "popular" oligos each of which occurs in as many unigenes as possible. in this paper, we describe the functionalities of oligospawn and the computational methods it employs, and we report on experimental results for the overgo probes designed with it.  the algorithms we designed are highly efficient and capable of processing unigene datasets of sizes on the order of several tens of mb in a few hours on a regular pc. the software has been used to design overgo probes employed to screen a barley bac library. oligospawn is freely available at. 