BACKGROUND
comparative genomic hybridization  is a powerful technique to determine the differences between the genomes of different cell types or organisms.
typically, genomic dna from known  and experimental  genomes is labeled and hybridized to an array of dna sequences prepared from the known genome.
intensities of hybridization of the two samples are compared to determine the relative copy number of each target gene in the experimental genome as compared to the known genome.
many studies involve determining the genomic abnormalities in tumor cells, but the technique has also been used in bacteria  <cit>  and yeast  <cit>  to investigate diverse topics such as genotyping, pathogenicity, and microbial evolution.
cgh experiments on cancerous and non-cancerous tissues are primarily used in determining the relative copy number of sequences in the tumor cells as compared to the normal tissue for the purpose of identifying genetic elements responsible for cell transformation.
to provide wide coverage of relatively large genomes such as human on a small number of arrays requires using large genomic fragments such as bacterial artificial chromosomes , or by using a large number of arrays  <cit> .
experiments in yeast and bacteria can typically be conducted at much higher resolution due to their smaller genomes, although comparisons must be limited to closely related species, as evolutionary divergence will affect hybridization dynamics if the species are significantly diverged.
a single spotted cdna or oligonucleotide array can easily represent every open reading frame  in the genome, and a high-density microarray can provide sequences that cover the entire genome.
typical high-density microarrays contain hundreds of thousands of short oligonucleotide  sequences .
the substantial variability in performance of different probe sequences and the large number of individual measurements taken complicate the analysis of hybridization data.
many methods have been developed for analyzing data from human array cgh using cdna or bac arrays  <cit> .
a common theme emerging from comparisons of closely related bacteria is genomic variability due to insertion and deletion of genes and gene islands.
regions that are present in a sequenced genome and absent or significantly diverged in an experimental genome can be readily detected by hybridization.
we have termed these "variable regions" because based on cgh alone, it is not possible to distinguish between deletions and sequences that have diverged to a degree that prevents or reduces hybridization.
defining the boundaries of these regions from high-density microarray data involves scoring each probe as indicative of either a conserved or variable sequence and grouping probes with consistent scores into larger segments with defined boundaries.
while there are many methods of scoring probes  <cit> , boundary definition remains a challenge.
a simple approach to detect deleted genes is to average probe values across each gene and select genes with unusually low relative hybridization values  <cit> .
this method defines the units-of-interest as entire genes and does not attempt to identify variable regions that lie outside of genes or only partially span gene boundaries.
larger clusters of variable genomic regions are defined by grouping adjacent variable genes, but definition of the boundaries of these clusters can be sensitive to inclusion or exclusion of individual genes in the initial analysis.
an approach developed for bacterial cgh, implemented in a program called tstep, identifies deletions using microarray data by scoring probes as absent or present based on perfect match and mismatched probe intensities as well as consideration of neighboring probe data using a sliding window  <cit> .
a heuristic set of rules is then applied to find clusters of absent probes.
other programs, developed to analyze mammalian cgh data, analyze data by smoothing probe intensities, followed by breakpoint identification by scanning for areas of high contrast between smoothed data values of neighboring probes  <cit> .
in our efforts to analyze cgh data from high-density microarrays, we found several common drawbacks with existing methods.
many methods simply score probes or genes as present or absent but do not provide a mechanism for defining region boundaries.
most of the available software for defining boundaries was developed for analyzing data from human spotted microarrays, and we encountered problems such as excessive setup and/or run time, dependence on genome annotation, input file format restrictions, and an inability to handle large data sets.
the data we used to develop our approach come from a high-density array with nearly  <dig>  individual  <dig> mer probes, whereas the human data comes primarily from spotted arrays with far fewer probes of longer length.
the larger size of our dataset and greater variability inherent in the performance of short probe sequences compared to longer probes precludes the use of most existing approaches.
for these reasons, we developed cghscan, a program that uses an iterative random walk method to detect variable regions using high-density cgh microarray data.
the algorithm identifies variable regions in data with high levels of noise independently of genome annotation, providing a rapid method for defining differences in high-density microarray cgh studies.
implementation
cghscan operates on a data set d comprised of binary data wherein each probe has been scored either conserved or variable in the experimental genome.
the data is input as a tab delimited text file containing the genomic coordinate of each probe along with which chromosome it corresponds to and the data value.
use of a proprietary file format was done to make the program usable irrespective of the software used by the experimenter to analyze their microarrays.
we score conserved probes as  <dig> and variable probes as - <dig>  but cghscan can operate on any binary numerical scoring method, providing that the score of the variable probes is less than the score of the conserved probes.
we strongly advise users to select a statistically rigorous method to score individual probes such as gack or ebarrays  <cit> ; however, if the data supplied by the user is in the form of raw numerical values for each probe cghscan will perform a simple scoring based on a user-defined cutoff value.
since the grouping of probes into variable genomic regions relies on the scores of individual probes, the choice of an appropriate method for initial scoring of probes is important and it is advisable to try using different scoring thresholds to confirm that the results are robust for a given data set.
cghscan requires the relative physical location of each probe sequence in the reference genome.
the random walk as a method for boundary definition
while many methods of analyzing binary data have been described  <cit> , we chose the random walk.
a one-dimensional random walk occurs on a line, where a series of equidistant steps are taken in one of the two available directions.
the probability of taking a step down is defined as p, while q is the probability of taking a step up.
a random walk of n steps is necessarily comprised of a number of down steps, nd and up steps, nu such that nd + nu = n. the probability of any single random walk occurring is given by the equation
!nd!nu!pndqnu
mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaadawcaaqaamaabmaabagaemoba42aasbaasqaaiabdsgakbqabagccqghrawkcqwgubgbdawgaawcbagaemydauhabeaaaogaayjkaiaawmcaaiabcgcahaqaaiabd6gaunaabaaaleaacqwgkbazaeqaaogaeiyiaeiaemoba42aasbaasqaaiabdwha1bqabagccqgghaqiaagaemiuaa1aawbaasqabeaacqwgubgbdawgaaadbagaemizaqgabeaaaagccqwgrbqudaahaawcbeqaaiabd6gaunaabaaameaacqwg1bqdaeqaaaaaaaa@4619@
which is the binomial probability.
in order to define the boundaries of variable regions, the genome-ordered probes are scanned beginning with probe d <dig> until a variable probe is encountered, probe dinit, and a one-dimensional random walk begins, with conserved and variable probes contributing + <dig>  and - <dig>  respectively.
assuming that the genomes being compared consist largely of conserved regions, the walk  will eventually return to the origin at probe dori, and have a minimum at probe dmin .
in the event of multiple identical minima, the dmin closest to dori is defined as the location of the minimum.
if the walk does not reach the origin before the end of the chromosome, the last probe in the chromosome is defined as dori.
the boundaries of the variable region are defined by dinit on the left side and dmin on the right, as this represents the longest region of local concentration of variable probes.
the coordinates are recorded as a region and the scan resumes at probe dmin + <dig>  where, once again, all conserved probes are ignored until the first variable probe is encountered, and another random walk is initiated.
this process is repeated until the end of the genome is reached.
analyses on circular genomes where there is the possibility that d <dig> lays within a variable region should be re-analyzed with an alternate d <dig> to ensure proper analysis of the region.
multiple chromosomes of a genome are scanned separately and in parallel.
a second iteration scans for conserved regions within the regions found in the first iteration.
this is necessary because the random walk tends to combine variable regions separated by a relatively small conserved region.
the requirement for ∑ assumes that each variable region will be followed by a sufficiently long stretch of conserved probes.
when two regions are close together, they can be grouped together by the random walk .
solving this problem requires an automated method for identifying significant local minima, while ignoring minor local minima caused by noise.
this can be approached in two different ways.
one possible solution is to record the most recent minimum dm <dig>  and as the walk proceeds calculate the statistical significance of the regions defined by dm1+ <dig> and the current probe.
using this method, the walk does not need to return to the origin, but merely significantly far away from the minimum providing a new minimum is not established.
the alternative solution, employed in cghscan, scans each region identified in the first iteration for conserved regions, using the same random walk method.
using this approach we can statistically evaluate the identified conserved regions as a group and are able to employ a correction for multiple tests.
regions found in this second iteration are similarly scanned for variable regions in a third iteration, which are scanned in for conserved regions in a fourth iteration, and further iterations are performed until no additional regions are detected.
statistical analysis of regions
for an operation of n iterations, probabilities are calculated for regions defined in the nth iteration first.
as these regions are detected as lying within regions defined in the previous iteration, p and q are defined as the proportion of variable and conserved probes, respectively, that comprise the regions identified in the previous iteration.
regions defined by a random walk from dinit to dmin can be statistically evaluated using the binomial distribution.
for smaller regions, the binomial probabilities can be calculated directly.
while the binomial probability is a useful metric for the user to evaluate regions, all evaluation of these regions for statistical significance are performed using the method developed by tarone  <cit>  which employs the minimum possible probability pn, which is described below.
for larger regions, we use an approximation of the binomial probability.
larger regions are defined as those where the number of probes multiplied by the smaller of p or q is greater than or equal to  <dig>  and binomial probabilities are approximated using the z-test.
for regions where the binomial probability is approximated with a z-test, a bonferroni multiple testing correction is used.
for the smaller regions, a modified bonferroni correction described by tarone  <cit>  developed specifically for discrete data is used.
briefly, for any region with a length of n probes, pn represents the minimum possible binomial probability for the region.
beginning with an integer k =  <dig>  the regions that satisfy the criterion k*pn < α comprise a subset n of all total regions n in a given iteration.
integer k is increased by one until k ≥ n. this modification removes regions from consideration that could not reject the null hypothesis under any circumstances and makes the correction less conservative.
a standard bonferroni correction is applied to the remaining regions using the minimum binomial probability  for each region.
regions that are called significant after the multiple correction tests are then "added back in" to the regions in the previous iteration in which they were found.
for example, a putative variable region from iteration n- <dig> spanning probes da to dz containing a statistically significant conserved region from iteration n spanning probes dx to dy will be broken into two regions, one spanning da to dx- <dig>  the other spanning dy+ <dig> to dz.
this process is repeated with iteration n- <dig> and so on until iteration  <dig> is reached, where regions are evaluated against p and q defined as the proportion of variable and conserved probes in the genome, respectively.
output
the output is a table reporting the genomic coordinates of all predicted variable regions with their binomial probability or approximation.
two additional tables are output, one detailing all larger variable regions that were identified using the z test, and another for the smaller variable regions analyzed by the modified bonferroni correction.
in the last two tables, variable regions are reported and are grouped by the iteration that they were identified in regardless of whether they passed the bonferroni correction to permit users to evaluate regions near the cutoff.
RESULTS
cghscan was used to analyze microarray data from a study by rajashekara et al.
<cit>  comparing the sequenced pathogen brucella melitensis strain  <dig> m with the closely related brucella ovis strain reo <dig>  the  <dig>  mbp b. melitensis genome is contained on two chromosomes.
the microarray contains  <dig> probes per open reading frame, plus a number of probes corresponding to intergenic regions, which combined provide extensive, albeit partial, coverage across the entire genome.
the trimmed mean of the middle 50% of ordered probe intensities was used to calculate a scaling factor to normalize probe intensities from three replicate experiments for each strain, which were then averaged.
log <dig> ratios of the average probe intensities between the experimental and known genome were calculated and input into cghscan using a significance value of  <dig> .
we tried using two different log <dig> ratio thresholds calculated by gack, a program designed to identify probes with extreme ratio values from microarray data  <cit> .
the first threshold, - <dig> , was calculated using the most lenient  gack setting for creating binary  data, and the second, - <dig> , using the default setting , which results in fewer probes being classified as variable.
b. ovis contains nine known deleted regions confirmed by sequencing as compared to b. melitensis  <cit> .
cghscan identified eight of the nine regions at both ratio thresholds, two in chromosome i, six in chromosome ii .
cghscan successfully identified these eight regions with a ratio threshold as low as - <dig> , indicating that the algorithm is effective over a range of ratio thresholds.
the only previously known deletion that cghscan did not identify is a  <dig> bp deletion that was not detectable using our approach given the probe density of the microarray.
some of the larger known deletions were identified by cghscan as a cluster of smaller variable regions, particularly with the lower ratio threshold .
this is partially due to the fact that the control strain contains known duplications of portions of these regions, which results in higher log <dig> ratios than expected in those areas.
the use of the lower ratio threshold can cause regions to become segmented due to the fact that more probes are called conserved, but segmented regions are in our experience easily recognizable as a single entity .
in addition to identifying eight of the nine known deletions, many additional putative variable regions were identified using either cutoff, with more regions being detected using the less stringent cutoff.
one of these regions contains a repeat present in multiple copies in  <dig> m, but apparently single or at least fewer copies in reo <dig>  causing reduced sequence dosage and apparent variation .
most of the putative variable regions had not been previously identified.
the analysis was repeated using data normalized against the mean instead of a trimmed mean to test performance using an alternative normalization method.
gack was used to establish the default cutoff and a low-stringency cutoff.
once again, cghscan identified the same eight known deletions, as well as other putative variable regions, with more overall regions being detected using the less stringent cutoff .
using the more stringent cutoff, the regions detected using data normalized against the mean vs. a trimmed mean were essentially identical, with only one region differing out of about  <dig>  using the less stringent cutoff, the differences were mostly in agreement as well, but did show more variation than at the more stringent cutoff.
cghscan has advantages over existing software, primarily because it was specifically designed to identify clusters of variable probes from datasets consisting of hundreds of thousands of individual probe measurements from high-density arrays.
other tools accomplish similar analyses, but typically assume that the data will consist at most tens of thousands of measurements from a single array, such as data generated from spotted arrays or from high-density arrays with data condensed into genic units.
for example, cgh-miner version  <dig> , which implements the "cluster along chromosomes" or clac method  <cit> , and acgh-smooth version  <dig> .
<dig>   <cit>  require data input as microsoft excel files, which cannot accommodate the large file sizes generated by high-density microarray experiments.
we encountered errors using data sets containing as low as  <dig>  probes using cgh segmentation  <cit> , and after hours it was unable to complete the analysis of a data set consisting of  <dig>  probes, less than one tenth that of a typical high-density microarray data set.
cghpro  <cit>  is a stand-alone java application that provides a comprehensive environment for analyzing cgh data that includes data normalization, analysis and visualization components.
the software, however, requires a mysql database and the statistical program r, making installation difficult for many potential users without the expertise necessary to install the multiple required components.
cgh-explorer  <cit>  is configured to analyze only data from human arrays and we were unable to reconfigure it to use another genome.
in order to assess the performance of existing applications on high-density microarray data sets and compare their results to cghscan it was often necessary to use only a portion of the data set, otherwise many programs would not be able to accommodate the data or complete the analysis.
applications with the option to define parameters were all run at their default settings.
as previously mentioned, using cgh segmentation  <cit>  we were unable to obtain results using a data set of as few as  <dig>  probes, which itself was too small a portion of the data to do a meaningful comparison.
charm version  <dig>   <cit>  was the only program that we tested that was able to analyze our entire data set.
using the default settings in charm, the program was able to identify five of the nine known deletions in b. ovis, with one of the regions missed being a large deletion in chromosome  <dig>  it should be noted that the default settings for charm do appear to be more conservative than the settings we used to test cghscan.
our ability to test multiple different settings using charm was complicated by excessive runtime, presumably due to the large sizes of our data files.
charm required hours to analyze a single data set, compared to seconds for cghscan, and charm was frequently unable to complete the analyses.
acgh-smooth version  <dig> .
<dig>   <cit>  limits its input to microsoft excel files which have a limit of  <dig>  rows of data.
we found that in practice using data sets of greater than  <dig>  probes in acgh-smooth caused errors that did not permit completion of the analysis.
we ran a data set consisting of  <dig>  probes from chromosome  <dig> that contained all seven of the known deletions on that chromosome.
acgh-smooth identified four of the seven regions, failing to detect the three smallest regions.
we had similar results when using the r package glad version  <dig> .
<dig>  glad was also unable to do a complete analysis on our entire data set, but was capable of analyzing the entire chromosome  <dig> data set of  <dig>  probes.
glad identified the three largest regions, but failed to detect the four smaller regions.
cghscan was able to identify six regions, but also missed the smallest region, a  <dig> bp deletion that proved to be undetectable by any method.
in general, the existing programs worked well on sample data when available, and implement useful algorithms for the analysis of human array cgh data.
the programs are not, however, well suited to high-density microarray cgh data analysis, as many could not accommodate large file sizes or operate in a reasonable amount of time.
additionally, many programs available require genome annotation and analyze gains and losses on a gene-by-gene basis.
high-density microarrays can measure differences on a much a smaller scale, and can even identify breakpoints that occur within genes or between genes that are refractory to gene-by-gene approaches.
these difficulties led us to the conclusion that we needed to develop cghscan to address the specific need we had for high-density microarray cgh data analysis.
CONCLUSIONS
we have developed a robust and efficient method for detecting variable regions between genomes using comparative genomic hybridization data from high-density microarrays.
the method is relatively insensitive to data normalization methods and cutoff selection and uses rigorous statistical analysis.
the method successfully identified all eight detectable deleted regions identified in a published comparison of b. ovis as compared to b. melitensis, as well as numerous additional regions that are predicted to differ between the genomes of these organisms.
availability and requirements
project name: cghscan
project home page:
operating system: platform independent
programming language: java
other requirements: java runtime environment  <dig> .2
license: gnu general public license
use: free, no license required
abbreviations
cgh – comparative genomic hybridization, orf – open reading frame
authors' contributions
ba co-conceived the algorithm, was the primary author of the software, drafted the manuscript, and assisted in the data and statistical analyses.
mg assisted in authoring the software, designed the graphical user interface, and was responsible for making the software distributable.
as was responsible for the statistical analysis, and assisted in drafting the manuscript.
bb assisted in the development of the software and data analysis.
jg assisted in the data analysis, offered technical expertise, and assisted in drafting the manuscript.
gr assisted in the data analysis.
gs assisted in the data analysis.
np conceived of the study, co-conceived the algorithm, assisted in the statistical analysis, and provided technical expertise.

 comparative genomic hybridization is a powerful technique to determine the differences between the genomes of different cell types or organisms. typically, genomic dna from known and experimental genomes is labeled and hybridized to an array of dna sequences prepared from the known genome. intensities of hybridization of the two samples are compared to determine the relative copy number of each target gene in the experimental genome as compared to the known genome. many studies involve determining the genomic abnormalities in tumor cells, but the technique has also been used in bacteria and yeast to investigate diverse topics such as genotyping, pathogenicity, and microbial evolution. cgh experiments on cancerous and non-cancerous tissues are primarily used in determining the relative copy number of sequences in the tumor cells as compared to the normal tissue for the purpose of identifying genetic elements responsible for cell transformation. to provide wide coverage of relatively large genomes such as human on a small number of arrays requires using large genomic fragments such as bacterial artificial chromosomes, or by using a large number of arrays. experiments in yeast and bacteria can typically be conducted at much higher resolution due to their smaller genomes, although comparisons must be limited to closely related species, as evolutionary divergence will affect hybridization dynamics if the species are significantly diverged. a single spotted cdna or oligonucleotide array can easily represent every open reading frame in the genome, and a high-density microarray can provide sequences that cover the entire genome. typical high-density microarrays contain hundreds of thousands of short oligonucleotide sequences. the substantial variability in performance of different probe sequences and the large number of individual measurements taken complicate the analysis of hybridization data. many methods have been developed for analyzing data from human array cgh using cdna or bac arrays. a common theme emerging from comparisons of closely related bacteria is genomic variability due to insertion and deletion of genes and gene islands. regions that are present in a sequenced genome and absent or significantly diverged in an experimental genome can be readily detected by hybridization. we have termed these "variable regions" because based on cgh alone, it is not possible to distinguish between deletions and sequences that have diverged to a degree that prevents or reduces hybridization. defining the boundaries of these regions from high-density microarray data involves scoring each probe as indicative of either a conserved or variable sequence and grouping probes with consistent scores into larger segments with defined boundaries. while there are many methods of scoring probes, boundary definition remains a challenge. a simple approach to detect deleted genes is to average probe values across each gene and select genes with unusually low relative hybridization values. this method defines the units-of-interest as entire genes and does not attempt to identify variable regions that lie outside of genes or only partially span gene boundaries. larger clusters of variable genomic regions are defined by grouping adjacent variable genes, but definition of the boundaries of these clusters can be sensitive to inclusion or exclusion of individual genes in the initial analysis. an approach developed for bacterial cgh, implemented in a program called tstep, identifies deletions using microarray data by scoring probes as absent or present based on perfect match and mismatched probe intensities as well as consideration of neighboring probe data using a sliding window. a heuristic set of rules is then applied to find clusters of absent probes. other programs, developed to analyze mammalian cgh data, analyze data by smoothing probe intensities, followed by breakpoint identification by scanning for areas of high contrast between smoothed data values of neighboring probes. in our efforts to analyze cgh data from high-density microarrays, we found several common drawbacks with existing methods. many methods simply score probes or genes as present or absent but do not provide a mechanism for defining region boundaries. most of the available software for defining boundaries was developed for analyzing data from human spotted microarrays, and we encountered problems such as excessive setup and/or run time, dependence on genome annotation, input file format restrictions, and an inability to handle large data sets. the data we used to develop our approach come from a high-density array with nearly individual mer probes, whereas the human data comes primarily from spotted arrays with far fewer probes of longer length. the larger size of our dataset and greater variability inherent in the performance of short probe sequences compared to longer probes precludes the use of most existing approaches. for these reasons, we developed cghscan, a program that uses an iterative random walk method to detect variable regions using high-density cgh microarray data. the algorithm identifies variable regions in data with high levels of noise independently of genome annotation, providing a rapid method for defining differences in high-density microarray cgh studies. implementation cghscan operates on a data set d comprised of binary data wherein each probe has been scored either conserved or variable in the experimental genome. the data is input as a tab delimited text file containing the genomic coordinate of each probe along with which chromosome it corresponds to and the data value. use of a proprietary file format was done to make the program usable irrespective of the software used by the experimenter to analyze their microarrays. we score conserved probes as and variable probes as - but cghscan can operate on any binary numerical scoring method, providing that the score of the variable probes is less than the score of the conserved probes. we strongly advise users to select a statistically rigorous method to score individual probes such as gack or ebarrays; however, if the data supplied by the user is in the form of raw numerical values for each probe cghscan will perform a simple scoring based on a user-defined cutoff value. since the grouping of probes into variable genomic regions relies on the scores of individual probes, the choice of an appropriate method for initial scoring of probes is important and it is advisable to try using different scoring thresholds to confirm that the results are robust for a given data set. cghscan requires the relative physical location of each probe sequence in the reference genome. the random walk as a method for boundary definition while many methods of analyzing binary data have been described, we chose the random walk. a one-dimensional random walk occurs on a line, where a series of equidistant steps are taken in one of the two available directions. the probability of taking a step down is defined as p, while q is the probability of taking a step up. a random walk of n steps is necessarily comprised of a number of down steps, nd and up steps, nu such that nd + nu = n. the probability of any single random walk occurring is given by the equation!nd!nu!pndqnu mathtype@mtef@5@5@+=feaafiart1ev1aaatcvaufkttlearuwrp9mdh5mbpbiqv92aaexatlxbi9gbaebbnrfifhhdyfgasaach8aky=wiffydh8gipec8eeeu0xxdbba9frfj0=oqffea0dxdd9vqai=hguq8kuc9pgc9s8qqaq=dirpe0xb9q8qilsfr0=vr0=vr0dc8meaabaqaciaacagaaeqabaqabegadaaakeaadawcaaqaamaabmaabagaemoba42aasbaasqaaiabdsgakbqabagccqghrawkcqwgubgbdawgaawcbagaemydauhabeaaaogaayjkaiaawmcaaiabcgcahaqaaiabd6gaunaabaaaleaacqwgkbazaeqaaogaeiyiaeiaemoba42aasbaasqaaiabdwha1bqabagccqgghaqiaagaemiuaa1aawbaasqabeaacqwgubgbdawgaaadbagaemizaqgabeaaaagccqwgrbqudaahaawcbeqaaiabd6gaunaabaaameaacqwg1bqdaeqaaaaaaaa@4619@ which is the binomial probability. in order to define the boundaries of variable regions, the genome-ordered probes are scanned beginning with probe d until a variable probe is encountered, probe dinit, and a one-dimensional random walk begins, with conserved and variable probes contributing + and - respectively. assuming that the genomes being compared consist largely of conserved regions, the walk will eventually return to the origin at probe dori, and have a minimum at probe dmin. in the event of multiple identical minima, the dmin closest to dori is defined as the location of the minimum. if the walk does not reach the origin before the end of the chromosome, the last probe in the chromosome is defined as dori. the boundaries of the variable region are defined by dinit on the left side and dmin on the right, as this represents the longest region of local concentration of variable probes. the coordinates are recorded as a region and the scan resumes at probe dmin + where, once again, all conserved probes are ignored until the first variable probe is encountered, and another random walk is initiated. this process is repeated until the end of the genome is reached. analyses on circular genomes where there is the possibility that d lays within a variable region should be re-analyzed with an alternate d to ensure proper analysis of the region. multiple chromosomes of a genome are scanned separately and in parallel. a second iteration scans for conserved regions within the regions found in the first iteration. this is necessary because the random walk tends to combine variable regions separated by a relatively small conserved region. the requirement for ∑ assumes that each variable region will be followed by a sufficiently long stretch of conserved probes. when two regions are close together, they can be grouped together by the random walk. solving this problem requires an automated method for identifying significant local minima, while ignoring minor local minima caused by noise. this can be approached in two different ways. one possible solution is to record the most recent minimum dm and as the walk proceeds calculate the statistical significance of the regions defined by dm1+ and the current probe. using this method, the walk does not need to return to the origin, but merely significantly far away from the minimum providing a new minimum is not established. the alternative solution, employed in cghscan, scans each region identified in the first iteration for conserved regions, using the same random walk method. using this approach we can statistically evaluate the identified conserved regions as a group and are able to employ a correction for multiple tests. regions found in this second iteration are similarly scanned for variable regions in a third iteration, which are scanned in for conserved regions in a fourth iteration, and further iterations are performed until no additional regions are detected. statistical analysis of regions for an operation of n iterations, probabilities are calculated for regions defined in the nth iteration first. as these regions are detected as lying within regions defined in the previous iteration, p and q are defined as the proportion of variable and conserved probes, respectively, that comprise the regions identified in the previous iteration. regions defined by a random walk from dinit to dmin can be statistically evaluated using the binomial distribution. for smaller regions, the binomial probabilities can be calculated directly. while the binomial probability is a useful metric for the user to evaluate regions, all evaluation of these regions for statistical significance are performed using the method developed by tarone which employs the minimum possible probability pn, which is described below. for larger regions, we use an approximation of the binomial probability. larger regions are defined as those where the number of probes multiplied by the smaller of p or q is greater than or equal to and binomial probabilities are approximated using the z-test. for regions where the binomial probability is approximated with a z-test, a bonferroni multiple testing correction is used. for the smaller regions, a modified bonferroni correction described by tarone developed specifically for discrete data is used. briefly, for any region with a length of n probes, pn represents the minimum possible binomial probability for the region. beginning with an integer k = the regions that satisfy the criterion k*pn < α comprise a subset n of all total regions n in a given iteration. integer k is increased by one until k ≥ n. this modification removes regions from consideration that could not reject the null hypothesis under any circumstances and makes the correction less conservative. a standard bonferroni correction is applied to the remaining regions using the minimum binomial probability for each region. regions that are called significant after the multiple correction tests are then "added back in" to the regions in the previous iteration in which they were found. for example, a putative variable region from iteration n- spanning probes da to dz containing a statistically significant conserved region from iteration n spanning probes dx to dy will be broken into two regions, one spanning da to dx- the other spanning dy+ to dz. this process is repeated with iteration n- and so on until iteration is reached, where regions are evaluated against p and q defined as the proportion of variable and conserved probes in the genome, respectively. output the output is a table reporting the genomic coordinates of all predicted variable regions with their binomial probability or approximation. two additional tables are output, one detailing all larger variable regions that were identified using the z test, and another for the smaller variable regions analyzed by the modified bonferroni correction. in the last two tables, variable regions are reported and are grouped by the iteration that they were identified in regardless of whether they passed the bonferroni correction to permit users to evaluate regions near the cutoff.  cghscan was used to analyze microarray data from a study by rajashekara et al. comparing the sequenced pathogen brucella melitensis strain m with the closely related brucella ovis strain reo the mbp b. melitensis genome is contained on two chromosomes. the microarray contains probes per open reading frame, plus a number of probes corresponding to intergenic regions, which combined provide extensive, albeit partial, coverage across the entire genome. the trimmed mean of the middle 50% of ordered probe intensities was used to calculate a scaling factor to normalize probe intensities from three replicate experiments for each strain, which were then averaged. log ratios of the average probe intensities between the experimental and known genome were calculated and input into cghscan using a significance value of. we tried using two different log ratio thresholds calculated by gack, a program designed to identify probes with extreme ratio values from microarray data. the first threshold, -, was calculated using the most lenient gack setting for creating binary data, and the second, -, using the default setting, which results in fewer probes being classified as variable. b. ovis contains nine known deleted regions confirmed by sequencing as compared to b. melitensis. cghscan identified eight of the nine regions at both ratio thresholds, two in chromosome i, six in chromosome ii. cghscan successfully identified these eight regions with a ratio threshold as low as -, indicating that the algorithm is effective over a range of ratio thresholds. the only previously known deletion that cghscan did not identify is a bp deletion that was not detectable using our approach given the probe density of the microarray. some of the larger known deletions were identified by cghscan as a cluster of smaller variable regions, particularly with the lower ratio threshold. this is partially due to the fact that the control strain contains known duplications of portions of these regions, which results in higher log ratios than expected in those areas. the use of the lower ratio threshold can cause regions to become segmented due to the fact that more probes are called conserved, but segmented regions are in our experience easily recognizable as a single entity. in addition to identifying eight of the nine known deletions, many additional putative variable regions were identified using either cutoff, with more regions being detected using the less stringent cutoff. one of these regions contains a repeat present in multiple copies in m, but apparently single or at least fewer copies in reo causing reduced sequence dosage and apparent variation. most of the putative variable regions had not been previously identified. the analysis was repeated using data normalized against the mean instead of a trimmed mean to test performance using an alternative normalization method. gack was used to establish the default cutoff and a low-stringency cutoff. once again, cghscan identified the same eight known deletions, as well as other putative variable regions, with more overall regions being detected using the less stringent cutoff. using the more stringent cutoff, the regions detected using data normalized against the mean vs. a trimmed mean were essentially identical, with only one region differing out of about using the less stringent cutoff, the differences were mostly in agreement as well, but did show more variation than at the more stringent cutoff. cghscan has advantages over existing software, primarily because it was specifically designed to identify clusters of variable probes from datasets consisting of hundreds of thousands of individual probe measurements from high-density arrays. other tools accomplish similar analyses, but typically assume that the data will consist at most tens of thousands of measurements from a single array, such as data generated from spotted arrays or from high-density arrays with data condensed into genic units. for example, cgh-miner version, which implements the "cluster along chromosomes" or clac method, and acgh-smooth version. require data input as microsoft excel files, which cannot accommodate the large file sizes generated by high-density microarray experiments. we encountered errors using data sets containing as low as probes using cgh segmentation, and after hours it was unable to complete the analysis of a data set consisting of probes, less than one tenth that of a typical high-density microarray data set. cghpro is a stand-alone java application that provides a comprehensive environment for analyzing cgh data that includes data normalization, analysis and visualization components. the software, however, requires a mysql database and the statistical program r, making installation difficult for many potential users without the expertise necessary to install the multiple required components. cgh-explorer is configured to analyze only data from human arrays and we were unable to reconfigure it to use another genome. in order to assess the performance of existing applications on high-density microarray data sets and compare their results to cghscan it was often necessary to use only a portion of the data set, otherwise many programs would not be able to accommodate the data or complete the analysis. applications with the option to define parameters were all run at their default settings. as previously mentioned, using cgh segmentation we were unable to obtain results using a data set of as few as probes, which itself was too small a portion of the data to do a meaningful comparison. charm version was the only program that we tested that was able to analyze our entire data set. using the default settings in charm, the program was able to identify five of the nine known deletions in b. ovis, with one of the regions missed being a large deletion in chromosome it should be noted that the default settings for charm do appear to be more conservative than the settings we used to test cghscan. our ability to test multiple different settings using charm was complicated by excessive runtime, presumably due to the large sizes of our data files. charm required hours to analyze a single data set, compared to seconds for cghscan, and charm was frequently unable to complete the analyses. acgh-smooth version. limits its input to microsoft excel files which have a limit of rows of data. we found that in practice using data sets of greater than probes in acgh-smooth caused errors that did not permit completion of the analysis. we ran a data set consisting of probes from chromosome that contained all seven of the known deletions on that chromosome. acgh-smooth identified four of the seven regions, failing to detect the three smallest regions. we had similar results when using the r package glad version. glad was also unable to do a complete analysis on our entire data set, but was capable of analyzing the entire chromosome data set of probes. glad identified the three largest regions, but failed to detect the four smaller regions. cghscan was able to identify six regions, but also missed the smallest region, a bp deletion that proved to be undetectable by any method. in general, the existing programs worked well on sample data when available, and implement useful algorithms for the analysis of human array cgh data. the programs are not, however, well suited to high-density microarray cgh data analysis, as many could not accommodate large file sizes or operate in a reasonable amount of time. additionally, many programs available require genome annotation and analyze gains and losses on a gene-by-gene basis. high-density microarrays can measure differences on a much a smaller scale, and can even identify breakpoints that occur within genes or between genes that are refractory to gene-by-gene approaches. these difficulties led us to the conclusion that we needed to develop cghscan to address the specific need we had for high-density microarray cgh data analysis.  we have developed a robust and efficient method for detecting variable regions between genomes using comparative genomic hybridization data from high-density microarrays. the method is relatively insensitive to data normalization methods and cutoff selection and uses rigorous statistical analysis. the method successfully identified all eight detectable deleted regions identified in a published comparison of b. ovis as compared to b. melitensis, as well as numerous additional regions that are predicted to differ between the genomes of these organisms. availability and requirements project name: cghscan project home page: operating system: platform independent programming language: java other requirements: java runtime environment.2 license: gnu general public license use: free, no license required abbreviations cgh – comparative genomic hybridization, orf – open reading frame authors' contributions ba co-conceived the algorithm, was the primary author of the software, drafted the manuscript, and assisted in the data and statistical analyses. mg assisted in authoring the software, designed the graphical user interface, and was responsible for making the software distributable. as was responsible for the statistical analysis, and assisted in drafting the manuscript. bb assisted in the development of the software and data analysis. jg assisted in the data analysis, offered technical expertise, and assisted in drafting the manuscript. gr assisted in the data analysis. gs assisted in the data analysis. np conceived of the study, co-conceived the algorithm, assisted in the statistical analysis, and provided technical expertise. 
the same result was obtained using two different normalization methods and two different scores to classify data for individual probes as representing conserved or variable genomic regions. the program, cghscan, uses an iterative random walk approach integrating multi-layered significance testing to detect these regions from comparative genomic hybridization data. when applied to comparative genomic hybridization data from a published experiment, cghscan identified eight of nine known deletions in a brucella ovis strain as compared to brucella melitensis. cghscan is an effective tool for analyzing comparative genomic hybridization data from high-density microarrays. we present an algorithm for analyzing microarray hybridization data to aid identification of regions that vary between an unsequenced genome and a sequenced reference genome. this technique has been applied to detecting differences between normal and cancerous tissues in eukaryotes as well as genomic variability in microbial strains and species. the algorithm is capable of accurately identifying known variable regions and is tolerant of high noise and varying methods of data preprocessing. statistical analysis is used to define each variable region providing a robust and reliable method for rapid identification of genomic differences independent of annotated gene boundaries. comparative genomic hybridization can rapidly identify chromosomal regions that vary between organisms and tissues. available methods for analyzing these experiments typically confine analyses to data from pre-defined annotated genome features, such as entire genes. the density of oligonucleotide probes available on current microarray platforms is particularly well-suited for comparisons of organisms with smaller genomes like bacteria and yeast where an entire genome can be assayed on a single microarray with high resolution. many of these methods are ill suited for datasets with the number of measurements typical of high-density microarrays.
 comparative genomic hybridization can rapidly identify chromosomal regions that vary between organisms and tissues. this technique has been applied to detecting differences between normal and cancerous tissues in eukaryotes as well as genomic variability in microbial strains and species. the density of oligonucleotide probes available on current microarray platforms is particularly well-suited for comparisons of organisms with smaller genomes like bacteria and yeast where an entire genome can be assayed on a single microarray with high resolution. available methods for analyzing these experiments typically confine analyses to data from pre-defined annotated genome features, such as entire genes. many of these methods are ill suited for datasets with the number of measurements typical of high-density microarrays.  we present an algorithm for analyzing microarray hybridization data to aid identification of regions that vary between an unsequenced genome and a sequenced reference genome. the program, cghscan, uses an iterative random walk approach integrating multi-layered significance testing to detect these regions from comparative genomic hybridization data. the algorithm tolerates a high level of noise in measurements of individual probe intensities and is relatively insensitive to the choice of method for normalizing probe intensity values and identifying probes that differ between samples. when applied to comparative genomic hybridization data from a published experiment, cghscan identified eight of nine known deletions in a brucella ovis strain as compared to brucella melitensis. the same result was obtained using two different normalization methods and two different scores to classify data for individual probes as representing conserved or variable genomic regions. the undetected region is a small deletion that is below the resolution of cghscan given the array design employed in the study.  cghscan is an effective tool for analyzing comparative genomic hybridization data from high-density microarrays. the algorithm is capable of accurately identifying known variable regions and is tolerant of high noise and varying methods of data preprocessing. statistical analysis is used to define each variable region providing a robust and reliable method for rapid identification of genomic differences independent of annotated gene boundaries. 