Optimized Probe Selection for Pan-genomic DNA Microarrays

Motivation: Array comparative genomic hybridization is a quick and cheap method for detecting and genotyping unknown microbial isolates. However, there are a fixed number of probes per array, and therefore the number of loci that can be targeted by a single array is limited. For accurate strain genotyping, an array must query a fully representative set of genes from the speciesʼ pan-genome. Prior genotyping arrays have only targeted a single strain or the conserved sequences of gene families. Results: This paper presents a new probe selection algorithm (PanArray) that can target multiple whole genomes in a minimal number of probes. Unlike arrays built on clustered gene families, PanArray guarantees that every subsequence of the genomes is independently targeted by a full complement of probes, increasing the flexibility and accuracy of the associated comparative analysis and genotyping. The viability of the algorithm is demonstrated by the design of a 385,000 probe array that fully tiles the genomes of 20 different Listeria monocytogenes strains at greater than two-fold coverage. Availability and Implementation: The PanArray design software is implemented in C++, and the PanArray source code and the L. monocytogenes array design are freely available upon request.