BACKGROUND
recent developments in technology have led to the sequencing of many eukaryotic and prokaryotic organisms.
availability of these genomic sequences unlocked opportunities for the development of whole-genome-based diagnostic assays, such as dna microarrays and polymerase chain reaction  assays, which offer higher specificity than traditional methods based on a single gene or protein  <cit> .
because of their simplicity and efficiency, these assays are increasingly being used for various applications in medicine, environmental monitoring, and biodefense.
the popularity of these assays, in turn, triggered the development of different computational tools for sequence-based signature design  <cit> .
microarray-based pathogen diagnostic assays are gaining popularity due to their ability to test for hundreds, or even thousands, of pathogens in a single diagnostic test  <cit> .
wilson et al.
<cit>  used 50-thousand  <dig> mer overlapping oligonucleotides to detect  <dig> pathogens, wang et al.
<cit>  reported using a microarray with 11-thousand  <dig> mer oligonucleotides that can identify ≥  <dig> distinct viruses, while palacios et al.
<cit>  designed a panmicrobial microarray comprising nearly 30-thousand  <dig> mer probes.
current technology for custom microarray design enables up to  <dig> oligonucleotides per slide, while arrays with  <dig>  million probes are available for other high-throughput applications, such as comparative genome hybridization  <cit> .
the ability to simultaneously screen against a wide range of targets is essential for detecting biological threat agents in environmental samples, where there may be no prior knowledge about the specific pathogens likely to be present in the sample.
in terms of the computational problems, the design of microarray probes for pathogen identification is fundamentally different from the design of microarray probes for gene expression analysis.
an oligonucleotide probe designed for monitoring the expression of a gene should hybridize only to the mrna of the corresponding gene, and should not have any significant cross-hybridization with other mrnas from the same organism.
because all sequences involved are gene transcripts of a single organism, the combined length of the sequences is typically, at most, a few megabases.
the problem, though computationally intensive, can be handled by a single processor in less than an hour  <cit> .
many efficient computational tools have been developed for designing microarray probes for gene expression analysis  <cit> .
in contrast, oligonucleotide probes designed for pathogen diagnostic assays should hybridize only with the intended target and should not have any significant cross-hybridization with any nontarget genome.
this necessitates the comparison of each candidate probe against every available sequenced nontarget genome.
to date, the combined size of the nucleotide sequences in the national center for biotechnology information  nt database is greater than  <dig> gigabases and is bound to grow exponentially as more and more genomes are sequenced.
the amount of sequence data that need to be analyzed for each target pathogen is also increasing due to multiple strains of many pathogens being sequenced.
therefore, the sheer magnitude of the search space necessitates efficient high-throughput algorithms that both quickly scan large genomic databases and reduce the space to a small set of unique regions in the target genome.
in this paper, we present a software tool for identifying oligonucleotide fingerprints for microarray-based pathogen diagnostic assays.
the software, named tool for oligonucleotide fingerprint identification , is an integrated, scalable, high-performance-computing pipeline that combines genome comparison tools, probe design software, and sequence alignment programs in order to design highly specific microarray probes for a given target pathogen .
this pipeline , is an improvement over an earlier version of the pipeline , presented by tembe et al.
<cit> .
tofi-beta incorporates several optimizations and enhancements that significantly reduce the overall execution time of the pipeline, opening up possibilities for future extension of the system to design fingerprints common to a group of targets.
in addition, tofi-beta uses new, multiple criteria for estimating probe specificity, which, for any given genome, results in a considerable increase in the number of identified in silico fingerprints without increase in the  false-positive rate.
this is particularly important in cases where the target sequence is a close match to other sequences, where the larger number of in silico fingerprints increases the chance of identification of true fingerprints.
existing methods for design of pathogen diagnostic assays
one method to design probes is to select regions of the pathogen genome that are known to be associated with specific functions.
for example, specific genes of bacterial genomes, such as the 16s rrna gene  <cit> , virulence genes  <cit> , and antibiotic resistance genes  <cit> , have all been used to design microarray probes for species-level diagnostics.
another method to design probes is to employ the whole genome of the pathogen.
a few software tools/algorithms have been proposed to guide the design of whole-genome-based pathogen diagnostic assays  <cit> .
some of these tools are intended for microarray-based assays  <cit> , whereas others are intended for pcr-based assays  <cit> .
most of these tools, however, do not have the capability of testing for specificity against a large number of nontarget genomes; they are based on the assumption that the signatures need only be unique with respect to the host or a small set of nontarget sequences.
for instance, kaderali and schliep  <cit>  developed an algorithm that analyzes a set of input target sequences and designs a single probe for each target, with the probe being unique with respect to all other input sequences.
the uniqueness of the probe is determined by constructing a generalized suffix tree for all the input target sequences.
the method presented by putonti et al.
<cit>  designs probes that are unique with respect to a host organism.
both of these approaches are clearly not adequate if the signatures are to identify pathogens from environmental samples containing a multitude of nontarget organisms.
because, in general, there is no prior knowledge of the contaminants in a sample, the signatures have to be unique with respect to all known nontarget sequences.
the kpath pipeline for pcr assays  <cit>  is the seminal software that introduced the concept of in silico comparison against all known nontarget sequences.
insignia  <cit>  is another tool for designing pcr assays.
unlike the current version of tofi, which designs fingerprints for a single genome, both kpath and insignia have the ability to design fingerprints that are common to multiple target genomes.
to our knowledge, kpath and insignia are the only tools other than tofi  <cit>  that have the provision for in silico sequence-based testing for specificity against multiple nontarget genomes.
neither kpath nor insignia is applicable for designing microarray fingerprints, as the design and specificity requirements of microarray fingerprints are quite different from those of pcr signatures.
for example, the most commonly used pcr signatures consist of a probe and two primers, which, due to their short length  and constraints on the inter-primer distance, can tolerate inexact matches with nontarget sequences without much degradation in specificity.
conversely, in addition to being characterized by only one dna segment with no spacing constraints, microarray probes are generally longer and more susceptible to cross-hybridization even in the absence of an exact match  <cit> .
this requires more extensive searches, for both exact and inexact matches, against nontarget sequences to identify highly specific fingerprints for microarrays.
implementation
the tofi pipeline consists of the three main stages illustrated in figure  <dig>  the stages are designed so that large portions of the target genome are eliminated in the less-expensive two initial stages, and the computationally more expensive searches for specific fingerprints are performed over smaller regions of the target genome in the final stage.
the first stage uses the suffix-tree-based mummer  <cit>  program to perform pairwise comparisons of the target genome with each nontarget genome and eliminates regions in the target genome that have exact matches with one of the nontarget genomes.
the surviving regions of the target genome, called candidate sequences, are then passed on to the second stage of the pipeline.
given a pair of sequences, mummer finds all maximal matches that are at least as long as a threshold  between the two sequences.
tofi uses mummer to find these maximal matches, and eliminates regions in the target genome that are covered by these maximal matches.
the threshold to use for minmatch is calculated based on the specificity parameters supplied by the user.
this ensures that every segment of the target genome that is at least as long as the minimum probe length and satisfies the specificity parameters is part of a candidate sequence.
stage  <dig> identifies oligonucleotides of desired length from the candidate sequences that satisfy experimental conditions, such as melting temperature  and gc content.
tofi uses the oligonucleotide modeling platform  software  <cit>  to identify these oligonucleotides, also referred to here as probes.
omp uses the nearest neighbor hybridization model  <cit>  to calculate tm and to estimate if a probe forms any secondary structures that may prevent it from hybridizing to the target genome.
in the third and final stage of the pipeline, tofi performs a blast  <cit>  search against a local copy of the ncbi nt database for each probe.
the program uses mpiblast  <cit>  to run blast in parallel on multiple processors.
probes with alignments to nontarget genomes that exceed the specificity thresholds are eliminated, and the surviving probes become the in silico dna fingerprints for the target genome.
these probes are then subjected to experimental validation to test their sensitivity and specificity.
tofi-beta incorporates major modifications in the first and third stages of the pipeline to increase computational speed and enhance the specificity assessment of the fingerprints.
in the following, we compare tofi-beta and tofi-alpha and describe these improvements.
improvements in stage 1
in stage  <dig>  the major improvement in tofi-beta over tofi-alpha is the comparison of the target against multiple nontarget genomes for finding exact matches.
tofi-alpha only allows for comparison against a single nontarget sequence.
comparison against a single genome is effective in eliminating a large portion of the target genome when a closely-related, nontarget near-neighbor genome sequence is available.
however, when such a nontarget sequence is not available, too many candidate sequences are passed on to the later stages of the pipeline, which are computationally more expensive.
even when a closely-related, nontarget near-neighbor is available, comparisons against additional nontarget genomes is advantageous.
as stage  <dig> is relatively inexpensive, the additional time spent in this stage is offset by the much larger reduction in computation time in the later steps, yielding a very favorable trade-off in overall runtime.
potentially, the target genome could be compared with all nontarget sequences in the entire nt database.
as described by tembe et al.
<cit> , sequence comparisons for exact matches in stage  <dig> are performed using the nucmer module in mummer.
some modifications were required in tofi-beta, however, to avoid some performance issues when using a large database of nontarget sequences.
since the larger databases are too big for mummer, they are split into smaller databases and the target sequence is compared for exact matches against the smaller databases.
this procedure is parallelized in tofi-beta so that the target sequence is compared against a different set of nontarget sequences at each processor.
the results are then assembled and processed so that only unique regions of the target genome are passed on to the next stage.
improvements in stage 3
in stage  <dig>  each probe that is generated in stage  <dig> is screened for cross-hybridization against all available nontarget genome sequences in the nt database using blast  <cit> .
stage  <dig> is, by far, the most computationally expensive stage, which takes about 99% of the total runtime of tofi-alpha.
in tofi-alpha, stage  <dig> consists of a single step in which a blast search is performed for each probe against the complete nt database.
in contrast, as illustrated in figure  <dig>  the third stage in tofi-beta consists of multiple, hierarchical blast steps, with the computational cost of the blast searches increasing with the number of steps.
at each step, the oligonucleotide probes having significant alignments with nontarget sequences are removed, and only the surviving probes are passed on to the next, more expensive step.
in the first step, we use the pairwise blast program bl2seq to identify matches with a near-neighbor genome, and the probes that meet the specificity requirements are passed on to the subsequent steps.
in the absence of a near-neighbor genome, this step is bypassed.
the subsequent steps consist of a series of blast searches using blastn, where at each step the probes are queried against increasingly larger nucleotide databases of more distantly-related organisms to the target organism.
for example, when yersinia pestis is the target organism, the probes are first queried against databases consisting of sequences of proteobacteria, then all other bacteria, and finally the nt database.
because the time taken to perform a blast search increases with database size and a probe is more likely to match sequences of closely-related organisms, the strategy in tofi-beta is to perform relatively less expensive blast searches against small databases of related organisms first, eliminating many nonspecific probes before performing more comprehensive and costly blast searches.
the hierarchical sequence databases are manually constructed.
the probes that meet the specificity criteria in all blast steps are provided as the in silico dna fingerprints for the target organism.
improved specificity criteria
probes designed for pathogen identification have to be unique to the target organism, and should not cross-hybridize with any nontarget organism.
high sequence similarity between a probe and a nontarget sequence, apparent from the presence of good pairwise sequence alignments, is generally indicative of cross-hybridization between the two.
there are multiple criteria for determining the specificity of a probe: overall sequence similarity, contiguous matches, and predicted free energy have all been shown to be important measures of the potential for cross-hybridization  <cit> .
in addition to these criteria, we propose the use of near-contiguous matches  to measure probe specificity.
sequence similarity, i.e., the number of matches  in the alignment between two sequences, is one criterion for estimating cross-hybridization.
this criterion measures only the matching bases.
that is, it does not take into consideration how the matches are distributed in the alignment.
tofi-alpha uses the number of mismatches in the alignment, denoted by t, as the sole criterion for determining probe specificity.
however, when the probe length is variable, specifying the matching bases as a percentage of the probe length allows for a more consistent measure of similarity, as a single threshold can be used for various probe lengths.
the percentage of matching bases in the alignment between two sequences is commonly referred to as the identity of the two sequences.
in tofi-beta, we use sequence identity as one of several criteria for estimating cross-hybridization.
in order to incorporate contiguous and near-contiguous matches in determining probe specificity, we use a series of thresholds m <dig>  m <dig>  m <dig>  and m <dig>  where mi is the maximum length of a contiguous region in which the alignment between a probe and a nontarget sequence has  matches and i mismatches/insertions/deletions.
accordingly, m <dig> is the length of the longest stretch of contiguous matches between a probe and a nontarget genome.
the use of multiple criteria for specificity is deemed to yield a number of advantages.
first, other factors, apart from overall sequence identity, influence the hybridization of a probe to a nontarget sequence.
kane et al.
<cit>  performed empirical analysis on  <dig> mer oligonucleotides in order to measure, among other things, the effect of overall sequence identity and contiguous stretches of similarity on cross-hybridization.
they concluded that a probe is likely to cross-hybridize with a nontarget if overall sequence identity is > 75% or if there is a contiguous match >  <dig> bp.
li et al.
<cit>  also concluded that better specificity can be obtained by using multiple criteria, such as sequence identity, length of contiguous matches and hybridization energy.
second, the use of multiple criteria for specificity gives finer control; one can relax the threshold value for each individual criterion and yet obtain more in silico fingerprints with comparable specificity to fingerprints that can be obtained using a single criterion.
conversely, using a single criterion does not give much control over the specificity of the selected probes.
applying strict thresholds for a single criterion might result in missing many specific probes, whereas relaxing the thresholds may lead to too many nonspecific probes  <cit> .
an additional advantage is that using multiple specificity criteria, including contiguous matches, improves runtime.
the selection of specificity criteria affects the choice of the length of minimum exact matches in stage  <dig>  and using multiple criteria allows for the selection of a smaller threshold for minimum exact matches.
this selection results in fewer candidate sequences passing stage  <dig>  thereby improving the overall pipeline performance.
the thresholds m <dig>  m <dig>  and m <dig> help design robust fingerprints that are not affected by small variations in nontarget sequences.
using m <dig>  m <dig>  and m <dig> one can avoid situations in which a small number of mutations/insertions/deletions in a nontarget sequence might potentially lead to long stretches of contiguous matches between the probe and nontarget, causing the probe to cross-hybridize with the nontarget.
for instance, in the example shown in figure  <dig>  the probe does not have a very long stretch of contiguous matches with a nontarget, but rather a long near-contiguous match.
in this instance, the probe might cross-hybridize with the nontarget because of the long stretch of near-contiguous match.
the threshold m <dig> is particularly useful in avoiding regions around common single nucleotide polymorphisms between the target and nontarget genomes.
using free energy  for probe selection
li et al.
<cit>  have suggested that free energy  is an important measure of probe specificity.
however, computing the Δg between a probe and nontarget sequences involves traversing through each nontarget genome and computing Δg for each alignment with the probe.
given the large number of nontarget genomes and the relatively high computational cost of each Δg calculation, such an approach is not practical for the current application.
a more feasible strategy would be to obtain the blast hits for the probe and compute Δg against each significant hit.
however, even this strategy would be impractical, owing to the large number of fingerprints reported at the end of stage  <dig>  a feasible strategy is to perform the calculations only at the very final stage, after the probes have been screened using other specificity criteria.
hence, Δg estimation  is provided as an optional post-processing step in tofi-beta.
RESULTS
the tofi pipeline can design oligonucleotide probes of any length.
the results that we present here are for the design of variable-length probes with length varying from  <dig> to  <dig> bp.
the choice of probe length was solely based on the requirements of the downstream field-deployable microarray platform for which these probes are designed, and hence we do not attempt to find optimal probe lengths for pathogen identification.
in general, shorter probes result in better specificity, and longer probes result in better sensitivity  <cit> .
performance improvements
to compare runtimes of tofi-beta and tofi-alpha under similar conditions, we conducted tests with t as the only specificity criterion in both, although tofi-beta can make use of multiple specificity criteria as described above.
table  <dig> shows comparative runtimes for four different genomes with t =  <dig>  which is a practical threshold for probes with lengths between  <dig> and  <dig> bp.
it can be seen that tofi-beta is at least twice as fast as and almost as much as five times faster than tofi-alpha in all test cases.
the results in table  <dig> are representative of runs with other bacterial pathogens.
the runtimes are rounded off to the nearest hour.
all runs were carried out on  <dig> processors.
the performance gains obtained in tofi-beta are partly due to using more near-neighbor genomes in stage  <dig>  and partly due to using multiple hierarchical steps in the blast stage.
table  <dig> shows a stage-by-stage comparison for f. tularensis using  <dig> processors.
in this case, tofi-beta is nearly five times faster than tofi-alpha, where about half of the speedup is the result of using multiple nontarget genomes in stage  <dig>  the changes in stage  <dig> reduce the number of probes reaching stage  <dig> by 44%, from  <dig> in tofi-alpha to  <dig> in tofi-beta, where the additional time for carrying out these steps  is offset by the much larger reduction in computation time in stage  <dig> .
the rest of the gains in performance are the result of hierarchical filtering in the blast stage.
the initial and intermediate inexpensive blast steps eliminated  <dig> probes out of the  <dig> probes in less than two hours, which would have taken more than  <dig> hours if a single blast step were to be used as in tofi-alpha.
for both tofi-alpha and tofi-beta, t =  <dig> is used as the sole specificity criterion.
the optimum number of blast steps depends on many factors, including the size of the target genome, the availability of genomic sequences from closely-related, nontarget genomes, and the number of processors available.
based on empirical evidence obtained by running the pipeline for various bacterial genomes, we observe that the use of one intermediate blast step is optimal in reducing the overall runtime.
additional blast steps do not reduce the runtime significantly when a large number of processors  are available.
however, when a limited number of processors are available, using additional blast steps might be useful in reducing the overall runtime.
effect of multiple specificity criteria
case studies: francisella tularensis and yersinia pestis
in the following, we present a detailed comparative analysis of the number and specificity of fingerprints obtained by using individual versus multiple specificity criteria.
our aim is to consider all potential probes that satisfy the experimental constraints and evaluate the specificity criteria based on estimated Δg of these probes with nontarget genomes.
accordingly, we evaluated all the probes resulting from stage  <dig>  where in stage  <dig> we compared the target with a single near-neighbor genome using an exact match threshold of  <dig> bp.
the results presented here are for f. tularensis schu s <dig>  and y. pestis co <dig> .
a contig from f. philomiragia atcc  <dig>  <cit>  was used as the near-neighbor for f. tularensis, and y. pseudotuberculosis ip  <dig>  was used as the near-neighbor for y. pestis.
probe design on the candidate sequences, taking into consideration the experimental constraints , yielded a total of  <dig> probes for f. tularensis and  <dig> probes for y. pestis.
blast searches were performed on these probes against the entire nt database downloaded from ncbi in july  <dig>  blast hits with the corresponding targets and synthetic constructs were ignored.
the remaining blast hits were extended on either side by  <dig> bp, and Δg with the corresponding probe was estimated using the simulation feature of the omp software.
for each probe, the largest negative Δg value among all blast hits was taken as a conservative measure of cross-hybridization between the probe and a nontarget sequence.
the probes are categorized into good, bad, or gray based on their Δg values, as actual experimental hybridization results are not available for these probes.
good probes are expected to have little or no cross-hybridization with nontarget genomes, bad probes are expected to have significant cross-hybridization, and the behavior of gray probes is too uncertain to categorize either way.
estimated Δg should not, however, be construed as a substitute for experimental hybridization tests.
we heuristically selected well-spaced Δg thresholds for good and bad probes in order to assess the relative performance of the different specificity criteria.
probes with Δg greater than or equal to - <dig> kcal/mol are categorized as good probes.
this threshold was selected because it corresponds to about 50% of the mean Δg between a probe and its complement, which is the approximate ratio recommended for  <dig> mers  <cit> .
probes with Δg less than - <dig> kcal/mol  are considered as bad probes.
the probes with Δg between - <dig> and - <dig> kcal/mol are labeled as gray probes.
further increase in separation between good and bad probes is not convenient because it reduces the sample size for comparative assessment.
f. tularensis
y. pestis
discussion
effect of database size on specificity thresholds
the size of the target genome and the size of the database of nontarget sequences affect the selection of thresholds for contiguous and near-contiguous matches.
for the size of target genomes and nontarget databases used in this paper, m <dig> =  <dig> appears to be an appropriate threshold, resulting in sufficient number of fingerprints for all the genomes in table  <dig>  however, as more and more nontarget sequences become available, it might not be possible to find unique  <dig> mers.
reed et al.
<cit>  present a model to estimate the quality of a probe based on the size of the database of nontarget sequences.
according to this model, the probability of finding a unique  <dig> mer is close to zero when the size of database is  <dig> gb.
as the size of sequence databases is quickly approaching this number, it might be necessary to use higher thresholds for m <dig> and other specificity parameters.
limitations of using blast
even though blast is among the best methods for sequence comparisons against large databases like the nt database, blast has its limitations.
blast is a heuristic approach that first finds short, exact, "anchor" matches and extends the alignments around these exact matches.
the size of these exact matches, termed word size, is given by the input parameter w. in the blastn program, used for blast searches against large sequence databases, the default value for w is  <dig> and the smallest possible value w can take is  <dig>  because every match reported by blast must include an exact match of length w, it imposes a lower bound on the values of the specificity thresholds m <dig>  m <dig>  m <dig>  and m <dig>  for any given w, the smallest near-contiguous match with i mismatches that can be guaranteed to be reported by blast is given by w, therefore, the minimum allowable value for any mi is w- <dig>  accordingly, the lowest thresholds of m <dig>  m <dig>  and m <dig> for w =  <dig> are  <dig>   <dig>  and  <dig>  respectively.
using lower thresholds for mi could result in some near contiguous matches of length mi not being reported by blast.
errors in sequence databases
tofi currently uses the description provided in the header line of a fasta sequence to determine if the sequence is a target or a nontarget sequence.
typographical errors or missing information in the ncbi sequence data can sometimes cause tofi to treat a sequence from a target organism as a nontarget sequence, which can potentially lead to removal of good fingerprints.
the fingerprints designed by tofi can only be as accurate as the sequence databases used for comparisons with nontarget sequences.
however, identifying the errors and removing low-quality data from sequence databases is beyond the scope of the tofi framework.
the only complete solution for handling errors in sequence data is to use manually curated sequence databases that contain only high-quality sequences with accurate sequence descriptions.
extension to multiple genomes
the performance improvements in tofi-beta pave the way for extending the pipeline to design probes common to a group of target genomes, e.g., multiple strains of a species and multiple species of a genus.
the identification of common fingerprints is a more computationally intensive problem, as it requires the simultaneous analyses of multiple target genomes.
in the future, we will extend the software pipeline to design sets of fingerprints common to multiple targets and sets unique to each target, taking maximum advantage of the shared sequences among the multiple genomes in order to reduce the overall computation time.
CONCLUSIONS
the enhanced pipeline incorporates major algorithmic improvements, resulting in performance that is nearly up to five-times faster than the previous version of the pipeline.
the use of multiple specificity criteria provides finer control over the number of resulting fingerprints.
this is helpful in obtaining a larger number of in silico fingerprints than those obtained using individual criteria, and may be essential for the following three reasons:  as more and more genomic sequences become available, there will be significant fingerprint erosion; matches with the newly available sequences will eliminate some fingerprints,  certain near-neighbor organisms may have very similar sequences, so, in these cases, obtaining a larger number of potential in silico fingerprints for experimental testing would be desirable, and  due to the noisy nature of microarray experiments, redundancy is essential for confidence in the results.
therefore, it is desirable to start with a sufficiently large number of in silico fingerprints, and identify specific fingerprints based on experimental results with the target and a panel of nontarget sequences.
availability and requirements
• project name: tofi
• project home page:
• operating systems: linux
• programming language: perl
• other requirements: mpiblast  <dig> .
<dig> or higher, mummer  <dig>  or higher, and omp developer edition
authors' contributions
rvs conceived and implemented the algorithmic improvements in tofi-beta.
kk developed the user interface for tofi-beta and modules for running omp.
nz analyzed the simulation data for specificity threshold selection.
jr conceived the project and provided overall project guidance.
rvs, nz and jr were the main writers of the manuscript.

 recent developments in technology have led to the sequencing of many eukaryotic and prokaryotic organisms. availability of these genomic sequences unlocked opportunities for the development of whole-genome-based diagnostic assays, such as dna microarrays and polymerase chain reaction assays, which offer higher specificity than traditional methods based on a single gene or protein. because of their simplicity and efficiency, these assays are increasingly being used for various applications in medicine, environmental monitoring, and biodefense. the popularity of these assays, in turn, triggered the development of different computational tools for sequence-based signature design. microarray-based pathogen diagnostic assays are gaining popularity due to their ability to test for hundreds, or even thousands, of pathogens in a single diagnostic test. wilson et al. used 50-thousand mer overlapping oligonucleotides to detect pathogens, wang et al. reported using a microarray with 11-thousand mer oligonucleotides that can identify ≥ distinct viruses, while palacios et al. designed a panmicrobial microarray comprising nearly 30-thousand mer probes. current technology for custom microarray design enables up to oligonucleotides per slide, while arrays with million probes are available for other high-throughput applications, such as comparative genome hybridization. the ability to simultaneously screen against a wide range of targets is essential for detecting biological threat agents in environmental samples, where there may be no prior knowledge about the specific pathogens likely to be present in the sample. in terms of the computational problems, the design of microarray probes for pathogen identification is fundamentally different from the design of microarray probes for gene expression analysis. an oligonucleotide probe designed for monitoring the expression of a gene should hybridize only to the mrna of the corresponding gene, and should not have any significant cross-hybridization with other mrnas from the same organism. because all sequences involved are gene transcripts of a single organism, the combined length of the sequences is typically, at most, a few megabases. the problem, though computationally intensive, can be handled by a single processor in less than an hour. many efficient computational tools have been developed for designing microarray probes for gene expression analysis. in contrast, oligonucleotide probes designed for pathogen diagnostic assays should hybridize only with the intended target and should not have any significant cross-hybridization with any nontarget genome. this necessitates the comparison of each candidate probe against every available sequenced nontarget genome. to date, the combined size of the nucleotide sequences in the national center for biotechnology information nt database is greater than gigabases and is bound to grow exponentially as more and more genomes are sequenced. the amount of sequence data that need to be analyzed for each target pathogen is also increasing due to multiple strains of many pathogens being sequenced. therefore, the sheer magnitude of the search space necessitates efficient high-throughput algorithms that both quickly scan large genomic databases and reduce the space to a small set of unique regions in the target genome. in this paper, we present a software tool for identifying oligonucleotide fingerprints for microarray-based pathogen diagnostic assays. the software, named tool for oligonucleotide fingerprint identification, is an integrated, scalable, high-performance-computing pipeline that combines genome comparison tools, probe design software, and sequence alignment programs in order to design highly specific microarray probes for a given target pathogen. this pipeline, is an improvement over an earlier version of the pipeline, presented by tembe et al.. tofi-beta incorporates several optimizations and enhancements that significantly reduce the overall execution time of the pipeline, opening up possibilities for future extension of the system to design fingerprints common to a group of targets. in addition, tofi-beta uses new, multiple criteria for estimating probe specificity, which, for any given genome, results in a considerable increase in the number of identified in silico fingerprints without increase in the false-positive rate. this is particularly important in cases where the target sequence is a close match to other sequences, where the larger number of in silico fingerprints increases the chance of identification of true fingerprints. existing methods for design of pathogen diagnostic assays one method to design probes is to select regions of the pathogen genome that are known to be associated with specific functions. for example, specific genes of bacterial genomes, such as the 16s rrna gene, virulence genes, and antibiotic resistance genes, have all been used to design microarray probes for species-level diagnostics. another method to design probes is to employ the whole genome of the pathogen. a few software tools/algorithms have been proposed to guide the design of whole-genome-based pathogen diagnostic assays. some of these tools are intended for microarray-based assays, whereas others are intended for pcr-based assays. most of these tools, however, do not have the capability of testing for specificity against a large number of nontarget genomes; they are based on the assumption that the signatures need only be unique with respect to the host or a small set of nontarget sequences. for instance, kaderali and schliep developed an algorithm that analyzes a set of input target sequences and designs a single probe for each target, with the probe being unique with respect to all other input sequences. the uniqueness of the probe is determined by constructing a generalized suffix tree for all the input target sequences. the method presented by putonti et al. designs probes that are unique with respect to a host organism. both of these approaches are clearly not adequate if the signatures are to identify pathogens from environmental samples containing a multitude of nontarget organisms. because, in general, there is no prior knowledge of the contaminants in a sample, the signatures have to be unique with respect to all known nontarget sequences. the kpath pipeline for pcr assays is the seminal software that introduced the concept of in silico comparison against all known nontarget sequences. insignia is another tool for designing pcr assays. unlike the current version of tofi, which designs fingerprints for a single genome, both kpath and insignia have the ability to design fingerprints that are common to multiple target genomes. to our knowledge, kpath and insignia are the only tools other than tofi that have the provision for in silico sequence-based testing for specificity against multiple nontarget genomes. neither kpath nor insignia is applicable for designing microarray fingerprints, as the design and specificity requirements of microarray fingerprints are quite different from those of pcr signatures. for example, the most commonly used pcr signatures consist of a probe and two primers, which, due to their short length and constraints on the inter-primer distance, can tolerate inexact matches with nontarget sequences without much degradation in specificity. conversely, in addition to being characterized by only one dna segment with no spacing constraints, microarray probes are generally longer and more susceptible to cross-hybridization even in the absence of an exact match. this requires more extensive searches, for both exact and inexact matches, against nontarget sequences to identify highly specific fingerprints for microarrays. implementation the tofi pipeline consists of the three main stages illustrated in figure the stages are designed so that large portions of the target genome are eliminated in the less-expensive two initial stages, and the computationally more expensive searches for specific fingerprints are performed over smaller regions of the target genome in the final stage. the first stage uses the suffix-tree-based mummer program to perform pairwise comparisons of the target genome with each nontarget genome and eliminates regions in the target genome that have exact matches with one of the nontarget genomes. the surviving regions of the target genome, called candidate sequences, are then passed on to the second stage of the pipeline. given a pair of sequences, mummer finds all maximal matches that are at least as long as a threshold between the two sequences. tofi uses mummer to find these maximal matches, and eliminates regions in the target genome that are covered by these maximal matches. the threshold to use for minmatch is calculated based on the specificity parameters supplied by the user. this ensures that every segment of the target genome that is at least as long as the minimum probe length and satisfies the specificity parameters is part of a candidate sequence. stage identifies oligonucleotides of desired length from the candidate sequences that satisfy experimental conditions, such as melting temperature and gc content. tofi uses the oligonucleotide modeling platform software to identify these oligonucleotides, also referred to here as probes. omp uses the nearest neighbor hybridization model to calculate tm and to estimate if a probe forms any secondary structures that may prevent it from hybridizing to the target genome. in the third and final stage of the pipeline, tofi performs a blast search against a local copy of the ncbi nt database for each probe. the program uses mpiblast to run blast in parallel on multiple processors. probes with alignments to nontarget genomes that exceed the specificity thresholds are eliminated, and the surviving probes become the in silico dna fingerprints for the target genome. these probes are then subjected to experimental validation to test their sensitivity and specificity. tofi-beta incorporates major modifications in the first and third stages of the pipeline to increase computational speed and enhance the specificity assessment of the fingerprints. in the following, we compare tofi-beta and tofi-alpha and describe these improvements. improvements in stage 1 in stage the major improvement in tofi-beta over tofi-alpha is the comparison of the target against multiple nontarget genomes for finding exact matches. tofi-alpha only allows for comparison against a single nontarget sequence. comparison against a single genome is effective in eliminating a large portion of the target genome when a closely-related, nontarget near-neighbor genome sequence is available. however, when such a nontarget sequence is not available, too many candidate sequences are passed on to the later stages of the pipeline, which are computationally more expensive. even when a closely-related, nontarget near-neighbor is available, comparisons against additional nontarget genomes is advantageous. as stage is relatively inexpensive, the additional time spent in this stage is offset by the much larger reduction in computation time in the later steps, yielding a very favorable trade-off in overall runtime. potentially, the target genome could be compared with all nontarget sequences in the entire nt database. as described by tembe et al., sequence comparisons for exact matches in stage are performed using the nucmer module in mummer. some modifications were required in tofi-beta, however, to avoid some performance issues when using a large database of nontarget sequences. since the larger databases are too big for mummer, they are split into smaller databases and the target sequence is compared for exact matches against the smaller databases. this procedure is parallelized in tofi-beta so that the target sequence is compared against a different set of nontarget sequences at each processor. the results are then assembled and processed so that only unique regions of the target genome are passed on to the next stage. improvements in stage 3 in stage each probe that is generated in stage is screened for cross-hybridization against all available nontarget genome sequences in the nt database using blast. stage is, by far, the most computationally expensive stage, which takes about 99% of the total runtime of tofi-alpha. in tofi-alpha, stage consists of a single step in which a blast search is performed for each probe against the complete nt database. in contrast, as illustrated in figure the third stage in tofi-beta consists of multiple, hierarchical blast steps, with the computational cost of the blast searches increasing with the number of steps. at each step, the oligonucleotide probes having significant alignments with nontarget sequences are removed, and only the surviving probes are passed on to the next, more expensive step. in the first step, we use the pairwise blast program bl2seq to identify matches with a near-neighbor genome, and the probes that meet the specificity requirements are passed on to the subsequent steps. in the absence of a near-neighbor genome, this step is bypassed. the subsequent steps consist of a series of blast searches using blastn, where at each step the probes are queried against increasingly larger nucleotide databases of more distantly-related organisms to the target organism. for example, when yersinia pestis is the target organism, the probes are first queried against databases consisting of sequences of proteobacteria, then all other bacteria, and finally the nt database. because the time taken to perform a blast search increases with database size and a probe is more likely to match sequences of closely-related organisms, the strategy in tofi-beta is to perform relatively less expensive blast searches against small databases of related organisms first, eliminating many nonspecific probes before performing more comprehensive and costly blast searches. the hierarchical sequence databases are manually constructed. the probes that meet the specificity criteria in all blast steps are provided as the in silico dna fingerprints for the target organism. improved specificity criteria probes designed for pathogen identification have to be unique to the target organism, and should not cross-hybridize with any nontarget organism. high sequence similarity between a probe and a nontarget sequence, apparent from the presence of good pairwise sequence alignments, is generally indicative of cross-hybridization between the two. there are multiple criteria for determining the specificity of a probe: overall sequence similarity, contiguous matches, and predicted free energy have all been shown to be important measures of the potential for cross-hybridization. in addition to these criteria, we propose the use of near-contiguous matches to measure probe specificity. sequence similarity, i.e., the number of matches in the alignment between two sequences, is one criterion for estimating cross-hybridization. this criterion measures only the matching bases. that is, it does not take into consideration how the matches are distributed in the alignment. tofi-alpha uses the number of mismatches in the alignment, denoted by t, as the sole criterion for determining probe specificity. however, when the probe length is variable, specifying the matching bases as a percentage of the probe length allows for a more consistent measure of similarity, as a single threshold can be used for various probe lengths. the percentage of matching bases in the alignment between two sequences is commonly referred to as the identity of the two sequences. in tofi-beta, we use sequence identity as one of several criteria for estimating cross-hybridization. in order to incorporate contiguous and near-contiguous matches in determining probe specificity, we use a series of thresholds m m m and m where mi is the maximum length of a contiguous region in which the alignment between a probe and a nontarget sequence has matches and i mismatches/insertions/deletions. accordingly, m is the length of the longest stretch of contiguous matches between a probe and a nontarget genome. the use of multiple criteria for specificity is deemed to yield a number of advantages. first, other factors, apart from overall sequence identity, influence the hybridization of a probe to a nontarget sequence. kane et al. performed empirical analysis on mer oligonucleotides in order to measure, among other things, the effect of overall sequence identity and contiguous stretches of similarity on cross-hybridization. they concluded that a probe is likely to cross-hybridize with a nontarget if overall sequence identity is > 75% or if there is a contiguous match > bp. li et al. also concluded that better specificity can be obtained by using multiple criteria, such as sequence identity, length of contiguous matches and hybridization energy. second, the use of multiple criteria for specificity gives finer control; one can relax the threshold value for each individual criterion and yet obtain more in silico fingerprints with comparable specificity to fingerprints that can be obtained using a single criterion. conversely, using a single criterion does not give much control over the specificity of the selected probes. applying strict thresholds for a single criterion might result in missing many specific probes, whereas relaxing the thresholds may lead to too many nonspecific probes. an additional advantage is that using multiple specificity criteria, including contiguous matches, improves runtime. the selection of specificity criteria affects the choice of the length of minimum exact matches in stage and using multiple criteria allows for the selection of a smaller threshold for minimum exact matches. this selection results in fewer candidate sequences passing stage thereby improving the overall pipeline performance. the thresholds m m and m help design robust fingerprints that are not affected by small variations in nontarget sequences. using m m and m one can avoid situations in which a small number of mutations/insertions/deletions in a nontarget sequence might potentially lead to long stretches of contiguous matches between the probe and nontarget, causing the probe to cross-hybridize with the nontarget. for instance, in the example shown in figure the probe does not have a very long stretch of contiguous matches with a nontarget, but rather a long near-contiguous match. in this instance, the probe might cross-hybridize with the nontarget because of the long stretch of near-contiguous match. the threshold m is particularly useful in avoiding regions around common single nucleotide polymorphisms between the target and nontarget genomes. using free energy for probe selection li et al. have suggested that free energy is an important measure of probe specificity. however, computing the Δg between a probe and nontarget sequences involves traversing through each nontarget genome and computing Δg for each alignment with the probe. given the large number of nontarget genomes and the relatively high computational cost of each Δg calculation, such an approach is not practical for the current application. a more feasible strategy would be to obtain the blast hits for the probe and compute Δg against each significant hit. however, even this strategy would be impractical, owing to the large number of fingerprints reported at the end of stage a feasible strategy is to perform the calculations only at the very final stage, after the probes have been screened using other specificity criteria. hence, Δg estimation is provided as an optional post-processing step in tofi-beta.  the tofi pipeline can design oligonucleotide probes of any length. the results that we present here are for the design of variable-length probes with length varying from to bp. the choice of probe length was solely based on the requirements of the downstream field-deployable microarray platform for which these probes are designed, and hence we do not attempt to find optimal probe lengths for pathogen identification. in general, shorter probes result in better specificity, and longer probes result in better sensitivity. performance improvements to compare runtimes of tofi-beta and tofi-alpha under similar conditions, we conducted tests with t as the only specificity criterion in both, although tofi-beta can make use of multiple specificity criteria as described above. table shows comparative runtimes for four different genomes with t = which is a practical threshold for probes with lengths between and bp. it can be seen that tofi-beta is at least twice as fast as and almost as much as five times faster than tofi-alpha in all test cases. the results in table are representative of runs with other bacterial pathogens. the runtimes are rounded off to the nearest hour. all runs were carried out on processors. the performance gains obtained in tofi-beta are partly due to using more near-neighbor genomes in stage and partly due to using multiple hierarchical steps in the blast stage. table shows a stage-by-stage comparison for f. tularensis using processors. in this case, tofi-beta is nearly five times faster than tofi-alpha, where about half of the speedup is the result of using multiple nontarget genomes in stage the changes in stage reduce the number of probes reaching stage by 44%, from in tofi-alpha to in tofi-beta, where the additional time for carrying out these steps is offset by the much larger reduction in computation time in stage. the rest of the gains in performance are the result of hierarchical filtering in the blast stage. the initial and intermediate inexpensive blast steps eliminated probes out of the probes in less than two hours, which would have taken more than hours if a single blast step were to be used as in tofi-alpha. for both tofi-alpha and tofi-beta, t = is used as the sole specificity criterion. the optimum number of blast steps depends on many factors, including the size of the target genome, the availability of genomic sequences from closely-related, nontarget genomes, and the number of processors available. based on empirical evidence obtained by running the pipeline for various bacterial genomes, we observe that the use of one intermediate blast step is optimal in reducing the overall runtime. additional blast steps do not reduce the runtime significantly when a large number of processors are available. however, when a limited number of processors are available, using additional blast steps might be useful in reducing the overall runtime. effect of multiple specificity criteria case studies: francisella tularensis and yersinia pestis in the following, we present a detailed comparative analysis of the number and specificity of fingerprints obtained by using individual versus multiple specificity criteria. our aim is to consider all potential probes that satisfy the experimental constraints and evaluate the specificity criteria based on estimated Δg of these probes with nontarget genomes. accordingly, we evaluated all the probes resulting from stage where in stage we compared the target with a single near-neighbor genome using an exact match threshold of bp. the results presented here are for f. tularensis schu s and y. pestis co. a contig from f. philomiragia atcc was used as the near-neighbor for f. tularensis, and y. pseudotuberculosis ip was used as the near-neighbor for y. pestis. probe design on the candidate sequences, taking into consideration the experimental constraints, yielded a total of probes for f. tularensis and probes for y. pestis. blast searches were performed on these probes against the entire nt database downloaded from ncbi in july blast hits with the corresponding targets and synthetic constructs were ignored. the remaining blast hits were extended on either side by bp, and Δg with the corresponding probe was estimated using the simulation feature of the omp software. for each probe, the largest negative Δg value among all blast hits was taken as a conservative measure of cross-hybridization between the probe and a nontarget sequence. the probes are categorized into good, bad, or gray based on their Δg values, as actual experimental hybridization results are not available for these probes. good probes are expected to have little or no cross-hybridization with nontarget genomes, bad probes are expected to have significant cross-hybridization, and the behavior of gray probes is too uncertain to categorize either way. estimated Δg should not, however, be construed as a substitute for experimental hybridization tests. we heuristically selected well-spaced Δg thresholds for good and bad probes in order to assess the relative performance of the different specificity criteria. probes with Δg greater than or equal to - kcal/mol are categorized as good probes. this threshold was selected because it corresponds to about 50% of the mean Δg between a probe and its complement, which is the approximate ratio recommended for mers. probes with Δg less than - kcal/mol are considered as bad probes. the probes with Δg between - and - kcal/mol are labeled as gray probes. further increase in separation between good and bad probes is not convenient because it reduces the sample size for comparative assessment. f. tularensis y. pestis discussion effect of database size on specificity thresholds the size of the target genome and the size of the database of nontarget sequences affect the selection of thresholds for contiguous and near-contiguous matches. for the size of target genomes and nontarget databases used in this paper, m = appears to be an appropriate threshold, resulting in sufficient number of fingerprints for all the genomes in table however, as more and more nontarget sequences become available, it might not be possible to find unique mers. reed et al. present a model to estimate the quality of a probe based on the size of the database of nontarget sequences. according to this model, the probability of finding a unique mer is close to zero when the size of database is gb. as the size of sequence databases is quickly approaching this number, it might be necessary to use higher thresholds for m and other specificity parameters. limitations of using blast even though blast is among the best methods for sequence comparisons against large databases like the nt database, blast has its limitations. blast is a heuristic approach that first finds short, exact, "anchor" matches and extends the alignments around these exact matches. the size of these exact matches, termed word size, is given by the input parameter w. in the blastn program, used for blast searches against large sequence databases, the default value for w is and the smallest possible value w can take is because every match reported by blast must include an exact match of length w, it imposes a lower bound on the values of the specificity thresholds m m m and m for any given w, the smallest near-contiguous match with i mismatches that can be guaranteed to be reported by blast is given by w, therefore, the minimum allowable value for any mi is w- accordingly, the lowest thresholds of m m and m for w = are and respectively. using lower thresholds for mi could result in some near contiguous matches of length mi not being reported by blast. errors in sequence databases tofi currently uses the description provided in the header line of a fasta sequence to determine if the sequence is a target or a nontarget sequence. typographical errors or missing information in the ncbi sequence data can sometimes cause tofi to treat a sequence from a target organism as a nontarget sequence, which can potentially lead to removal of good fingerprints. the fingerprints designed by tofi can only be as accurate as the sequence databases used for comparisons with nontarget sequences. however, identifying the errors and removing low-quality data from sequence databases is beyond the scope of the tofi framework. the only complete solution for handling errors in sequence data is to use manually curated sequence databases that contain only high-quality sequences with accurate sequence descriptions. extension to multiple genomes the performance improvements in tofi-beta pave the way for extending the pipeline to design probes common to a group of target genomes, e.g., multiple strains of a species and multiple species of a genus. the identification of common fingerprints is a more computationally intensive problem, as it requires the simultaneous analyses of multiple target genomes. in the future, we will extend the software pipeline to design sets of fingerprints common to multiple targets and sets unique to each target, taking maximum advantage of the shared sequences among the multiple genomes in order to reduce the overall computation time.  the enhanced pipeline incorporates major algorithmic improvements, resulting in performance that is nearly up to five-times faster than the previous version of the pipeline. the use of multiple specificity criteria provides finer control over the number of resulting fingerprints. this is helpful in obtaining a larger number of in silico fingerprints than those obtained using individual criteria, and may be essential for the following three reasons: as more and more genomic sequences become available, there will be significant fingerprint erosion; matches with the newly available sequences will eliminate some fingerprints, certain near-neighbor organisms may have very similar sequences, so, in these cases, obtaining a larger number of potential in silico fingerprints for experimental testing would be desirable, and due to the noisy nature of microarray experiments, redundancy is essential for confidence in the results. therefore, it is desirable to start with a sufficiently large number of in silico fingerprints, and identify specific fingerprints based on experimental results with the target and a panel of nontarget sequences. availability and requirements • project name: tofi • project home page: • operating systems: linux • programming language: perl • other requirements: mpiblast. or higher, mummer or higher, and omp developer edition authors' contributions rvs conceived and implemented the algorithmic improvements in tofi-beta. kk developed the user interface for tofi-beta and modules for running omp. nz analyzed the simulation data for specificity threshold selection. jr conceived the project and provided overall project guidance. rvs, nz and jr were the main writers of the manuscript. 
the improvements in specificity assessment, based on multiple specificity criteria, result in robust and consistent evaluation of cross-hybridization with nontarget sequences. in addition, the multiple criteria provide finer control on the number of resulting fingerprints, which helps in obtaining a larger number of fingerprints with high specificity. simulation tests for francisella tularensis and yersinia pestis, using a well-established hybridization model to estimate cross-hybridization with nontarget sequences, show that the improved specificity criteria yield a larger number of fingerprints as compared to using a single specificity criterion. the design process is implemented in a high-performance computing software pipeline that incorporates major algorithmic improvements over a previous version to both reduce computation time and improve specificity assessment. the faster runtimes, achieved as the result of algorithmic improvements, are critical for extending the pipeline to process multiple target genomes. the algorithmic improvements result in significant reduction in runtimes, with the updated pipeline being nearly up to five-times faster than the previous version. we present a methodology for high-throughput design of oligonucleotide fingerprints for microarray-based pathogen diagnostic assays. the oligonucleotide fingerprints, or dna microarray probes, are designed for identifying target organisms in environmental or clinical samples.
 we present a methodology for high-throughput design of oligonucleotide fingerprints for microarray-based pathogen diagnostic assays. the oligonucleotide fingerprints, or dna microarray probes, are designed for identifying target organisms in environmental or clinical samples. the design process is implemented in a high-performance computing software pipeline that incorporates major algorithmic improvements over a previous version to both reduce computation time and improve specificity assessment.  the algorithmic improvements result in significant reduction in runtimes, with the updated pipeline being nearly up to five-times faster than the previous version. the improvements in specificity assessment, based on multiple specificity criteria, result in robust and consistent evaluation of cross-hybridization with nontarget sequences. in addition, the multiple criteria provide finer control on the number of resulting fingerprints, which helps in obtaining a larger number of fingerprints with high specificity. simulation tests for francisella tularensis and yersinia pestis, using a well-established hybridization model to estimate cross-hybridization with nontarget sequences, show that the improved specificity criteria yield a larger number of fingerprints as compared to using a single specificity criterion.  the faster runtimes, achieved as the result of algorithmic improvements, are critical for extending the pipeline to process multiple target genomes. the larger numbers of identified fingerprints, obtained by considering broader specificity criteria, are essential for designing probes for hard-to-distinguish target sequences. 