BACKGROUND
microarrays are well known for their success in studying gene expression  <cit> .
as one of their many other roles, dna microarrays can also be used to characterize both large-scale and small-scale genetic variations.
for instance, array comparative genomic hybridization  is commonly used in human cancer studies to genotype cell lines by detecting gene loss and copy number variations  <cit> .
at a finer resolution, microarrays are also used to detect single nucleotide polymorphisms at targeted loci  <cit> .
in addition to human screens, microarrays have been widely used for the detection and genotyping of microbial species.
notably, a viral genotyping microarray  <cit>  was one of the methods used to etiologically link severe acute respiratory syndrome  to a novel coronavirus  <cit> .
arrays for the detection and comparative analysis of bacterial genomes have also been developed, including arrays for listeria monocytogenes  <cit> , and many other bacterial species.
however, these earlier, low-density arrays did not contain enough probes to target the entire genome of the bacterium, and were forced to probe only a small subset of the known genes.
as the density of dna microarrays increased in recent years, it has become possible to probe the entire genome of an organism in addition to only specific genes.
an array providing unbiased coverage of probes across a genome is commonly referred to as a whole-genome tiling array.
such arrays have been very successful for genome-scale analysis, including the discovery of novel transcripts, splicing variants, protein binding sites, and polymorphisms  <cit> .
depending on the offset between adjacent probe locations, whole-genome tilings can be either gapped, end-to-end, or overlapping .
in the human genome, tiling arrays are designed to probe the genome at evenly spaced intervals.
to maximize the expected specificity of the array, repetitive probes must be avoided and experimental conditions, such as melting temperature, equalized.
this creates an optimization problem in choosing which sequences should be included on the array  <cit> .
in smaller microbial genomes, it is possible to target every position of the genome with overlapping probes, simplifying the design process.
for example, extreme high-density arrays can now accommodate  <dig>  million variable length probes on a single chip .
for an average  <dig> mb sized bacterial genome and  <dig> nt probe length, probes can be offset by only a single base-pair and still span the entire genome, generating a coverage of 50×.
by tiling the entire genome, some suboptimal probes will be included on the array, but can be identified and corrected for in the analysis.
these overlapping arrays are capable of identifying polymorphism at a much finer resolution than gapped arrays.
tiling arrays have traditionally been constructed based on the genome of a single reference strain and used to locate genomic differences contained in the experimental strains.
however, single-genome arrays can only detect and analyze sequences similar to those included on the array, and cannot discover or analyze sequences absent in the reference strain.
after the introduction of the pan-genome concept  <cit> , it has become increasingly clear that some microbial species contain significant genetic diversity, and it is not suitable to compare against only a single reference strain.
the pan-genome hypothesis states that any given species has two sets of genes.
first, a set of core genes present in all strains that define the species; and second, a set of dispensable genes present in only one or a few of the strains that presumably mediate adaptation.
a single genome describes the genomic material for a particular strain, but the pan-genome describes the genomic makeup for an entire species.
single reference tiling arrays cannot survey this full diversity.
ideally, an array for analyzing new strains should cover the genomic diversity of the entire pan-genome.
with the explosion in microarray densities, it is now possible to design pan-genome tiling arrays that contain all genomic sequence from the known pan-genome.
the simplest strategy is to fully tile the genomes of each strain independently.
however, due to similarities between the strains, some sequences would be tiled with excessive redundancy, and this approach would be cost ineffective.
instead, a pan-genome array should aim to minimize costs by using the minimal probe set necessary to target every element of the pan-genome with adequate coverage.
the typical approach for targeting multiple strains is to group individual genes into gene families and then probe only the conserved sequences of those families  <cit> .
for example, willenbrock et al.
designed an innovative  <dig> strain escherichia coli pan-genome array by clustering homologous genes based on pairwise alignment similarity  <cit> .
homology was defined as gene alignments with an e-value < 10- <dig>  a bitscore >  <dig>  and alignment coverage of at least 50% of the gene length.
for each resulting gene group, a consensus sequence was generated via multiple alignment, and probes were designed to target the most conserved regions of the consensus.
the resulting array comprised  <dig>  probes, targeting  <dig>  gene groups, with a median coverage of  <dig> probes per gene group.
targeting only the conserved sequence of gene families is an effective and efficient method for detecting--at a low resolution--the presence and absence of gene families; however, for studies that require a finer resolution, this method omits many potentially significant sequences from the array.
firstly, a slight variation in a gene  can be responsible for a significantly different phenotype.
by only targeting the conserved portion of gene families, the variable regions responsible for these differences will not be included on the array.
secondly, a gene-centric design includes only coding sequences.
therefore, these designs cannot be used to detect differences in intergenic regions which may include regulatory elements, or used for studies that require a whole-genome tiling, such as transcriptome mapping or chromatin-immunoprecipitation-chip  studies.
finally, gene-centric design models depend on an accurate annotation of the genome.
if genes have been mis-annotated or omitted from the annotation, such genes cannot be properly represented on the array.
this is particularly troublesome for many draft-quality genomes that have highly fragmented sequence assemblies and lack accurate annotations.
for these reasons, a whole-genome tiling is preferable for applications that require more flexibility or an unbiased tiling of the genome.
however, no methods have been described for efficiently tiling multiple whole-genome sequences.
this paper describes a method for pan-genome tiling array design that both minimizes the number of probes required and guarantees that all sequences in the pan-genome are fully tiled by the array.
the prior gene-centric approaches are abandoned in favor of a more concrete, probe-centric approach that relies only on the genomic sequences and not the annotation.
to summarize the new approach, let the pan-genome g be the set of all genomes from a species, and let p be the non-redundant set of all length k substrings from g. due to sequence conservation between genomes, a single probe may match to multiple locations  of the pan-genome.
call these matches the probe targets.
the pan-tiling problem is to find a minimum cardinality subset h ⊆ p such that all sequences of g are targeted by probes in h and no target is offset more than maxoff from an adjacent target .
constructing a full tiling of the pan-genome seems like it would require a large number of probes, but by leveraging the similarities between strains, a reasonably sized probe set can be constructed that fully covers a large pan-genome with adequate redundancy.
the key to the strategy is choosing probes that will hybridize to as many of the strains as possible, while using only a necessary amount of probes to cover polymorphisms .
for example, figure 1b shows a pan-genome tiling for two miniature genomes, with a maxoff of one-third the probe length.
genomes a and b are identical except for a small insertion in the middle of b. fully tiling both genomes requires a total of  <dig> probe targets , but probe set h illustrates that these  <dig> targets can be tiled with just  <dig> probes.
conserved probes are used to tile the left and right of both genomes, and distinct probes are used to tile the two polymorphism variants.
this is obviously a simplified example.
the problem becomes more difficult as the number of genomes and complexity of polymorphisms increases.
the methods presented in this paper were developed to aid the design of a pan-genome cgh tiling array for listeria monocytogenes--the causative agent of listeriosis and a niaid category b biodefense agent that is of significant food safety and public health concern  <cit> .
the species of l. monocytogenes is composed of three primary genetic lineages  that display different capabilities of environmental survival and pathogenic potential to cause human infectious disease  <cit> .
in order to both characterize new strains based on genetic content, and detect polymorphism at a higher resolution in small rnas  and intergenic sequences, the array was required to cover all pan-genomic sequences with a high density of probes.
this bacterial species is particularly well suited for pan-genome array design because there are a remarkable number of strains that have been sequenced.
at the time of writing, a total of  <dig> l. monocytogenes complete or draft genome sequences were available, totaling  <dig>  mbp .
genomic sequences and annotations were obtained from the national microbial pathogen database resource   <cit> .
the sequence conservation for the sequenced strains was computed with nucmer  <cit> , and ranges between 94% and 99% in nucleotide identity versus the completed egd-e reference strain.
even with such substantial diversity within the species, the panarray algorithm is able to design a pan-genome tiling covering each genome at more than twofold coverage using only  <dig>  50-mer probes.
a similar density tiling for a single l. monocytogenes strain would require  <dig>  probes, meaning the panarray design covers 20× more genomes using only 3× more probes.
a description of this design, along with array designs for six other bacterial pan-genomes is given in the results section.
sequences and annotations were obtained from nmpdr.
the final column shows the nucleotide identity of a whole-genome alignment versus strain egd-e. *number of annotated protein coding genes and rnas reported by nmpdr at the time of this study.
methods
the general strategy of the panarray design algorithm is best summarized by analogy to the well-known minimum hitting set problem in computer science  <cit> .
let p be a set of n points and f = {p <dig>  p <dig> ..., pm} be a family of m subsets of p. minimum hitting set is the problem of selecting the minimum cardinality subset h ⊆ p such that h contains at least one element from each subset in f. although finding a minimum hitting set is known to be np hard, it is a well studied problem and efficient approximation algorithms are known.
to see the similarities between the pan-tiling and minimum hitting set problems, let the sequence g be a concatenation of all the genomes from a species, and let w = {w <dig>  w <dig> ..., wm} be the set of m intervals that results from segmenting g into non-overlapping, end-to-end, length l windows.
let p be the non-redundant set of length k substrings from g. a probe candidate p ∈ p is said to hit a window w ∈ w if a match between p and a substring of g begins in the interval w. let pi ⊆ p be the subset of probes that hit the window wi, and f = {p <dig>  p <dig> ..., pm} for the m windows of w. a minimum hitting set h of f is a minimum cardinality subset of probes h ⊆ p such that every window of the pan-genome is hit by at least one probe in h. therefore, finding h effectively tiles the entire pan-genome using a small number of probes.
window and probe indexing
windowing the genome simplifies the pan-tiling problem by casting it is a minimum hitting set problem, and at the same time enforces the maxoff constraint.
because each window is forced to contain at least one target, any two adjacent targets cannot be separated by more than twice the window length.
therefore, the window length is equal to one half maxoff.
for example, given a maximum offset of 2l, windows are marked off every l bases of the pan-genome--with the first window w <dig> covering the interval , and the second window w <dig> covering , and so on.
assuming one target is chosen per window, and the target locations are evenly distributed within windows, the average distance between adjacent targets is expected to be equal to the window length.
for a window length l, equal to the probe length k, the resulting depth of coverage averages one, because the probes are spaced k bases apart on average.
for any other window length l, the resulting depth of coverage c is expected to be c ≈ k/l.
the extreme case being l =  <dig>  which results in exactly k-fold coverage because a probe must hit every position in g.
to solve the minimum hitting set problem, once the pan-genome is discretized into a set of windows, each window must be mapped to the set of probe hits it contains.
as before, a probe p hits a window if a match between p and g begins within the window's interval.
thus far exact matches have been assumed, but a match can be defined by any criteria necessary for efficient hybridization.
to help reduce probe redundancy, the panarray implementation can optionally use inexact matches containing a single mismatch.
any suitable k-mer indexing algorithm can be utilized for this phase, but allowing for mismatches can be computationally expensive.
the implementation uses a fast, but memory intensive, compressed keyword tree for indexing all probe hits.
alternatively, a slower, but memory efficient, hashing scheme would also work.
to index the 1-mismatch hits, each probe's 3k possible 1-mimsatch permutations are added to the index as well.
the result of the indexing is a list of positions and windows for all k-mers of the pan-genome .
at this stage, the final list of probe candidates may be manually filtered based on typical criterion such as melting temperature, gc content, secondary structure, etc.
for ungapped tilings, it is impossible to avoid suboptimal probes.
however, highly repetitive probes can be identified by the number of genomic positions they map to, and should be discarded if they threaten to confound the array analysis .
alternatively, the input sequences may be masked prior to k-mer indexing to avoid repetitive or unwanted sequence altogether.
for cgh arrays, each probe is considered equivalent to its reverse complement, but for expression or transcriptome arrays, forward and reverse strand probes must be considered independently.
probe matches are listed on the strand on which they appear, so for single-stranded samples, the sequence to be synthesized for the array will need to be reversed complemented.
for dna tiling arrays it is helpful to assume the sample will be double-stranded so that genomic inversions in one or more of the strains do not have to be tiled separately.
probe selection
as detailed above, selecting a minimum probe set for tiling s is equivalent to finding the minimum hitting set of p. as before, w is the windowed pan-genome.
let wp be the subset of windows hit by probe p, and u be the set of currently uncovered windows.
let a window hit by at least one probe be termed as covered, and the coverage of a probe be the number of windows it hits |wp|.
a naive algorithm for finding a small hitting set h is to choose, for each uncovered window, a probe hitting the window that also hits the most other windows.
the idea being that choosing probes with the highest coverage will minimize the total number of probes necessary to cover all windows.
however, this approach does not properly account for the probe coverages.
only a single probe is needed to cover a window, so after selecting a probe p, all other probes that hit a window in wp will see their effective coverage reduced.
take for instance two probes p and q that hit the exact same set of windows.
choosing p reduces the effective coverage of q to zero, because all of q's windows have already been covered by p. let the residual coverage rp of a probe be the effective coverage after some other set of probes have already been chosen .
a greedy algorithm first suggested by johnson  <cit>  improves on the naive approach by allowing to reconsider the residual coverage of probes after each iteration.
this algorithm has since been shown to be essentially a best-possible approximation for the minimum hitting set problem  <cit> .
when adapted for the current problem, the algorithm chooses, while uncovered windows remain, the probe that hits the most currently uncovered windows.
the greedy panarray algorithm is:
greedy panarray algorithm
h = Ø
u = w
while u ≠ Ø
select
u ← u - wp
h ← h ∪ {p}
return h
at the start of the algorithm, all initial coverages are inserted into the queue.
to maintain the priority queue after a new probe is chosen, all residual coverages are considered invalid.
during the next iteration, a new rp value is computed for the front of the queue, marked as valid, and reinserted into the queue.
this process is repeated until a valid residual returns to the front of the queue.
often, newly computed residuals will return quickly to the head of the queue before the others have been updated.
at this point it is unnecessary to update any other residuals because their new values cannot be greater than their current value.
therefore, the head of the queue must be the updated maximum.
this lazy evaluation of the residuals avoids many unnecessary computations and drastically improves the performance of the algorithm.
the greedy algorithm without this speedup takes days to complete, but with the speedup runs in a matter of seconds.
probe annotation
the flexibility of the panarray design algorithm is a result of its probe-centric approach.
because it does not require any identification or clustering of genes, the design is independent of any genome annotation.
therefore, instead of building the annotation into the design of the array, the annotation can be mapped onto the array after the design.
most importantly, this strategy allows for intergenic sequence and unannotated genomes to be included on the array, and annotation updates to be incorporated as they become available.
for example, after the l. monocytogenes array had been designed , over  <dig> new srnas were discovered in listeria  <cit> .
neatly, the sequences of each had already been tiled by the array design, and the updated annotation was easily remapped onto the array.
as another example, the gene counts provided by nmpdr in table  <dig> are inconsistent and vary between  <dig>  and  <dig>  genes per genome, suggesting considerable annotation error.
uncoupling the array design from the annotations removes any possibility that annotation errors will affect the design.
included with the final probe set h is the list of locations on the pan-genome that each probe matches.
if the genome sequence is updated, the location information can be easily recovered by remapping the probes to the genome using a matching tool such as mummer  <cit>  or vmatch  <cit> .
to annotate the array, probes are mapped to all annotation features with a coinciding location.
the result is a many-to-many mapping with each feature being targeted by multiple probes, and a single probe possibly targeting multiple features .
with this mapping, all probes targeting a specific gene in the pan-genome can be quickly recovered.
RESULTS
listeria monocytogenes pan-genome array
as suggested in the introduction, l. monocytogenes is a good candidate for constructing a pan-genome tiling array because the species has been widely sequenced, with  <dig> complete or draft genome sequences available.
to confirm that the sequenced genomes contain the majority of l. monocytogenes genetic diversity, the pan-genome size was estimated using the methods of tettelin et al.
<cit>  as implemented in the ergatis package  <cit> .
seventeen of the eighteen l. monocytogenes genomes listed as annotated by nmpdr in table  <dig> were used in the analysis .
according to the cited method, the addition of an nth genome was simulated by searching the annotated genes of each genome against all possible permutations of n- <dig> other genomes.
genes without a match over 50% protein similarity for at least 50% of their length were recorded as "new".
the number of new genes n expected to be discovered in the nth sequenced genome was modeled by the power law n = κn-α, and the parameters κ and α were estimated from the data via non-linear least squares regression using the r function nls  <cit> .
the regression was performed on the full set of over  <dig> million data points.
a power law model was found to fit the l. monocytogenes data better than the originally proposed exponential model.
this agrees with a recent suggestion that a power law is a more appropriate model of the pan-genome phenomenon  <cit> .
the estimated number of undiscovered genes is shown in figure  <dig>  the power law exponent α was found to be  <dig>  ±  <dig> , suggesting that the l. monocytogenes pan-genome is closed , and the sequencing of more genomes would eventually sample the entire set of dispensable genes.
therefore, it appears the vast majority of l. monocytogenes genes have been sequenced and are included on the array.
this model predicts that the addition of a 21st genome to table  <dig> would yield only ~  <dig> new genes.
however, only a single lineage iii genome was included in this analysis, so this prediction might be artificially low for a new lineage iii strain.
the sole lineage iii strain analyzed  contains  <dig> genes absent in any of the lineage i and ii strains.
to capture the full diversity of l. monocytogenes, all  <dig> genomes listed in table  <dig> were included in the design, with a combined sequence length of  <dig> , <dig> bp and a total of  <dig>  annotated genes.
to avoid tiling low quality or contaminant sequence, contigs less than  <dig> kbp in length were discarded--reducing the tiled sequence length to  <dig> , <dig> bp.
the design was constrained to a  <dig>  feature nimblegen array with a probe length of  <dig> nt.
because hybridization of a 50-mer probe will tolerate a few mismatches, probes differing by a single mismatch were considered equivalent during the design phase.
the window length was set to  <dig> bp, enforcing a maximum target offset of  <dig>  an expected depth of coverage of about 50/ <dig> =  <dig> ×, and resulting in approximately  <dig>  million windows.
these parameters guarantee that every base-pair of the pan-genome will be covered by at least one probe, since the maximum offset is less than the probe length.
to cover each window, the panarray algorithm selected  <dig>  distinct probes mapping to  <dig> , <dig> positions in the pan-genome.
on average, each probe in the design targets about  <dig> different positions in the pan-genome.
rather than being repeated sequences within the same genome, these different locations most often refer to a conserved locus in multiple strains .
interestingly, the degree of probe reuse corresponds well with the known evolutionary relationship of the strains.
included on the chip are  <dig> genomes from lineage i,  <dig> from lineage ii, and  <dig> from lineage iii.
this would suggest that the peak at genomes =  <dig> in figure  <dig> is for strain-specific probes; the peaks around  <dig> and  <dig> are for lineage-specific probes; and the peak around  <dig> is for species-specific probes that are conserved in all  <dig> l. monocytogenes genomes.
because this is a dense tiling of the entire genome, it was unnecessary to optimize probes for uniqueness, as is done in standard expression arrays with only a few probes per gene.
probes were screened for repetitive sequences, but the l. monocytogenes strains were found to contain few repeats.
the most repetitive 15-mer occurs only  <dig> times per genome, and the most repetitive 50-mer probe used in the design targets a "cell wall surface anchor protein" family and occurs a maximum of  <dig> times per genome.
altogether,  <dig> % of the probes target at most one location per genome.
to augment the original panarray design, an additional  <dig> negative control probes were added to the array, chosen from bacillus spp., which is a known cohabitant of listeria.
the negative control probes were chosen to be specific to bacillus spp.
using the insignia genomic signature design pipeline  <cit> .
the remaining  <dig>  features on the array were filled by selecting individual probes to supplement the lowest coverage regions of the design.
all probes were checked to conform to nimblegen design specifications, and a few probes were trimmed to meet synthesis cycle limits.
the resulting l. monocytogenes pan-genome array has an average depth-of-coverage of  <dig> ×, with a median probe offset of  <dig> bp, and a modal offset equal to the window length of  <dig> bp.
the full distribution of probe offsets is given in figure  <dig>  as expected, the average offset is equal to the window length .
the uneven distribution and pronounced mode is the caused by non-random tie breaking.
in the case of a conserved sequence, where every probe hits the same number of genomes, the first probe of the window is always chosen.
also, the heavy left tail indicates that many windows are covered by more than one probe and the solution that is slightly denser than expected .
this may be a consequence of the sequence composition, or may indicate a non-optimal solution.
finally, the majority of targeted sequences exactly match their probe  and the remainder match with a single mismatch .
the performance gain of panarray over more naive methods is significant.
for instance, selecting a single probe from each window requires roughly  <dig>  million probes.
the slightly more principled naive algorithm, that does not recompute residual coverages, chooses  <dig> , <dig> probes, but is still well over the  <dig>  probe limit.
the greedy panarray algorithm meets this limit and vastly outperforms the other methods--requiring only  <dig>  probes to cover the entire pan-genome.
with the lazy evaluation speedup, the panarray algorithm is also comparable in runtime to the naive algorithms.
on a single  <dig>  ghz processor, the naive algorithm took  <dig> seconds; the greedy algorithm without lazy evaluation was terminated without completing after a few days; and the greedy panarray algorithm with lazy evaluation took only  <dig> seconds.
the runtime for the final design process was dominated by building the k-mer index, which required  <dig> minutes using a compressed keyword tree.
design analysis for additional pan-genomes
using panarray, additional arrays were designed for a total of seven bacterial pan-genomes, for which a large number of genomes have been sequenced.
the additional species include: francisella tularensis, staphylococcus aureus, bacillus anthracis, vibrio cholerae, burkholderia pseudomallei, escherichia coli, and shigella spp.
due to their high similarity, e. coli and shigella spp.
were considered as a single pan-genome.
to facilitate easy comparison, all designs were created with a window length of  <dig> bp, a probe length of  <dig> nt, and allowing for probes to contain a single mismatch to their target.
as with the l. monocytogenes design above, draft genomes were included, but contigs less than  <dig> kbp were discarded.
the results are given in table  <dig>  probe "reuse" is measured in the average number of targets per probe.
it is rare for a 50-mer probe to match to more than one location per genome, so the number of targets per probe is roughly equivalent to the average number of genomes that a probe matches.
avg.
length is the average genome length for a species.
pan length is the sum of all genome lengths for a species.
targets is the total number of locations targeted by the probes.
a single probe may target multiple genomes in the species.
reuse is the average number of targets per probe, and a normalized reuse is given in parentheses as the reuse divided by the number of genomes.
the highly conserved species of b. anthracis exhibits near perfect probe reuse.
almost every b. anthracis probe matches all of the included strains; therefore, the number of probes required to tile the nine sequenced strains is nearly the same as is required to tile one strain.
this is because the pan-genome of b. anthracis is closed and the strains are highly conserved at the nucleotide level .
adding successive b. anthracis strains to the array would increase the required number of probes very gradually.
in contrast, l. monocytogenes has the lowest degree of probe reuse, with each probe targeting on average only 39% of the included strains.
this is a reflection of the diversity of strains that have been sequenced and the low level of nucleotide conservation between strains, with some strains differing by as much as 8% .
any snp rate of higher than 2%  exceeds the  <dig> mismatch threshold per probe and requires additional probes to target the divergent sequence.
however, as more variants are added to the array, the addition of each successive genome requires fewer new probes than the last, on average.
figure  <dig> shows this relationship for the l. monocytogenes strains.
successive strains are added by order of lineage, from the bottom of table  <dig> to the top, and the design is recomputed at each step.
there are pronounced jumps in the number of probes required when the first of a new lineage is added, but the number of probes needed to tile the rest of the lineage quickly levels off.
escherichia coli and shigella spp.
form the largest pan-genome currently sequenced, totaling over  <dig> mbp of genomic sequence.
even for a pan-genome of this size and diversity, panarray effectively tiles all sequences at an average of 2× coverage using only  <dig>  probes--well below the maximum number of probes available on current arrays.
the b. pseudomallei pan-genome is roughly equivalent in total number of pan-genome bases, but requires considerably fewer probes because of higher probe reuse.
due to the large number of sequenced genomes and relatively high similarity between strains, the b. pseudomallei design exhibits the highest probe reuse factor of all the designs .
creating a 2× coverage tiling by choosing one probe every  <dig> bp would require roughly  <dig>  million probes for the b. pseudomallei pan-genome, but panarray was able to create a  <dig> × tiling of the same pan-genome with only  <dig>  probes.
implementation and availability
the panarray algorithm was implemented in c++, and the source code is freely available at http://www.cbcb.umd.edu/software/panarray.
the listeria monocytogenes array design described above is available from the gene expression omnibus  <cit>  under geo accession number gpl <dig>
discussion
the panarray algorithm described above is ideal for high-density tilings of overlapping or closely spaced probes.
the results section has shown that this algorithm is applicable for all currently available bacterial pan-genomes.
however, if the maximum number of probes is limited, or the genome size is extremely large, it may be necessary to design a tiling with gaps between the probe targets .
in this case, it is necessary to choose unique probes that avoid unwanted cross hybridization between repetitive sequences within the genome.
to achieve this, repetitive probes can be filtered, or the coverage scores used in the panarray algorithm can be weighted to penalize repetitive probes.
for example, probe coverage can be redefined as the number of genomes a probe targets, rather than the number of windows, and probes targeting multiple windows in the same genome can be appropriately down-weighted.
in many cases, probes within the same window will share the same coverage score, and rules can be applied for breaking the tie and choosing the most reliable probe.
similar schemes could be devised to favor probes with any other desirable criteria.
array analysis of acgh experiments is typically conducted on signal ratios between a reference and experimental hybridization.
duplications or deletions in the experimental samples are evident as non-zero values of the log ratio of the two normalized signals.
so-called segmentation algorithms examine this log ratio across multiple positions in reference sequence to determine the boundaries of the variations  <cit> .
the most accurate methods consider not just individual probes, but a context of probes around a genomic location, and can identify even small polymorphisms between the strains.
these analyses require both a reference signal and a reference coordinate system on which the probes are tiled.
usually a whole-genome tiling is constructed for a single reference strain, but because panarray provides a whole-genome tiling for every reference strain included in the array, the same array design can be used to perform segmentation analysis against any reference strain on the array.
in addition to segmentation analysis versus a reference genome, a pan-genome array makes it possible to analyze uncharacterized strains in the context of the entire pan-genome.
in some cases, it is preferable to use a multi-strain control  <cit> , but depending on the number of genomes, it can be impractical to co-hybridize all reference strains included on the chip.
in these cases, traditional segmentation or log-ratio analysis must be replaced by a method that does not require a reference hybridization signal.
for gene-level analysis, direct analysis of the individual probe intensities provides comparable sensitivity and specificity versus segmentation analysis  <cit> , and various methods have been developed that operate independently of a signal ratio  <cit> .
a probe-based approach provides the most flexibility for pan-genome array analysis, because each probe can be individually scored based on its own intensity, and the genes can be classified based on the aggregated scores of the individual probe scores without the need for a control hybridization.
pan-genome tiling arrays have all the applications of single-strain tiling arrays, but with enhanced flexibility and the ability to analyze previously uncharacterized strains.
pan-genome acgh offers an economical alterative to sequencing for determining the genomic makeup of uncharacterized strains in a species and explaining the causative factors of phenotypic differences between strains.
probe based methods, like microarray, are especially well suited for situations where sequencing is inefficient because there is a low abundance of target dna and a high abundance of background dna intermixed.
for example, applications such as real-time pathogen detection, surveillance, and diagnostics require a known sequence of dna to be targeted from a vast environment  <cit> .
a pan-genome array could be used for the detection and genotyping of pathogens from a large environment, without needing to isolate the individual cells.
pan-genome arrays could also be used to capture all species- or locus-specific genomic material from an environment, which could then be directly processed or sequenced separately from the metagenome.
microarray based genomic capture has already been applied to targeted human resequencing as an efficient means of enriching for desired sequencing templates  <cit> .
CONCLUSIONS
without the need for sequencing additional genomes of the same species, pan-genomic acgh has become an increasingly popular and cost-effective approach to compare and characterize genomic contents of unknown bacterial isolates.
prior multi-strain arrays have targeted the conserved sequences of gene families, or a selected group of polymorphisms; therefore, providing only partial coverage of the pan-genome.
panarray is a probe selection algorithm capable designing a tiling array that fully covers all genomes of a species using a minimal number of probes.
the viability of this method is demonstrated by array designs for seven different bacterial pan-genomes, each of which can fit on a single microarray slide.
by constructing an unbiased tiling of all known sequences, these unique pan-genome tiling arrays provide maximum flexibility for the analysis, detection, or capture of genomic material for entire species.
authors' contributions
amp conceived the problem, designed and implemented the algorithm, performed the analyses, and wrote the manuscript.
xd contributed to the design and analysis, and edited the manuscript.
wz and sls helped conceive the problem, edited the manuscript, and coordinated the project.
all authors read and approved the final manuscript.

 microarrays are well known for their success in studying gene expression. as one of their many other roles, dna microarrays can also be used to characterize both large-scale and small-scale genetic variations. for instance, array comparative genomic hybridization is commonly used in human cancer studies to genotype cell lines by detecting gene loss and copy number variations. at a finer resolution, microarrays are also used to detect single nucleotide polymorphisms at targeted loci. in addition to human screens, microarrays have been widely used for the detection and genotyping of microbial species. notably, a viral genotyping microarray was one of the methods used to etiologically link severe acute respiratory syndrome to a novel coronavirus. arrays for the detection and comparative analysis of bacterial genomes have also been developed, including arrays for listeria monocytogenes, and many other bacterial species. however, these earlier, low-density arrays did not contain enough probes to target the entire genome of the bacterium, and were forced to probe only a small subset of the known genes. as the density of dna microarrays increased in recent years, it has become possible to probe the entire genome of an organism in addition to only specific genes. an array providing unbiased coverage of probes across a genome is commonly referred to as a whole-genome tiling array. such arrays have been very successful for genome-scale analysis, including the discovery of novel transcripts, splicing variants, protein binding sites, and polymorphisms. depending on the offset between adjacent probe locations, whole-genome tilings can be either gapped, end-to-end, or overlapping. in the human genome, tiling arrays are designed to probe the genome at evenly spaced intervals. to maximize the expected specificity of the array, repetitive probes must be avoided and experimental conditions, such as melting temperature, equalized. this creates an optimization problem in choosing which sequences should be included on the array. in smaller microbial genomes, it is possible to target every position of the genome with overlapping probes, simplifying the design process. for example, extreme high-density arrays can now accommodate million variable length probes on a single chip. for an average mb sized bacterial genome and nt probe length, probes can be offset by only a single base-pair and still span the entire genome, generating a coverage of 50×. by tiling the entire genome, some suboptimal probes will be included on the array, but can be identified and corrected for in the analysis. these overlapping arrays are capable of identifying polymorphism at a much finer resolution than gapped arrays. tiling arrays have traditionally been constructed based on the genome of a single reference strain and used to locate genomic differences contained in the experimental strains. however, single-genome arrays can only detect and analyze sequences similar to those included on the array, and cannot discover or analyze sequences absent in the reference strain. after the introduction of the pan-genome concept, it has become increasingly clear that some microbial species contain significant genetic diversity, and it is not suitable to compare against only a single reference strain. the pan-genome hypothesis states that any given species has two sets of genes. first, a set of core genes present in all strains that define the species; and second, a set of dispensable genes present in only one or a few of the strains that presumably mediate adaptation. a single genome describes the genomic material for a particular strain, but the pan-genome describes the genomic makeup for an entire species. single reference tiling arrays cannot survey this full diversity. ideally, an array for analyzing new strains should cover the genomic diversity of the entire pan-genome. with the explosion in microarray densities, it is now possible to design pan-genome tiling arrays that contain all genomic sequence from the known pan-genome. the simplest strategy is to fully tile the genomes of each strain independently. however, due to similarities between the strains, some sequences would be tiled with excessive redundancy, and this approach would be cost ineffective. instead, a pan-genome array should aim to minimize costs by using the minimal probe set necessary to target every element of the pan-genome with adequate coverage. the typical approach for targeting multiple strains is to group individual genes into gene families and then probe only the conserved sequences of those families. for example, willenbrock et al. designed an innovative strain escherichia coli pan-genome array by clustering homologous genes based on pairwise alignment similarity. homology was defined as gene alignments with an e-value < 10- a bitscore > and alignment coverage of at least 50% of the gene length. for each resulting gene group, a consensus sequence was generated via multiple alignment, and probes were designed to target the most conserved regions of the consensus. the resulting array comprised probes, targeting gene groups, with a median coverage of probes per gene group. targeting only the conserved sequence of gene families is an effective and efficient method for detecting--at a low resolution--the presence and absence of gene families; however, for studies that require a finer resolution, this method omits many potentially significant sequences from the array. firstly, a slight variation in a gene can be responsible for a significantly different phenotype. by only targeting the conserved portion of gene families, the variable regions responsible for these differences will not be included on the array. secondly, a gene-centric design includes only coding sequences. therefore, these designs cannot be used to detect differences in intergenic regions which may include regulatory elements, or used for studies that require a whole-genome tiling, such as transcriptome mapping or chromatin-immunoprecipitation-chip studies. finally, gene-centric design models depend on an accurate annotation of the genome. if genes have been mis-annotated or omitted from the annotation, such genes cannot be properly represented on the array. this is particularly troublesome for many draft-quality genomes that have highly fragmented sequence assemblies and lack accurate annotations. for these reasons, a whole-genome tiling is preferable for applications that require more flexibility or an unbiased tiling of the genome. however, no methods have been described for efficiently tiling multiple whole-genome sequences. this paper describes a method for pan-genome tiling array design that both minimizes the number of probes required and guarantees that all sequences in the pan-genome are fully tiled by the array. the prior gene-centric approaches are abandoned in favor of a more concrete, probe-centric approach that relies only on the genomic sequences and not the annotation. to summarize the new approach, let the pan-genome g be the set of all genomes from a species, and let p be the non-redundant set of all length k substrings from g. due to sequence conservation between genomes, a single probe may match to multiple locations of the pan-genome. call these matches the probe targets. the pan-tiling problem is to find a minimum cardinality subset h ⊆ p such that all sequences of g are targeted by probes in h and no target is offset more than maxoff from an adjacent target. constructing a full tiling of the pan-genome seems like it would require a large number of probes, but by leveraging the similarities between strains, a reasonably sized probe set can be constructed that fully covers a large pan-genome with adequate redundancy. the key to the strategy is choosing probes that will hybridize to as many of the strains as possible, while using only a necessary amount of probes to cover polymorphisms. for example, figure 1b shows a pan-genome tiling for two miniature genomes, with a maxoff of one-third the probe length. genomes a and b are identical except for a small insertion in the middle of b. fully tiling both genomes requires a total of probe targets, but probe set h illustrates that these targets can be tiled with just probes. conserved probes are used to tile the left and right of both genomes, and distinct probes are used to tile the two polymorphism variants. this is obviously a simplified example. the problem becomes more difficult as the number of genomes and complexity of polymorphisms increases. the methods presented in this paper were developed to aid the design of a pan-genome cgh tiling array for listeria monocytogenes--the causative agent of listeriosis and a niaid category b biodefense agent that is of significant food safety and public health concern. the species of l. monocytogenes is composed of three primary genetic lineages that display different capabilities of environmental survival and pathogenic potential to cause human infectious disease. in order to both characterize new strains based on genetic content, and detect polymorphism at a higher resolution in small rnas and intergenic sequences, the array was required to cover all pan-genomic sequences with a high density of probes. this bacterial species is particularly well suited for pan-genome array design because there are a remarkable number of strains that have been sequenced. at the time of writing, a total of l. monocytogenes complete or draft genome sequences were available, totaling mbp. genomic sequences and annotations were obtained from the national microbial pathogen database resource. the sequence conservation for the sequenced strains was computed with nucmer, and ranges between 94% and 99% in nucleotide identity versus the completed egd-e reference strain. even with such substantial diversity within the species, the panarray algorithm is able to design a pan-genome tiling covering each genome at more than twofold coverage using only 50-mer probes. a similar density tiling for a single l. monocytogenes strain would require probes, meaning the panarray design covers 20× more genomes using only 3× more probes. a description of this design, along with array designs for six other bacterial pan-genomes is given in the results section. sequences and annotations were obtained from nmpdr. the final column shows the nucleotide identity of a whole-genome alignment versus strain egd-e. *number of annotated protein coding genes and rnas reported by nmpdr at the time of this study. methods the general strategy of the panarray design algorithm is best summarized by analogy to the well-known minimum hitting set problem in computer science. let p be a set of n points and f = {p p..., pm} be a family of m subsets of p. minimum hitting set is the problem of selecting the minimum cardinality subset h ⊆ p such that h contains at least one element from each subset in f. although finding a minimum hitting set is known to be np hard, it is a well studied problem and efficient approximation algorithms are known. to see the similarities between the pan-tiling and minimum hitting set problems, let the sequence g be a concatenation of all the genomes from a species, and let w = {w w..., wm} be the set of m intervals that results from segmenting g into non-overlapping, end-to-end, length l windows. let p be the non-redundant set of length k substrings from g. a probe candidate p ∈ p is said to hit a window w ∈ w if a match between p and a substring of g begins in the interval w. let pi ⊆ p be the subset of probes that hit the window wi, and f = {p p..., pm} for the m windows of w. a minimum hitting set h of f is a minimum cardinality subset of probes h ⊆ p such that every window of the pan-genome is hit by at least one probe in h. therefore, finding h effectively tiles the entire pan-genome using a small number of probes. window and probe indexing windowing the genome simplifies the pan-tiling problem by casting it is a minimum hitting set problem, and at the same time enforces the maxoff constraint. because each window is forced to contain at least one target, any two adjacent targets cannot be separated by more than twice the window length. therefore, the window length is equal to one half maxoff. for example, given a maximum offset of 2l, windows are marked off every l bases of the pan-genome--with the first window w covering the interval, and the second window w covering, and so on. assuming one target is chosen per window, and the target locations are evenly distributed within windows, the average distance between adjacent targets is expected to be equal to the window length. for a window length l, equal to the probe length k, the resulting depth of coverage averages one, because the probes are spaced k bases apart on average. for any other window length l, the resulting depth of coverage c is expected to be c ≈ k/l. the extreme case being l = which results in exactly k-fold coverage because a probe must hit every position in g. to solve the minimum hitting set problem, once the pan-genome is discretized into a set of windows, each window must be mapped to the set of probe hits it contains. as before, a probe p hits a window if a match between p and g begins within the window's interval. thus far exact matches have been assumed, but a match can be defined by any criteria necessary for efficient hybridization. to help reduce probe redundancy, the panarray implementation can optionally use inexact matches containing a single mismatch. any suitable k-mer indexing algorithm can be utilized for this phase, but allowing for mismatches can be computationally expensive. the implementation uses a fast, but memory intensive, compressed keyword tree for indexing all probe hits. alternatively, a slower, but memory efficient, hashing scheme would also work. to index the 1-mismatch hits, each probe's 3k possible 1-mimsatch permutations are added to the index as well. the result of the indexing is a list of positions and windows for all k-mers of the pan-genome. at this stage, the final list of probe candidates may be manually filtered based on typical criterion such as melting temperature, gc content, secondary structure, etc. for ungapped tilings, it is impossible to avoid suboptimal probes. however, highly repetitive probes can be identified by the number of genomic positions they map to, and should be discarded if they threaten to confound the array analysis. alternatively, the input sequences may be masked prior to k-mer indexing to avoid repetitive or unwanted sequence altogether. for cgh arrays, each probe is considered equivalent to its reverse complement, but for expression or transcriptome arrays, forward and reverse strand probes must be considered independently. probe matches are listed on the strand on which they appear, so for single-stranded samples, the sequence to be synthesized for the array will need to be reversed complemented. for dna tiling arrays it is helpful to assume the sample will be double-stranded so that genomic inversions in one or more of the strains do not have to be tiled separately. probe selection as detailed above, selecting a minimum probe set for tiling s is equivalent to finding the minimum hitting set of p. as before, w is the windowed pan-genome. let wp be the subset of windows hit by probe p, and u be the set of currently uncovered windows. let a window hit by at least one probe be termed as covered, and the coverage of a probe be the number of windows it hits |wp|. a naive algorithm for finding a small hitting set h is to choose, for each uncovered window, a probe hitting the window that also hits the most other windows. the idea being that choosing probes with the highest coverage will minimize the total number of probes necessary to cover all windows. however, this approach does not properly account for the probe coverages. only a single probe is needed to cover a window, so after selecting a probe p, all other probes that hit a window in wp will see their effective coverage reduced. take for instance two probes p and q that hit the exact same set of windows. choosing p reduces the effective coverage of q to zero, because all of q's windows have already been covered by p. let the residual coverage rp of a probe be the effective coverage after some other set of probes have already been chosen. a greedy algorithm first suggested by johnson improves on the naive approach by allowing to reconsider the residual coverage of probes after each iteration. this algorithm has since been shown to be essentially a best-possible approximation for the minimum hitting set problem. when adapted for the current problem, the algorithm chooses, while uncovered windows remain, the probe that hits the most currently uncovered windows. the greedy panarray algorithm is:    greedy panarray algorithm       h = Ø       u = w       while u ≠ Ø          select             u ← u - wp             h ← h ∪ {p}       return h at the start of the algorithm, all initial coverages are inserted into the queue. to maintain the priority queue after a new probe is chosen, all residual coverages are considered invalid. during the next iteration, a new rp value is computed for the front of the queue, marked as valid, and reinserted into the queue. this process is repeated until a valid residual returns to the front of the queue. often, newly computed residuals will return quickly to the head of the queue before the others have been updated. at this point it is unnecessary to update any other residuals because their new values cannot be greater than their current value. therefore, the head of the queue must be the updated maximum. this lazy evaluation of the residuals avoids many unnecessary computations and drastically improves the performance of the algorithm. the greedy algorithm without this speedup takes days to complete, but with the speedup runs in a matter of seconds. probe annotation the flexibility of the panarray design algorithm is a result of its probe-centric approach. because it does not require any identification or clustering of genes, the design is independent of any genome annotation. therefore, instead of building the annotation into the design of the array, the annotation can be mapped onto the array after the design. most importantly, this strategy allows for intergenic sequence and unannotated genomes to be included on the array, and annotation updates to be incorporated as they become available. for example, after the l. monocytogenes array had been designed, over new srnas were discovered in listeria. neatly, the sequences of each had already been tiled by the array design, and the updated annotation was easily remapped onto the array. as another example, the gene counts provided by nmpdr in table are inconsistent and vary between and genes per genome, suggesting considerable annotation error. uncoupling the array design from the annotations removes any possibility that annotation errors will affect the design. included with the final probe set h is the list of locations on the pan-genome that each probe matches. if the genome sequence is updated, the location information can be easily recovered by remapping the probes to the genome using a matching tool such as mummer or vmatch. to annotate the array, probes are mapped to all annotation features with a coinciding location. the result is a many-to-many mapping with each feature being targeted by multiple probes, and a single probe possibly targeting multiple features. with this mapping, all probes targeting a specific gene in the pan-genome can be quickly recovered.  listeria monocytogenes pan-genome array as suggested in the introduction, l. monocytogenes is a good candidate for constructing a pan-genome tiling array because the species has been widely sequenced, with complete or draft genome sequences available. to confirm that the sequenced genomes contain the majority of l. monocytogenes genetic diversity, the pan-genome size was estimated using the methods of tettelin et al. as implemented in the ergatis package. seventeen of the eighteen l. monocytogenes genomes listed as annotated by nmpdr in table were used in the analysis. according to the cited method, the addition of an nth genome was simulated by searching the annotated genes of each genome against all possible permutations of n- other genomes. genes without a match over 50% protein similarity for at least 50% of their length were recorded as "new". the number of new genes n expected to be discovered in the nth sequenced genome was modeled by the power law n = κn-α, and the parameters κ and α were estimated from the data via non-linear least squares regression using the r function nls. the regression was performed on the full set of over million data points. a power law model was found to fit the l. monocytogenes data better than the originally proposed exponential model. this agrees with a recent suggestion that a power law is a more appropriate model of the pan-genome phenomenon. the estimated number of undiscovered genes is shown in figure the power law exponent α was found to be ±, suggesting that the l. monocytogenes pan-genome is closed, and the sequencing of more genomes would eventually sample the entire set of dispensable genes. therefore, it appears the vast majority of l. monocytogenes genes have been sequenced and are included on the array. this model predicts that the addition of a 21st genome to table would yield only ~ new genes. however, only a single lineage iii genome was included in this analysis, so this prediction might be artificially low for a new lineage iii strain. the sole lineage iii strain analyzed contains genes absent in any of the lineage i and ii strains. to capture the full diversity of l. monocytogenes, all genomes listed in table were included in the design, with a combined sequence length of, bp and a total of annotated genes. to avoid tiling low quality or contaminant sequence, contigs less than kbp in length were discarded--reducing the tiled sequence length to, bp. the design was constrained to a feature nimblegen array with a probe length of nt. because hybridization of a 50-mer probe will tolerate a few mismatches, probes differing by a single mismatch were considered equivalent during the design phase. the window length was set to bp, enforcing a maximum target offset of an expected depth of coverage of about 50/ = ×, and resulting in approximately million windows. these parameters guarantee that every base-pair of the pan-genome will be covered by at least one probe, since the maximum offset is less than the probe length. to cover each window, the panarray algorithm selected distinct probes mapping to, positions in the pan-genome. on average, each probe in the design targets about different positions in the pan-genome. rather than being repeated sequences within the same genome, these different locations most often refer to a conserved locus in multiple strains. interestingly, the degree of probe reuse corresponds well with the known evolutionary relationship of the strains. included on the chip are genomes from lineage i, from lineage ii, and from lineage iii. this would suggest that the peak at genomes = in figure is for strain-specific probes; the peaks around and are for lineage-specific probes; and the peak around is for species-specific probes that are conserved in all l. monocytogenes genomes. because this is a dense tiling of the entire genome, it was unnecessary to optimize probes for uniqueness, as is done in standard expression arrays with only a few probes per gene. probes were screened for repetitive sequences, but the l. monocytogenes strains were found to contain few repeats. the most repetitive 15-mer occurs only times per genome, and the most repetitive 50-mer probe used in the design targets a "cell wall surface anchor protein" family and occurs a maximum of times per genome. altogether, % of the probes target at most one location per genome. to augment the original panarray design, an additional negative control probes were added to the array, chosen from bacillus spp., which is a known cohabitant of listeria. the negative control probes were chosen to be specific to bacillus spp. using the insignia genomic signature design pipeline. the remaining features on the array were filled by selecting individual probes to supplement the lowest coverage regions of the design. all probes were checked to conform to nimblegen design specifications, and a few probes were trimmed to meet synthesis cycle limits. the resulting l. monocytogenes pan-genome array has an average depth-of-coverage of ×, with a median probe offset of bp, and a modal offset equal to the window length of bp. the full distribution of probe offsets is given in figure as expected, the average offset is equal to the window length. the uneven distribution and pronounced mode is the caused by non-random tie breaking. in the case of a conserved sequence, where every probe hits the same number of genomes, the first probe of the window is always chosen. also, the heavy left tail indicates that many windows are covered by more than one probe and the solution that is slightly denser than expected. this may be a consequence of the sequence composition, or may indicate a non-optimal solution. finally, the majority of targeted sequences exactly match their probe and the remainder match with a single mismatch. the performance gain of panarray over more naive methods is significant. for instance, selecting a single probe from each window requires roughly million probes. the slightly more principled naive algorithm, that does not recompute residual coverages, chooses, probes, but is still well over the probe limit. the greedy panarray algorithm meets this limit and vastly outperforms the other methods--requiring only probes to cover the entire pan-genome. with the lazy evaluation speedup, the panarray algorithm is also comparable in runtime to the naive algorithms. on a single ghz processor, the naive algorithm took seconds; the greedy algorithm without lazy evaluation was terminated without completing after a few days; and the greedy panarray algorithm with lazy evaluation took only seconds. the runtime for the final design process was dominated by building the k-mer index, which required minutes using a compressed keyword tree. design analysis for additional pan-genomes using panarray, additional arrays were designed for a total of seven bacterial pan-genomes, for which a large number of genomes have been sequenced. the additional species include: francisella tularensis, staphylococcus aureus, bacillus anthracis, vibrio cholerae, burkholderia pseudomallei, escherichia coli, and shigella spp. due to their high similarity, e. coli and shigella spp. were considered as a single pan-genome. to facilitate easy comparison, all designs were created with a window length of bp, a probe length of nt, and allowing for probes to contain a single mismatch to their target. as with the l. monocytogenes design above, draft genomes were included, but contigs less than kbp were discarded. the results are given in table probe "reuse" is measured in the average number of targets per probe. it is rare for a 50-mer probe to match to more than one location per genome, so the number of targets per probe is roughly equivalent to the average number of genomes that a probe matches. avg. length is the average genome length for a species. pan length is the sum of all genome lengths for a species. targets is the total number of locations targeted by the probes. a single probe may target multiple genomes in the species. reuse is the average number of targets per probe, and a normalized reuse is given in parentheses as the reuse divided by the number of genomes. the highly conserved species of b. anthracis exhibits near perfect probe reuse. almost every b. anthracis probe matches all of the included strains; therefore, the number of probes required to tile the nine sequenced strains is nearly the same as is required to tile one strain. this is because the pan-genome of b. anthracis is closed and the strains are highly conserved at the nucleotide level. adding successive b. anthracis strains to the array would increase the required number of probes very gradually. in contrast, l. monocytogenes has the lowest degree of probe reuse, with each probe targeting on average only 39% of the included strains. this is a reflection of the diversity of strains that have been sequenced and the low level of nucleotide conservation between strains, with some strains differing by as much as 8%. any snp rate of higher than 2% exceeds the mismatch threshold per probe and requires additional probes to target the divergent sequence. however, as more variants are added to the array, the addition of each successive genome requires fewer new probes than the last, on average. figure shows this relationship for the l. monocytogenes strains. successive strains are added by order of lineage, from the bottom of table to the top, and the design is recomputed at each step. there are pronounced jumps in the number of probes required when the first of a new lineage is added, but the number of probes needed to tile the rest of the lineage quickly levels off. escherichia coli and shigella spp. form the largest pan-genome currently sequenced, totaling over mbp of genomic sequence. even for a pan-genome of this size and diversity, panarray effectively tiles all sequences at an average of 2× coverage using only probes--well below the maximum number of probes available on current arrays. the b. pseudomallei pan-genome is roughly equivalent in total number of pan-genome bases, but requires considerably fewer probes because of higher probe reuse. due to the large number of sequenced genomes and relatively high similarity between strains, the b. pseudomallei design exhibits the highest probe reuse factor of all the designs. creating a 2× coverage tiling by choosing one probe every bp would require roughly million probes for the b. pseudomallei pan-genome, but panarray was able to create a × tiling of the same pan-genome with only probes. implementation and availability the panarray algorithm was implemented in c++, and the source code is freely available at http://www.cbcb.umd.edu/software/panarray. the listeria monocytogenes array design described above is available from the gene expression omnibus under geo accession number gpl discussion the panarray algorithm described above is ideal for high-density tilings of overlapping or closely spaced probes. the results section has shown that this algorithm is applicable for all currently available bacterial pan-genomes. however, if the maximum number of probes is limited, or the genome size is extremely large, it may be necessary to design a tiling with gaps between the probe targets. in this case, it is necessary to choose unique probes that avoid unwanted cross hybridization between repetitive sequences within the genome. to achieve this, repetitive probes can be filtered, or the coverage scores used in the panarray algorithm can be weighted to penalize repetitive probes. for example, probe coverage can be redefined as the number of genomes a probe targets, rather than the number of windows, and probes targeting multiple windows in the same genome can be appropriately down-weighted. in many cases, probes within the same window will share the same coverage score, and rules can be applied for breaking the tie and choosing the most reliable probe. similar schemes could be devised to favor probes with any other desirable criteria. array analysis of acgh experiments is typically conducted on signal ratios between a reference and experimental hybridization. duplications or deletions in the experimental samples are evident as non-zero values of the log ratio of the two normalized signals. so-called segmentation algorithms examine this log ratio across multiple positions in reference sequence to determine the boundaries of the variations. the most accurate methods consider not just individual probes, but a context of probes around a genomic location, and can identify even small polymorphisms between the strains. these analyses require both a reference signal and a reference coordinate system on which the probes are tiled. usually a whole-genome tiling is constructed for a single reference strain, but because panarray provides a whole-genome tiling for every reference strain included in the array, the same array design can be used to perform segmentation analysis against any reference strain on the array. in addition to segmentation analysis versus a reference genome, a pan-genome array makes it possible to analyze uncharacterized strains in the context of the entire pan-genome. in some cases, it is preferable to use a multi-strain control, but depending on the number of genomes, it can be impractical to co-hybridize all reference strains included on the chip. in these cases, traditional segmentation or log-ratio analysis must be replaced by a method that does not require a reference hybridization signal. for gene-level analysis, direct analysis of the individual probe intensities provides comparable sensitivity and specificity versus segmentation analysis, and various methods have been developed that operate independently of a signal ratio. a probe-based approach provides the most flexibility for pan-genome array analysis, because each probe can be individually scored based on its own intensity, and the genes can be classified based on the aggregated scores of the individual probe scores without the need for a control hybridization. pan-genome tiling arrays have all the applications of single-strain tiling arrays, but with enhanced flexibility and the ability to analyze previously uncharacterized strains. pan-genome acgh offers an economical alterative to sequencing for determining the genomic makeup of uncharacterized strains in a species and explaining the causative factors of phenotypic differences between strains. probe based methods, like microarray, are especially well suited for situations where sequencing is inefficient because there is a low abundance of target dna and a high abundance of background dna intermixed. for example, applications such as real-time pathogen detection, surveillance, and diagnostics require a known sequence of dna to be targeted from a vast environment. a pan-genome array could be used for the detection and genotyping of pathogens from a large environment, without needing to isolate the individual cells. pan-genome arrays could also be used to capture all species- or locus-specific genomic material from an environment, which could then be directly processed or sequenced separately from the metagenome. microarray based genomic capture has already been applied to targeted human resequencing as an efficient means of enriching for desired sequencing templates.  without the need for sequencing additional genomes of the same species, pan-genomic acgh has become an increasingly popular and cost-effective approach to compare and characterize genomic contents of unknown bacterial isolates. prior multi-strain arrays have targeted the conserved sequences of gene families, or a selected group of polymorphisms; therefore, providing only partial coverage of the pan-genome. panarray is a probe selection algorithm capable designing a tiling array that fully covers all genomes of a species using a minimal number of probes. the viability of this method is demonstrated by array designs for seven different bacterial pan-genomes, each of which can fit on a single microarray slide. by constructing an unbiased tiling of all known sequences, these unique pan-genome tiling arrays provide maximum flexibility for the analysis, detection, or capture of genomic material for entire species. authors' contributions amp conceived the problem, designed and implemented the algorithm, performed the analyses, and wrote the manuscript. xd contributed to the design and analysis, and edited the manuscript. wz and sls helped conceive the problem, edited the manuscript, and coordinated the project. all authors read and approved the final manuscript. 
prior microarrays have included only a single strain per array or the conserved sequences of gene families. unlike arrays built on clustered gene families, panarray uses an unbiased, probe-centric approach that does not rely on annotations, gene clustering, or multi-alignments. this method, as with all microarray applications, requires adequate coverage of probes targeting the regions of interest. array comparative genomic hybridization is a fast and cost-effective method for detecting, genotyping, and comparing the genomic sequence of unknown bacterial isolates. the viability of the algorithm is demonstrated by array designs for seven different bacterial pan-genomes and, in particular, the design of a probe array that fully tiles the genomes of different listeria monocytogenes strains with overlapping probes at greater than twofold coverage. however, such a whole-genome tiling requires that the genome sequence is known in advance. panarray is an oligonucleotide probe selection algorithm for tiling multiple genome sequences using a minimal number of probes. these unique pan-genome tiling arrays provide maximum flexibility for the analysis of both known and uncharacterized strains. to minimize the required number of probes, probes conserved across multiple strains in the pan-genome are selected first, and additional probes are used only where necessary to span polymorphic regions of the genome. this paper presents a new probe selection algorithm that can tile multiple whole genomes using a minimal number of probes.
 array comparative genomic hybridization is a fast and cost-effective method for detecting, genotyping, and comparing the genomic sequence of unknown bacterial isolates. this method, as with all microarray applications, requires adequate coverage of probes targeting the regions of interest. an unbiased tiling of probes across the entire length of the genome is the most flexible design approach. however, such a whole-genome tiling requires that the genome sequence is known in advance. for the accurate analysis of uncharacterized bacteria, an array must query a fully representative set of sequences from the species' pan-genome. prior microarrays have included only a single strain per array or the conserved sequences of gene families. these arrays omit potentially important genes and sequence variants from the pan-genome.  this paper presents a new probe selection algorithm that can tile multiple whole genomes using a minimal number of probes. unlike arrays built on clustered gene families, panarray uses an unbiased, probe-centric approach that does not rely on annotations, gene clustering, or multi-alignments. instead, probes are evenly tiled across all sequences of the pan-genome at a consistent level of coverage. to minimize the required number of probes, probes conserved across multiple strains in the pan-genome are selected first, and additional probes are used only where necessary to span polymorphic regions of the genome. the viability of the algorithm is demonstrated by array designs for seven different bacterial pan-genomes and, in particular, the design of a probe array that fully tiles the genomes of different listeria monocytogenes strains with overlapping probes at greater than twofold coverage.  panarray is an oligonucleotide probe selection algorithm for tiling multiple genome sequences using a minimal number of probes. it is capable of fully tiling all genomes of a species on a single microarray chip. these unique pan-genome tiling arrays provide maximum flexibility for the analysis of both known and uncharacterized strains. 