BACKGROUND
horizontal gene transfer is an important mechanism for the evolution of microbial genomes.
in  <dig>  it was first observed that large blocks of horizontally acquired foreign sequences occur in chromosomes of pathogenic bacteria, and those regions are highly correlated with pathogenicity  <cit> .
some of these possess mobile elements consisting of a gene for specific recombinase and sequences having characteristics of integration sites.
some others, despite their apparently foreign nature, lack insertion sequences, recombinase genes and specific att sites, and they may contain only fragments of mobility genes.
in the latter case, the mobility sequences were probably lost in course of evolution after their integration into the bacterial genome  <cit> .
the first known foreign dna blocks that were proved to be associated with virulence genes of pathogenic bacteria were named as pathogenicity islands  <cit> .
later on, genomes of non-pathogenic bacteria have been shown to contain foreign gene blocks, which are not associated with virulence.
these gene blocks determine various accessory functions like secondary metabolic activities, antibiotic resistance, symbiosis and other special functions related to the survival in harsh environmental conditions  <cit> .
subsequently, all foreign gene blocks are collectively named in the literature as genomic islands   <cit> .
there is an extensive literature on the study of gis in prokaryotic genomes  <cit> .
gis in prokaryotic genomes often contain horizontally transferred genetic materials as evident from the presence of integrase, transposons, phage mediated genes, etc.
in these islands.
consequently, they are critically important in the study of the evolution, the pathogenesis and other special features of prokaryotic genomes.
several methods have been reported and discussed in the available literature for detecting gis in prokaryotic genomes  <cit> .
many of these methods use markers such as transposons, proximal trnas, flanking repeats etc.
to identify gis  <cit> .
mantri and williams  <cit>  used trna and tmrna as markers.
they further searched for the phage integrase and passed through different filtration procedures for the identification of gis.
ou et al.
<cit>  also started with trna and tmrna genes as primary markers, and after passing through different filtration techniques, the gis were identified.
in another previous study, the authors have identified the gis after performing the cluster analysis of the chromosomal fragments, which are formed by fragmenting the chromosomes based on locations of transposons  <cit> .
such methods, which are based on standard markers, are particularly useful for detecting gis acquired by a genome from another compositionally close donor genome or those, which have become compositionally close to the host genome due to the amelioration process.
in such cases, the islands may not bear any compositional signature that can be used to distinguish it from rest of the host genome.
consequently, identification of such islands has to rely on possible presence of structural features, like trna, direct repeats , integrase gene etc.
however, there are limitations of such methods, which are based on standard markers.
firstly, only the gis, which are associated with standard markers, can be identified by this method.
secondly, there may be intra-chromosomal rearrangements, and islands may no longer be in the proximity of those standard markers after such rearrangements.
consequently, many gis may not be detected by marker-based methods  <cit> .
in an earlier paper  <cit> , the authors used discriminant analysis, a supervised statistical technique, based on a training data-set that was formed by the authors using the aggregation of known gis from different organisms.
however, unless there are several organisms with some statistical similarities in their genome sequences as well as in their known gis, such an aggregation to form the training data-set may not be appropriate.
besides, the gis available and known a priori for a single organism may be very few at the beginning of the investigation.
in this paper, we have developed a method that does not use any standard marker when islands are searched in the genome.
islands identified by this method may, however, be confirmed subsequently by supporting factors that include such markers as well as possible presence of known horizontally transferred genes .
this will be clear in the section where we discuss the results.
further, the proposed method is unsupervised in nature, and it does not require any training data set for its implementation.
our method searches for islands in a prokaryotic chromosome using a probing window that slides over the entire chromosome and also varies in its size.
for a given size and a given position of that probing window, the segment of the chromosome captured by the window is compared with the rest of the chromosome by means of statistical tests.
the outcome of each such test is a statistical p-value that lies between zero and one.
a low p-value, which indicates a significant difference between the segments captured by the probing window and the rest of the chromosome, bears evidence for the probing window having a substantial overlap with a gi.
all these p-values obtained from statistical tests carried out at different locations and for different sizes of the probing window can be represented by a 3d plot, which enables visualization of locations and sizes of gis in the chromosome.
for the determination of gis, window based methods have been used in some earlier studies.
the gis of pseudomonas putida kt <dig> were determined by analyzing the compositional bias of the mono-, di- and tetra-nucleotide contents in the segment of the genome under the probing window of  <dig> bp that slides in steps of  <dig> bp  <cit> .
these authors, however, have used windows with fixed lengths, and there is no objective guideline for how to determine that length in practice.
zhang and zhang  <cit>  used a windowless method for displaying the distribution of genomic gc content, and the cumulative gc profile was used by them for the determination of gis.
abrupt jump in cumulative gc profile, which is due to relatively different gc content of an island, enabled them to identify the gi.
but this was done in a subjective manner and neither clear quantitative measure nor any formal statistical test for assessing the abrupt change in the cumulative gc profile was proposed by these authors.
known methods for identifying gis are primarily based on gc contents of the islands, their oligo-nucleotide usage patterns and the codon usage biases in the genes present in the island  <cit> .
when a fixed segment under the probing window is compared with the whole chromosome, which may contain several gis , such a comparison is likely to get influenced by those islands, and this reduces the resolution of the comparison.
in order to cope with this problem, we have introduced a refinement phase in our algorithm, where the fixed segment under the probing window is compared with randomly selected segments from the chromosome excluding the parts detected as 'putative gi's' in the first phase.
this will be discussed in detail in the section on methods.
various procedures studied in the literature generally lack a formal and rigorous statistical treatment of the problem of comparing a segment of the chromosome with the rest of the chromosome in order to decide whether the segment is the part of a gi or not.
often no formal statistical test is carried out, and the decision to declare a segment as part of an island is done in a subjective way as mentioned earlier.
in some other cases, statistical tests have been carried out in a way that is somewhat questionable in the sense that the determination of the critical values and the p-values is not adequately justified due to lack of a rigorous statistical distribution theory of the deviance measures used for such tests.
yoon et al.
<cit>  used mahalanobis distance to evaluate the deviation of the codon usage of a gene from the mean of that in the genome.
they assumed normal distribution of codon frequencies without much justification for it, and converted the mahalanobis distance into a p-value using the χ <dig> distribution function.
they have considered a gene as extraneous in codon usage if its p-value was less than  <dig>   <cit> .
on the other hand, zhang and zhang  <cit>  obtained their results based on codon usage and amino acid usage biases using different cut-offs for the p-values.
in some earlier studies  <cit> , authors used higher order motifs to capture the compositionally deviating regions from the genome.
in another study by vernikos et al.
<cit> , authors used variable order motifs and relative entropy for the detection of compositionally deviating regions.
in our method, we have used a monte-carlo statistical test, which is partly motivated by the idea of the bootstrap method in statistics  <cit>  for comparing the segment under the probing window with randomly selected segments from the rest of the chromosome.
such monte-carlo statistical tests based on randomly selected segments of the chromosome can be supported by simple and precise statistical distribution theory.
methods
let us denote a whole chromosomal sequence of an organism by s, and s will denote a given segment of s. in order to assess whether s differs significantly from the rest of s, we need a measure of distance that can be used for quantitative comparison between the given segment s and any other segment s' of s not having any overlap with s. such a distance measure, which we may denote as d, can be based on gc contents of s and s' or their oligo-nucleotide distributions.
for instance, one may use the absolute distance, the euclidean distance or kullback-leibler divergence computed from oligo nucleotide frequencies.
alternatively, for annotated genomes, one may form the distance measure d by comparing the gene contents of s and s' and their codon and amino acid usage biases.
merkl et al.
<cit>  used codon usage analysis of two species assuming the similarity of codon usage in phylogenetically related species.
weinel et al.
<cit>  analyzed the di-nucleotide usage and the tetra-nucleotide usage in sliding windows and compared them with the di-nucleotide usage of the whole genome and uniform tetra-nucleotide usage respectively.
in the study by zhang and zhang  <cit> , putative gis detected by cumulative gc profile were further analyzed by codon usage and amino acid usage of those regions compared to the whole chromosome s. comparison of the codon usage and oligo-nucleotide usage of the given segment s with those for the whole chromosome s has some drawbacks because s may contain several gis.
in some cases, the total size of the gis in s would be much larger than the length of s, and it can be as large as 20% of the size of s  <cit> .
this may statistically contaminate values of various parameters related to gc content as well as oligo-nucleotide and codon usage biases when computed for the entire chromosomal sequence s. this is likely to reduce the resolution of the comparison.
in our algorithm, this issue is carefully addressed by introducing a refinement phase, which has been discussed below.
in our method, the comparison between s and the rest of s is based on n randomly selected segments s <dig> , s <dig> , s <dig> , .........s <dig> n from the chromosome s, each of which has the same length as that of s, and none of them has any overlap with s. we also choose n random pairs of segments , , , ......... from s, where for each  <dig> ≤ i ≤ n, s <dig> i and s <dig> i are independently selected, and each of them has the same length as the given segment s and no overlap with s. then, we can compute the distances  d <dig> i = d and d <dig> i = d for  <dig> ≤ i ≤ n and form the following two sets of distance values:
d <dig> = {d <dig> i| <dig> ≤ i ≤ n} and d <dig> = {d <dig> i| <dig> ≤ i ≤ n}.
if s happens to be a part of a gi with characteristics very different from the rest of s, the values in d <dig> are expected to be larger than those in d <dig>  otherwise, the values in the two sets are expected to be of the same order of magnitudes.
statistical test for comparing s with the rest of s
in view of the way the distance values in d <dig> and d <dig> have been obtained by random sampling of segments of s, the values in each of these two sets can be viewed as independent and identically distributed random variables, and the values in d <dig> will be completely independent from the values in d <dig>  the problem of comparing the values in the two sets d <dig> and d <dig> can be formulated as a statistical testing problem, where the null hypothesis can be taken as h0: "the expected value of an element in d <dig> is the same as that of an element in d <dig> " and the alternative hypothesis would be ha: "the expected value of an element in d <dig> is larger than that of an element in d <dig> " we set
m1=n−1∑i=1nd <dig> i,s12=n−1∑i=1n <dig>
m2=n−1∑i=1nd <dig> i,s22=n−1∑i=1n <dig>
then, each of m <dig> and m <dig> is approximately normally distributed being an average of independent and identically distributed random variables by the well-known central limit theorem in probability theory if n is large.
further, m <dig> and m <dig> are independently distributed, and s <dig> 2/n and s <dig> 2/n will be the standard estimates for their variances respectively.
hence, the statistic
z=m1−m2{+}
will be approximately normally distributed for large n, and the mean of that normal distribution will be zero if h <dig> is true, and it will be positive if ha is true.
the variance of that asymptotic normal distribution will be one under both hypotheses.
consequently, z can be used as a test statistic for testing h <dig> against ha in a one-sided test.
here, the p-value can be computed using the observed value of z for the given segment s under the probing window and the standard normal distribution.
this way of assessing the statistical significance of the evidence for s being part of a gi in the chromosome s using a monte-carlo test based on random samples of segments from s is partly motivated by the idea of the bootstrap  <cit> .
in the present study, we have used n =  <dig>  for larger values of n, the normal approximation will be more accurate for the distribution of the test statistic, but the corresponding computation time will also increase linearly with n, and this might lead to a substantial computational cost when we want to do the analysis for multiple segments with varying sizes located at different positions in the genome.
for some smaller chromosomes, we have tried values of n up to  <dig>  but the results did not change significantly.
if for some reasons , one is forced to use smaller values of n, the normal approximation for the distribution of z will not be valid.
in that case, one may work with a different formulation of the statistical hypotheses as follows.
the null hypothesis in that case can be formulated as h0: "the statistical distribution of an element in d <dig> is the same as that of an element in d2", and the alternative hypothesis can be formulated as ha: "the distribution of an element in d <dig> is stochastically larger than that of an element in d2".
with these re-formulated hypotheses, one can carry out the test using two-sample kolmogorov-smirnov statistic  <cit>  or wilcoxon-mann-whitney statistic  <cit> .
these tests, which are computationally more expensive than the test based on normal distribution, have been used by previous authors  <cit> .
however, the power of such non-parametric statistical tests for detecting gis tends to be less than the preceding test based on normal distribution, which is applicable for relatively larger values of n.
statistical analysis with segments having variable sizes and locations
in order to identify islands at different locations of the chromosome and to determine the stretches of those islands, it is necessary to carry out our statistical analysis using a probing window that slides across the chromosome and also varies in its size.
the statistical test described above can be implemented for any location and size of the segment s under that probing window, and the p-value can be computed.
it would be useful to plot these p-values so that one can visualize possible locations of the islands in the chromosome as well as their stretches.
such a plot of p-values would also enable us to assess visually the statistical significance of the evidence for or against different segments of the chromosomes to be possible parts of gis.
for visual presentation of the 'putative gis' identified by the analysis described above, a 3d plot for a chromosome can be generated.
in this 3d plot, chromosomal locations of the probing window are plotted along the x-axis, corresponding probing window sizes are plotted along the y-axis, and the p-values in gray scale are plotted along the z-axis.
here, the p-value for a specific location and size of the window is plotted using a gray scale that changes gradually from black to white, where black corresponds to the extreme p-value =  <dig>  and white corresponds to the other extreme p-value =  <dig>  the white dots corresponding to higher p-values become almost invisible in the white background while dark dots corresponding to low p-values will be prominently visible marking the 'putative gis' in the chromosome.
for a specified value of p <dig> , one can determine all the segments of a chromosome that are associated with a p-value less than or equal to p <dig>  this will lead to the identification of some 'putative gis' having varying sizes and locations in the chromosome that are identifiable with p-values equal to p <dig> or smaller.
ranges of the 'putative gis' in terms of their chromosomal locations can be determined using the cut-off value p <dig> and considering a specified number of at least r overlapping windows of variable sizes having p-values smaller than or equal to p <dig>
further refinement of the 'putative gis' identified by the first phase of the algorithm
in the first phase of our analysis, the presence of several gis in the genome may statistically contaminate the randomly sampled segments by affecting their oligo-nucleotide distributions.
besides, 'putative gis' obtained using the first phase of the algorithm, are always of larger size than what they are supposed to be because of the presence of many 'false positives' .
to reduce the false positives and increase the resolution of our method, a refinement phase with a sliding probing window w of a fixed size over the regions detected as 'putative gis' by the first phase of the analysis has been performed.
random samples of genomic segments in the refinement phase were chosen from the genome excluding the regions detected as 'putative gis' in the first phase.
this substantially reduces the influence of various possible islands present in s on any statistical comparison between w and the randomly selected segment, and that in turn increases the resolution of the comparison.
the comparison between a probing window w and the rest of s excluding the regions under'putative gis' is again based on n randomly selected segments w <dig> , w <dig> , w <dig> , .........w <dig> n each of which has the same length as that of w. the statistical analysis is very similar to that used in the first phase.
the p-values are generated using monte-carlo tests carried out at variable locations of the probing window with a fixed size.
a smaller probing window is recommended for the refinement phase as it will provide a way of precisely detecting the gis.
gene order conservation is rarely observed in distantly related species and several rearrangements and movement of genes occurs frequently.
so, some genes, which are not horizontally acquired from other species, may be present within a 'putative gi' identified in the first phase, and to some extent, this problem is taken care of by the use of a smaller probing window.
however, the use of smaller probing window requires randomly sampled segments from non-contaminated stretches of the genome, and those stretches are available after running the first phase.
further, the probing window should not be so small that it can be dominated by a single gene, which would increase the effect of codon biases or amino acid biases related to the level of expression or protein function.
smaller probing windows are not recommended in the first phase because it increases the computational cost during the first phase.
the use of smaller probing windows that slide over the genome lead to a large number of statistical tests, and this may produce many false positive results.
further, there are high chances of substantial overlap of a randomly selected window in the first phase with an island in the genome containing horizontally acquired materials.
as in the first phase of the analysis, for a specified value of p <dig> , one can again determine all the segments of a 'putative gi', which is identified in the first phase, that are associated with a p-value less than or equal to p <dig>
the entire methodology is presented in the form of a flow chart in fig.
1a, b, and we have named our method as design-island .
choice of different parameters associated with the algorithm
in the following section, we have presented results obtained using the absolute distance based on tetra-nucleotide frequencies.
those results are obtained using p <dig> =  <dig>  and r =  <dig> in first phase and p <dig> =  <dig>  in the refinement phase.
the value of p <dig> in the first phase was relaxed to  <dig> , and it was chosen in such a way that most of the horizontally acquired stretches of the genome could be captured by the 'putative gis' detected in the first phase.
after we obtain the 'putative islands', we would be able to generate some statistically non-contaminated stretches of the genome .
those stretches can be used for random sampling of segments in the refinement phase.
in order to determine the value of p <dig> in the refinement phase, we have carried out a performance assessment of our method for different values of p <dig> based on a dataset related to salmonella typhi ct <dig> generated by vernikos et al.
<cit> .
their method of constructing the dataset of putative horizontally transferred genes is discussed briefly in the section on results and discussion.
we have calculated the sensitivity , the specificity  and the accuracy  of our method for different values of p <dig> ranging from p <dig> =  <dig>  to p <dig> =  <dig>  .
the slopes of the curve for sn, sp and ac were also plotted for different values of p <dig> .
as this cut-off p-value increases, the specificity and the accuracy increase, but the sensitivity decreases.
we have observed that the specificity and the accuracy increase steadily up to p <dig> =  <dig>  , and then the slope of each of the two curves decreases .
the sensitivity was observed to decreases with the increase in the cut-off p-value, but in the region from p <dig> =  <dig>  to p <dig> =  <dig> , the sensitivity decreases slowly, and then it decreases much more sharply.
alternatively, one can determine the value of p <dig> using the roc curve approach.
when we used that technique with a range of p <dig> values from  <dig>  to  <dig> , it again led to the same value of p <dig> as the optimal, and we have chosen the cut-off p-value as p <dig> =  <dig>  for the refinement phase.
it is possible that for some other bacterial genomes, a different choice of p <dig> would be optimal depending on the nucleotide compositions of those genomes.
however, some empirical studies using this choice of p <dig> for some bacterial genomes other than s. typhi ct <dig> demonstrated reasonable performance of our algorithm.
we have carried out our analysis with distance measures based on oligo-nucleotides of different orders .
the islands detected by methods based on different orders of oligo-nucleotides did not differ considerably.
only in some cases either the boundaries of the segments of the 'putative gis' slightly differed or a single 'putative gi' broke into two or more segments.
in most of the organisms, the 'putative gis' detected using tetra-nucleotide analysis include those detected by other analysis based on other oligo-nucleotides, and the later analysis sometimes missed some of the important segments of the genomes containing known horizontally acquired materials.
as we will see in the section containing a comparative study of different methods, our method outperformed the method w <dig>  <cit> , which is a method based on octa-nucleotides, in many cases.
we have considered three types of distance measure computed using oligo-nucleotide frequencies.
these are the absolute distance, the euclidean distance and the kullback-leibler divergence.
but all these distances lead to almost the same result.
the 'putative gis' detected by methods based on different distances tend to differ in their boundaries to a small extent.
we have finally decided to use the absolute distance, which is computationally the simplest among all the distances considered.
before computing the distances, as some authors suggested  <cit> , one may normalize higher order oligo-nucleotide frequencies by lower order oligo-nucleotide frequencies based on markov type models.
one may, in principle, use distances computed using codon usage or amino acid usage biases instead of oligo-nucleotide distributions.
however, that will require the use of complete annotation of the entire chromosome and the gene content of each and every randomly selected segment for our monte-carlo test.
this makes the implementation of the method computationally challenging, and we have not pursued that here.
RESULTS
we have implemented design-island on the chromosome of salmonella typhi ct <dig> obtained from ncbi database  <cit> .
the co-ordinates of statistically significant genomic segments detected by design-island and their gene contents in the chromosomes of s. typhi ct <dig> are presented in additional file  <dig> and detected segments of salmonella typhi ct <dig> are discussed below.
salmonella typhi ct18
salmonella enterica serovar typhi , an aetiological agent of typhoid fever, is a serious invasive bacterial disease of human.
many s. enterica serovars actively invade the mucosal surface of the intestine but are normally contained in healthy individuals by the local immune defence mechanism.
however, s. typhi has evolved the ability to spread to the deeper tissues of human including liver, spleen and bone marrow  <cit> .
in s. typhi, thirteen pathogenicity islands  and five islands containing bacteriophages related genes have been reported  <cit> .
in s. typhi ct <dig>  design-island detected ninety seven 'putative gis' in the first phase, and after refinement, these islands are broken into two hundreds and twenty-one statistically significant genomic segments that include all of the gis detected in the previous studies.
major genes contained in these segments code for phage proteins, putative pathogenicity island proteins, virulence associated secretory protein, vi polysaccharide proteins, integrase, phage integrase, putative bacteriophage proteins, is element transposases, flagellar proteins, uv protection protein, type iii secretion system, type iii restriction-modification system, killing factor kica and b, different chains of nadh dehydrogenase and heat shock proteins.
among the newly detected genomic segments, the major genes present are those, which code for putative toxin like proteins, putative virulence proteins, putative phage proteins, integrase, type iii restriction modification system, some pseudo genes, some transporters, flagellar biosynthetic proteins and several accessory proteins, different chains of nadh dehydrogenase and atp synthase, penicillin binding protein, fimbrial subunits, lipopolysaccharide core biosynthesis protein, heat shock and cold shock proteins.
two 3d plots generated from the first phase of our algorithm and some representative 1d plots generated from the refinement phase of the algorithm applied to the chromosome of s. typhi ct <dig> are shown here in fig.
3a, b. the first plot corresponds to the stretch of the chromosome from the start of the chromosome up to  <dig>  mbp position , and the other plot corresponds to the stretch of the chromosome from  <dig>  mbp position up to the end .
representative 1d plots for four of the 'putative gis' detected in the first phase and enclosed in gray blocks are shown in the lower panel of the figures.
the 'putative gi' that stretches from  <dig> to  <dig> is fragmented into three segments, namely 11000– <dig> bp, 30000– <dig> bp and 50000– <dig> bp.
the 'putative gi' that stretches from  <dig> to  <dig> bp is fragmented into two segments, namely 1008250– <dig> bp and 1059250– <dig> bp.
the 'putative gi' that stretches from  <dig> to  <dig> bp is fragmented into three segments, namely 1872500– <dig> bp, 1903500– <dig> bp and 1911500– <dig> bp .
in fig.
3b, the 1d plot for the 'putative gi' that stretches from  <dig> to  <dig> bp is shown in the lower panel.
this 'putative gi' is fragmented into six segments, namely 4398500– <dig> bp, 4402500– <dig> bp, 4408500– <dig> bp, 4442500– <dig> bp, 4511500– <dig> bp and 4544500– <dig> bp.
the third, the fourth and the fifth segments of the above mentioned 'putative gi' contain mainly phage genes, some pseudo genes and the vi polysaccharide, which is the major virulence determinant in s. typhi.
after running the refinement phase, the genes excluded from the above mentioned 'putative gis' are mainly dna polymerase iii, theta subunit, transcriptional activator protein, putative transcriptional regulator, exodeoxyribonuclease x, ribosome modulation factor , possible sulfatase regulatory protein, serine/threonine protein phosphatase  <dig>  putative ion and/or amino acid symporter, aminopeptidase n and some hypothetical and conserved hypothetical proteins.
performance comparison with other methods
for performance assessment of design-island, a dataset of  <dig> manually curated putative horizontally transferred genes in s. typhi ct <dig>  generated by vernikos et al.
<cit>  were used.
s. typhi ct <dig> is a well-studied prokaryote in terms of its hgt events.
vernikos et al.
<cit>  selected s. typhimurium lt <dig> as a sister lineage to s. typhi, and the genome of e. coli k <dig> was chosen as an outgroup of s. typhi and s. typhimurium.
their main idea was that the genes present in all the three genomes form a set of core genes, while the rest of the genes represent either species or strain specific genes, and thus they may be considered as putative htgs .
the sensitivity , the specificity  and the accuracy  of design-island have been compared with those of six other methods available in the literature, namely w <dig>  <cit> , islandpath-gc , islandpath-db   <cit> , islander  <cit> , hgt-db  <cit>  and ivom  <cit> .
the results are summarized in fig.
<dig> accompanied with its data table.
the sensitivity of design-island is the highest  among the methods considered for comparison, the second in the list being ivom .
regarding the accuracy also, the design-island is in the highest position with an accuracy =  <dig> %, and ivom is in the second position with an accuracy =  <dig> %.
the third method in the list is w <dig> with accuracy =  <dig> %.
the specificity of design-island  is comparable with that of ivom  and w <dig> .
however, the specificity of design-island is low when compared with that of hgt-db  and islander .
note that design-island, ivom and w <dig> predicted a much larger number of putative horizontally transferred genes compared to the number of such horizontally transferred genes predicted by hgt-db and islander, and this largely explains the behaviour of different methods in terms of their accuracies as pointed out by earlier authors  <cit> .
co-ordinates of the detected segments and the percentages of the genome covered by  the 'putative islands' identified in the first phase of the algorithm,  genomic segments detected after the refinement phase are given in additional file  <dig>  further, in the last column of additional file  <dig>  the genes included in our identified segments along with the percentage of those genes in the entire collection of genes present in the annotated chromosome are presented.
the percentages of htgs identified by different methods are reported in additional file  <dig>
ribosomal proteins and many other highly expressed genes tend to deviate compositionally from the genomic background.
however, those genes may have limited mobility, and they may not transfer across species  <cit> .
for this reason, ribosomal proteins, other highly expressed genes with biased compositions and the stretches with heavy loads of ribosomal proteins are excluded from the segments obtained in the refinement phase of the algorithm following a similar approach taken by some earlier authors  <cit> .
CONCLUSIONS
the method proposed and discussed in this paper is an unsupervised method in the sense that it does not require any training dataset to begin with.
the method uses monte-carlo statistical tests that are implemented using randomly sampled segments, and normal critical values are used for the test statistic.
in many of the earlier methods, no statistical test has been performed, and in some cases, where statistical tests were carried out, the determination of the critical values and the p-values were not adequately justified due to lack of rigorous statistical distribution theory.
in design-island, such difficulties are effectively overcome by using monte-carlo statistical tests based on randomly selected segments from a chromosome.
we have carried out an elaborate comparative analysis involving different bacterial genomes, and it demonstrates that the performance of design-island is often comparable to many other well known methods in terms of their sensitivity, specificity and accuracy.
further, in some cases, design-island outperforms many of those competing methods.
design-island can detect new segments of bacterial genomes as parts of some gis that might have been missed by earlier methods.
for example, in the case of s. typhi ct <dig>  design-island has predicted some pathogenic or pathogenicity related genes like putative virulence proteins, putative phage proteins, integrase as horizontally acquired materials that were not detected by earlier methods.
availability and requirements
the computer program for design-island along with a 'readme' file can be downloaded from .
abbreviations
gis: genomic islands; dr: direct repeat; sn: sensitivity; sp: specificity; ac: accuracy; s. typhi: salmonella typhi; spis: salmonella pathogenicity islands
authors' contributions
rc was responsible for development and implementation of the computational analysis as well as drafting of the manuscript.
kc advised on data analysis and manuscript preparation.
pc advised on development of the methodology, data analysis, designing of the study and manuscript preparation.
all authors read and approved the final manuscript.
supplementary material
additional file 1
predicted islands and their gene content in salmonella typhi ct <dig>  the data provided presents genomic segments predicted by design-island and genes present in those islands.
click here for file
additional file 2
percent of genes detected as htgs in different methods.
the data provided presents percentage of genes  present in the detected islands using different methods.
click here for file
acknowledgements
the research of raghunath chatterjee was supported by a fellowship from the council of scientific and industrial research, government of india.
the research of probal chaudhuri was supported by grants from the council of scientific and industrial research, government of india and the department of biotechnology, government of india.
the authors are grateful to george vernikos of sanger institute for several helpful discussions over email and providing their data on salmonella typhi ct <dig> and computer programs related to their ivom algorithm.
the authors thank two anonymous referees for their careful reading of an earlier version of the paper and suggesting appropriate revision.

 horizontal gene transfer is an important mechanism for the evolution of microbial genomes. in it was first observed that large blocks of horizontally acquired foreign sequences occur in chromosomes of pathogenic bacteria, and those regions are highly correlated with pathogenicity. some of these possess mobile elements consisting of a gene for specific recombinase and sequences having characteristics of integration sites. some others, despite their apparently foreign nature, lack insertion sequences, recombinase genes and specific att sites, and they may contain only fragments of mobility genes. in the latter case, the mobility sequences were probably lost in course of evolution after their integration into the bacterial genome. the first known foreign dna blocks that were proved to be associated with virulence genes of pathogenic bacteria were named as pathogenicity islands. later on, genomes of non-pathogenic bacteria have been shown to contain foreign gene blocks, which are not associated with virulence. these gene blocks determine various accessory functions like secondary metabolic activities, antibiotic resistance, symbiosis and other special functions related to the survival in harsh environmental conditions. subsequently, all foreign gene blocks are collectively named in the literature as genomic islands. there is an extensive literature on the study of gis in prokaryotic genomes. gis in prokaryotic genomes often contain horizontally transferred genetic materials as evident from the presence of integrase, transposons, phage mediated genes, etc. in these islands. consequently, they are critically important in the study of the evolution, the pathogenesis and other special features of prokaryotic genomes. several methods have been reported and discussed in the available literature for detecting gis in prokaryotic genomes. many of these methods use markers such as transposons, proximal trnas, flanking repeats etc. to identify gis. mantri and williams used trna and tmrna as markers. they further searched for the phage integrase and passed through different filtration procedures for the identification of gis. ou et al. also started with trna and tmrna genes as primary markers, and after passing through different filtration techniques, the gis were identified. in another previous study, the authors have identified the gis after performing the cluster analysis of the chromosomal fragments, which are formed by fragmenting the chromosomes based on locations of transposons. such methods, which are based on standard markers, are particularly useful for detecting gis acquired by a genome from another compositionally close donor genome or those, which have become compositionally close to the host genome due to the amelioration process. in such cases, the islands may not bear any compositional signature that can be used to distinguish it from rest of the host genome. consequently, identification of such islands has to rely on possible presence of structural features, like trna, direct repeats, integrase gene etc. however, there are limitations of such methods, which are based on standard markers. firstly, only the gis, which are associated with standard markers, can be identified by this method. secondly, there may be intra-chromosomal rearrangements, and islands may no longer be in the proximity of those standard markers after such rearrangements. consequently, many gis may not be detected by marker-based methods. in an earlier paper, the authors used discriminant analysis, a supervised statistical technique, based on a training data-set that was formed by the authors using the aggregation of known gis from different organisms. however, unless there are several organisms with some statistical similarities in their genome sequences as well as in their known gis, such an aggregation to form the training data-set may not be appropriate. besides, the gis available and known a priori for a single organism may be very few at the beginning of the investigation. in this paper, we have developed a method that does not use any standard marker when islands are searched in the genome. islands identified by this method may, however, be confirmed subsequently by supporting factors that include such markers as well as possible presence of known horizontally transferred genes. this will be clear in the section where we discuss the results. further, the proposed method is unsupervised in nature, and it does not require any training data set for its implementation. our method searches for islands in a prokaryotic chromosome using a probing window that slides over the entire chromosome and also varies in its size. for a given size and a given position of that probing window, the segment of the chromosome captured by the window is compared with the rest of the chromosome by means of statistical tests. the outcome of each such test is a statistical p-value that lies between zero and one. a low p-value, which indicates a significant difference between the segments captured by the probing window and the rest of the chromosome, bears evidence for the probing window having a substantial overlap with a gi. all these p-values obtained from statistical tests carried out at different locations and for different sizes of the probing window can be represented by a 3d plot, which enables visualization of locations and sizes of gis in the chromosome. for the determination of gis, window based methods have been used in some earlier studies. the gis of pseudomonas putida kt were determined by analyzing the compositional bias of the mono-, di- and tetra-nucleotide contents in the segment of the genome under the probing window of bp that slides in steps of bp. these authors, however, have used windows with fixed lengths, and there is no objective guideline for how to determine that length in practice. zhang and zhang used a windowless method for displaying the distribution of genomic gc content, and the cumulative gc profile was used by them for the determination of gis. abrupt jump in cumulative gc profile, which is due to relatively different gc content of an island, enabled them to identify the gi. but this was done in a subjective manner and neither clear quantitative measure nor any formal statistical test for assessing the abrupt change in the cumulative gc profile was proposed by these authors. known methods for identifying gis are primarily based on gc contents of the islands, their oligo-nucleotide usage patterns and the codon usage biases in the genes present in the island. when a fixed segment under the probing window is compared with the whole chromosome, which may contain several gis, such a comparison is likely to get influenced by those islands, and this reduces the resolution of the comparison. in order to cope with this problem, we have introduced a refinement phase in our algorithm, where the fixed segment under the probing window is compared with randomly selected segments from the chromosome excluding the parts detected as'putative gi's' in the first phase. this will be discussed in detail in the section on methods. various procedures studied in the literature generally lack a formal and rigorous statistical treatment of the problem of comparing a segment of the chromosome with the rest of the chromosome in order to decide whether the segment is the part of a gi or not. often no formal statistical test is carried out, and the decision to declare a segment as part of an island is done in a subjective way as mentioned earlier. in some other cases, statistical tests have been carried out in a way that is somewhat questionable in the sense that the determination of the critical values and the p-values is not adequately justified due to lack of a rigorous statistical distribution theory of the deviance measures used for such tests. yoon et al. used mahalanobis distance to evaluate the deviation of the codon usage of a gene from the mean of that in the genome. they assumed normal distribution of codon frequencies without much justification for it, and converted the mahalanobis distance into a p-value using the χ distribution function. they have considered a gene as extraneous in codon usage if its p-value was less than. on the other hand, zhang and zhang obtained their results based on codon usage and amino acid usage biases using different cut-offs for the p-values. in some earlier studies, authors used higher order motifs to capture the compositionally deviating regions from the genome. in another study by vernikos et al., authors used variable order motifs and relative entropy for the detection of compositionally deviating regions. in our method, we have used a monte-carlo statistical test, which is partly motivated by the idea of the bootstrap method in statistics for comparing the segment under the probing window with randomly selected segments from the rest of the chromosome. such monte-carlo statistical tests based on randomly selected segments of the chromosome can be supported by simple and precise statistical distribution theory. methods let us denote a whole chromosomal sequence of an organism by s, and s will denote a given segment of s. in order to assess whether s differs significantly from the rest of s, we need a measure of distance that can be used for quantitative comparison between the given segment s and any other segment s' of s not having any overlap with s. such a distance measure, which we may denote as d, can be based on gc contents of s and s' or their oligo-nucleotide distributions. for instance, one may use the absolute distance, the euclidean distance or kullback-leibler divergence computed from oligo nucleotide frequencies. alternatively, for annotated genomes, one may form the distance measure d by comparing the gene contents of s and s' and their codon and amino acid usage biases. merkl et al. used codon usage analysis of two species assuming the similarity of codon usage in phylogenetically related species. weinel et al. analyzed the di-nucleotide usage and the tetra-nucleotide usage in sliding windows and compared them with the di-nucleotide usage of the whole genome and uniform tetra-nucleotide usage respectively. in the study by zhang and zhang, putative gis detected by cumulative gc profile were further analyzed by codon usage and amino acid usage of those regions compared to the whole chromosome s. comparison of the codon usage and oligo-nucleotide usage of the given segment s with those for the whole chromosome s has some drawbacks because s may contain several gis. in some cases, the total size of the gis in s would be much larger than the length of s, and it can be as large as 20% of the size of s. this may statistically contaminate values of various parameters related to gc content as well as oligo-nucleotide and codon usage biases when computed for the entire chromosomal sequence s. this is likely to reduce the resolution of the comparison. in our algorithm, this issue is carefully addressed by introducing a refinement phase, which has been discussed below. in our method, the comparison between s and the rest of s is based on n randomly selected segments s, s, s,.........s n from the chromosome s, each of which has the same length as that of s, and none of them has any overlap with s. we also choose n random pairs of segments,,,......... from s, where for each ≤ i ≤ n, s i and s i are independently selected, and each of them has the same length as the given segment s and no overlap with s. then, we can compute the distances d i = d and d i = d for ≤ i ≤ n and form the following two sets of distance values: d = {d i| ≤ i ≤ n} and d = {d i| ≤ i ≤ n}. if s happens to be a part of a gi with characteristics very different from the rest of s, the values in d are expected to be larger than those in d otherwise, the values in the two sets are expected to be of the same order of magnitudes. statistical test for comparing s with the rest of s in view of the way the distance values in d and d have been obtained by random sampling of segments of s, the values in each of these two sets can be viewed as independent and identically distributed random variables, and the values in d will be completely independent from the values in d the problem of comparing the values in the two sets d and d can be formulated as a statistical testing problem, where the null hypothesis can be taken as h0: "the expected value of an element in d is the same as that of an element in d " and the alternative hypothesis would be ha: "the expected value of an element in d is larger than that of an element in d " we set m1=n−1∑i=1nd i,s12=n−1∑i=1n m2=n−1∑i=1nd i,s22=n−1∑i=1n then, each of m and m is approximately normally distributed being an average of independent and identically distributed random variables by the well-known central limit theorem in probability theory if n is large. further, m and m are independently distributed, and s 2/n and s 2/n will be the standard estimates for their variances respectively. hence, the statistic z=m1−m2{+} will be approximately normally distributed for large n, and the mean of that normal distribution will be zero if h is true, and it will be positive if ha is true. the variance of that asymptotic normal distribution will be one under both hypotheses. consequently, z can be used as a test statistic for testing h against ha in a one-sided test. here, the p-value can be computed using the observed value of z for the given segment s under the probing window and the standard normal distribution. this way of assessing the statistical significance of the evidence for s being part of a gi in the chromosome s using a monte-carlo test based on random samples of segments from s is partly motivated by the idea of the bootstrap. in the present study, we have used n = for larger values of n, the normal approximation will be more accurate for the distribution of the test statistic, but the corresponding computation time will also increase linearly with n, and this might lead to a substantial computational cost when we want to do the analysis for multiple segments with varying sizes located at different positions in the genome. for some smaller chromosomes, we have tried values of n up to but the results did not change significantly. if for some reasons, one is forced to use smaller values of n, the normal approximation for the distribution of z will not be valid. in that case, one may work with a different formulation of the statistical hypotheses as follows. the null hypothesis in that case can be formulated as h0: "the statistical distribution of an element in d is the same as that of an element in d2", and the alternative hypothesis can be formulated as ha: "the distribution of an element in d is stochastically larger than that of an element in d2". with these re-formulated hypotheses, one can carry out the test using two-sample kolmogorov-smirnov statistic or wilcoxon-mann-whitney statistic. these tests, which are computationally more expensive than the test based on normal distribution, have been used by previous authors. however, the power of such non-parametric statistical tests for detecting gis tends to be less than the preceding test based on normal distribution, which is applicable for relatively larger values of n. statistical analysis with segments having variable sizes and locations in order to identify islands at different locations of the chromosome and to determine the stretches of those islands, it is necessary to carry out our statistical analysis using a probing window that slides across the chromosome and also varies in its size. the statistical test described above can be implemented for any location and size of the segment s under that probing window, and the p-value can be computed. it would be useful to plot these p-values so that one can visualize possible locations of the islands in the chromosome as well as their stretches. such a plot of p-values would also enable us to assess visually the statistical significance of the evidence for or against different segments of the chromosomes to be possible parts of gis. for visual presentation of the'putative gis' identified by the analysis described above, a 3d plot for a chromosome can be generated. in this 3d plot, chromosomal locations of the probing window are plotted along the x-axis, corresponding probing window sizes are plotted along the y-axis, and the p-values in gray scale are plotted along the z-axis. here, the p-value for a specific location and size of the window is plotted using a gray scale that changes gradually from black to white, where black corresponds to the extreme p-value = and white corresponds to the other extreme p-value = the white dots corresponding to higher p-values become almost invisible in the white background while dark dots corresponding to low p-values will be prominently visible marking the'putative gis' in the chromosome. for a specified value of p, one can determine all the segments of a chromosome that are associated with a p-value less than or equal to p this will lead to the identification of some'putative gis' having varying sizes and locations in the chromosome that are identifiable with p-values equal to p or smaller. ranges of the'putative gis' in terms of their chromosomal locations can be determined using the cut-off value p and considering a specified number of at least r overlapping windows of variable sizes having p-values smaller than or equal to p further refinement of the'putative gis' identified by the first phase of the algorithm in the first phase of our analysis, the presence of several gis in the genome may statistically contaminate the randomly sampled segments by affecting their oligo-nucleotide distributions. besides,'putative gis' obtained using the first phase of the algorithm, are always of larger size than what they are supposed to be because of the presence of many'false positives'. to reduce the false positives and increase the resolution of our method, a refinement phase with a sliding probing window w of a fixed size over the regions detected as'putative gis' by the first phase of the analysis has been performed. random samples of genomic segments in the refinement phase were chosen from the genome excluding the regions detected as'putative gis' in the first phase. this substantially reduces the influence of various possible islands present in s on any statistical comparison between w and the randomly selected segment, and that in turn increases the resolution of the comparison. the comparison between a probing window w and the rest of s excluding the regions under'putative gis' is again based on n randomly selected segments w, w, w,.........w n each of which has the same length as that of w. the statistical analysis is very similar to that used in the first phase. the p-values are generated using monte-carlo tests carried out at variable locations of the probing window with a fixed size. a smaller probing window is recommended for the refinement phase as it will provide a way of precisely detecting the gis. gene order conservation is rarely observed in distantly related species and several rearrangements and movement of genes occurs frequently. so, some genes, which are not horizontally acquired from other species, may be present within a'putative gi' identified in the first phase, and to some extent, this problem is taken care of by the use of a smaller probing window. however, the use of smaller probing window requires randomly sampled segments from non-contaminated stretches of the genome, and those stretches are available after running the first phase. further, the probing window should not be so small that it can be dominated by a single gene, which would increase the effect of codon biases or amino acid biases related to the level of expression or protein function. smaller probing windows are not recommended in the first phase because it increases the computational cost during the first phase. the use of smaller probing windows that slide over the genome lead to a large number of statistical tests, and this may produce many false positive results. further, there are high chances of substantial overlap of a randomly selected window in the first phase with an island in the genome containing horizontally acquired materials. as in the first phase of the analysis, for a specified value of p, one can again determine all the segments of a'putative gi', which is identified in the first phase, that are associated with a p-value less than or equal to p the entire methodology is presented in the form of a flow chart in fig. 1a, b, and we have named our method as design-island. choice of different parameters associated with the algorithm in the following section, we have presented results obtained using the absolute distance based on tetra-nucleotide frequencies. those results are obtained using p = and r = in first phase and p = in the refinement phase. the value of p in the first phase was relaxed to, and it was chosen in such a way that most of the horizontally acquired stretches of the genome could be captured by the'putative gis' detected in the first phase. after we obtain the'putative islands', we would be able to generate some statistically non-contaminated stretches of the genome. those stretches can be used for random sampling of segments in the refinement phase. in order to determine the value of p in the refinement phase, we have carried out a performance assessment of our method for different values of p based on a dataset related to salmonella typhi ct generated by vernikos et al.. their method of constructing the dataset of putative horizontally transferred genes is discussed briefly in the section on results and discussion. we have calculated the sensitivity, the specificity and the accuracy of our method for different values of p ranging from p = to p =. the slopes of the curve for sn, sp and ac were also plotted for different values of p. as this cut-off p-value increases, the specificity and the accuracy increase, but the sensitivity decreases. we have observed that the specificity and the accuracy increase steadily up to p =, and then the slope of each of the two curves decreases. the sensitivity was observed to decreases with the increase in the cut-off p-value, but in the region from p = to p =, the sensitivity decreases slowly, and then it decreases much more sharply. alternatively, one can determine the value of p using the roc curve approach. when we used that technique with a range of p values from to, it again led to the same value of p as the optimal, and we have chosen the cut-off p-value as p = for the refinement phase. it is possible that for some other bacterial genomes, a different choice of p would be optimal depending on the nucleotide compositions of those genomes. however, some empirical studies using this choice of p for some bacterial genomes other than s. typhi ct demonstrated reasonable performance of our algorithm. we have carried out our analysis with distance measures based on oligo-nucleotides of different orders. the islands detected by methods based on different orders of oligo-nucleotides did not differ considerably. only in some cases either the boundaries of the segments of the'putative gis' slightly differed or a single'putative gi' broke into two or more segments. in most of the organisms, the'putative gis' detected using tetra-nucleotide analysis include those detected by other analysis based on other oligo-nucleotides, and the later analysis sometimes missed some of the important segments of the genomes containing known horizontally acquired materials. as we will see in the section containing a comparative study of different methods, our method outperformed the method w, which is a method based on octa-nucleotides, in many cases. we have considered three types of distance measure computed using oligo-nucleotide frequencies. these are the absolute distance, the euclidean distance and the kullback-leibler divergence. but all these distances lead to almost the same result. the'putative gis' detected by methods based on different distances tend to differ in their boundaries to a small extent. we have finally decided to use the absolute distance, which is computationally the simplest among all the distances considered. before computing the distances, as some authors suggested, one may normalize higher order oligo-nucleotide frequencies by lower order oligo-nucleotide frequencies based on markov type models. one may, in principle, use distances computed using codon usage or amino acid usage biases instead of oligo-nucleotide distributions. however, that will require the use of complete annotation of the entire chromosome and the gene content of each and every randomly selected segment for our monte-carlo test. this makes the implementation of the method computationally challenging, and we have not pursued that here.  we have implemented design-island on the chromosome of salmonella typhi ct obtained from ncbi database. the co-ordinates of statistically significant genomic segments detected by design-island and their gene contents in the chromosomes of s. typhi ct are presented in additional file and detected segments of salmonella typhi ct are discussed below. salmonella typhi ct18 salmonella enterica serovar typhi, an aetiological agent of typhoid fever, is a serious invasive bacterial disease of human. many s. enterica serovars actively invade the mucosal surface of the intestine but are normally contained in healthy individuals by the local immune defence mechanism. however, s. typhi has evolved the ability to spread to the deeper tissues of human including liver, spleen and bone marrow. in s. typhi, thirteen pathogenicity islands and five islands containing bacteriophages related genes have been reported. in s. typhi ct design-island detected ninety seven'putative gis' in the first phase, and after refinement, these islands are broken into two hundreds and twenty-one statistically significant genomic segments that include all of the gis detected in the previous studies. major genes contained in these segments code for phage proteins, putative pathogenicity island proteins, virulence associated secretory protein, vi polysaccharide proteins, integrase, phage integrase, putative bacteriophage proteins, is element transposases, flagellar proteins, uv protection protein, type iii secretion system, type iii restriction-modification system, killing factor kica and b, different chains of nadh dehydrogenase and heat shock proteins. among the newly detected genomic segments, the major genes present are those, which code for putative toxin like proteins, putative virulence proteins, putative phage proteins, integrase, type iii restriction modification system, some pseudo genes, some transporters, flagellar biosynthetic proteins and several accessory proteins, different chains of nadh dehydrogenase and atp synthase, penicillin binding protein, fimbrial subunits, lipopolysaccharide core biosynthesis protein, heat shock and cold shock proteins. two 3d plots generated from the first phase of our algorithm and some representative 1d plots generated from the refinement phase of the algorithm applied to the chromosome of s. typhi ct are shown here in fig. 3a, b. the first plot corresponds to the stretch of the chromosome from the start of the chromosome up to mbp position, and the other plot corresponds to the stretch of the chromosome from mbp position up to the end. representative 1d plots for four of the'putative gis' detected in the first phase and enclosed in gray blocks are shown in the lower panel of the figures. the'putative gi' that stretches from to is fragmented into three segments, namely 11000– bp, 30000– bp and 50000– bp. the'putative gi' that stretches from to bp is fragmented into two segments, namely 1008250– bp and 1059250– bp. the'putative gi' that stretches from to bp is fragmented into three segments, namely 1872500– bp, 1903500– bp and 1911500– bp. in fig. 3b, the 1d plot for the'putative gi' that stretches from to bp is shown in the lower panel. this'putative gi' is fragmented into six segments, namely 4398500– bp, 4402500– bp, 4408500– bp, 4442500– bp, 4511500– bp and 4544500– bp. the third, the fourth and the fifth segments of the above mentioned'putative gi' contain mainly phage genes, some pseudo genes and the vi polysaccharide, which is the major virulence determinant in s. typhi. after running the refinement phase, the genes excluded from the above mentioned'putative gis' are mainly dna polymerase iii, theta subunit, transcriptional activator protein, putative transcriptional regulator, exodeoxyribonuclease x, ribosome modulation factor, possible sulfatase regulatory protein, serine/threonine protein phosphatase putative ion and/or amino acid symporter, aminopeptidase n and some hypothetical and conserved hypothetical proteins. performance comparison with other methods for performance assessment of design-island, a dataset of manually curated putative horizontally transferred genes in s. typhi ct generated by vernikos et al. were used. s. typhi ct is a well-studied prokaryote in terms of its hgt events. vernikos et al. selected s. typhimurium lt as a sister lineage to s. typhi, and the genome of e. coli k was chosen as an outgroup of s. typhi and s. typhimurium. their main idea was that the genes present in all the three genomes form a set of core genes, while the rest of the genes represent either species or strain specific genes, and thus they may be considered as putative htgs. the sensitivity, the specificity and the accuracy of design-island have been compared with those of six other methods available in the literature, namely w, islandpath-gc, islandpath-db, islander, hgt-db and ivom. the results are summarized in fig. accompanied with its data table. the sensitivity of design-island is the highest among the methods considered for comparison, the second in the list being ivom. regarding the accuracy also, the design-island is in the highest position with an accuracy = %, and ivom is in the second position with an accuracy = %. the third method in the list is w with accuracy = %. the specificity of design-island is comparable with that of ivom and w. however, the specificity of design-island is low when compared with that of hgt-db and islander. note that design-island, ivom and w predicted a much larger number of putative horizontally transferred genes compared to the number of such horizontally transferred genes predicted by hgt-db and islander, and this largely explains the behaviour of different methods in terms of their accuracies as pointed out by earlier authors. co-ordinates of the detected segments and the percentages of the genome covered by the'putative islands' identified in the first phase of the algorithm, genomic segments detected after the refinement phase are given in additional file further, in the last column of additional file the genes included in our identified segments along with the percentage of those genes in the entire collection of genes present in the annotated chromosome are presented. the percentages of htgs identified by different methods are reported in additional file ribosomal proteins and many other highly expressed genes tend to deviate compositionally from the genomic background. however, those genes may have limited mobility, and they may not transfer across species. for this reason, ribosomal proteins, other highly expressed genes with biased compositions and the stretches with heavy loads of ribosomal proteins are excluded from the segments obtained in the refinement phase of the algorithm following a similar approach taken by some earlier authors.  the method proposed and discussed in this paper is an unsupervised method in the sense that it does not require any training dataset to begin with. the method uses monte-carlo statistical tests that are implemented using randomly sampled segments, and normal critical values are used for the test statistic. in many of the earlier methods, no statistical test has been performed, and in some cases, where statistical tests were carried out, the determination of the critical values and the p-values were not adequately justified due to lack of rigorous statistical distribution theory. in design-island, such difficulties are effectively overcome by using monte-carlo statistical tests based on randomly selected segments from a chromosome. we have carried out an elaborate comparative analysis involving different bacterial genomes, and it demonstrates that the performance of design-island is often comparable to many other well known methods in terms of their sensitivity, specificity and accuracy. further, in some cases, design-island outperforms many of those competing methods. design-island can detect new segments of bacterial genomes as parts of some gis that might have been missed by earlier methods. for example, in the case of s. typhi ct design-island has predicted some pathogenic or pathogenicity related genes like putative virulence proteins, putative phage proteins, integrase as horizontally acquired materials that were not detected by earlier methods. availability and requirements the computer program for design-island along with a'readme' file can be downloaded from. abbreviations gis: genomic islands; dr: direct repeat; sn: sensitivity; sp: specificity; ac: accuracy; s. typhi: salmonella typhi; spis: salmonella pathogenicity islands authors' contributions rc was responsible for development and implementation of the computational analysis as well as drafting of the manuscript. kc advised on data analysis and manuscript preparation. pc advised on development of the methodology, data analysis, designing of the study and manuscript preparation. all authors read and approved the final manuscript. supplementary material additional file 1 predicted islands and their gene content in salmonella typhi ct the data provided presents genomic segments predicted by design-island and genes present in those islands. click here for file additional file 2 percent of genes detected as htgs in different methods. the data provided presents percentage of genes present in the detected islands using different methods. click here for file acknowledgements the research of raghunath chatterjee was supported by a fellowship from the council of scientific and industrial research, government of india. the research of probal chaudhuri was supported by grants from the council of scientific and industrial research, government of india and the department of biotechnology, government of india. the authors are grateful to george vernikos of sanger institute for several helpful discussions over email and providing their data on salmonella typhi ct and computer programs related to their ivom algorithm. the authors thank two anonymous referees for their careful reading of an earlier version of the paper and suggesting appropriate revision.
this method is applied to salmonella typhi ct genome leading to the discovery of several new pathogenicity, antibiotic resistance and metabolic islands that were missed by earlier methods. many of the available methods for detecting genomic islands in prokaryotic genomes use markers such as transposons, proximal trnas, flanking repeats etc., or they use other supervised techniques requiring training datasets. most of these methods are primarily based on the biases in gc content or codon and amino acid usage of the islands. some'putative gis' are identified in the first phase, and those are refined into smaller segments containing horizontally acquired genes in the refinement phase. such tests are supported by precise statistical distribution theory, and consequently, the resulting p-values are quite reliable for making the decision. however, these methods either do not use any formal statistical test of significance or use statistical tests for which the critical values and the p-values are not adequately justified. we propose a method, which is unsupervised in nature and uses monte-carlo statistical tests based on randomly selected segments of a chromosome. the proposed method is based on statistical tests supported by precise distribution theory and reliable p-values along with a technique for visualizing statistically significant islands.
 many of the available methods for detecting genomic islands in prokaryotic genomes use markers such as transposons, proximal trnas, flanking repeats etc., or they use other supervised techniques requiring training datasets. most of these methods are primarily based on the biases in gc content or codon and amino acid usage of the islands. however, these methods either do not use any formal statistical test of significance or use statistical tests for which the critical values and the p-values are not adequately justified. we propose a method, which is unsupervised in nature and uses monte-carlo statistical tests based on randomly selected segments of a chromosome. such tests are supported by precise statistical distribution theory, and consequently, the resulting p-values are quite reliable for making the decision.  our algorithm runs in two phases. some'putative gis' are identified in the first phase, and those are refined into smaller segments containing horizontally acquired genes in the refinement phase. this method is applied to salmonella typhi ct genome leading to the discovery of several new pathogenicity, antibiotic resistance and metabolic islands that were missed by earlier methods. many of these islands contain mobile genetic elements like phage-mediated genes, transposons, integrase and is elements confirming their horizontal acquirement.  the proposed method is based on statistical tests supported by precise distribution theory and reliable p-values along with a technique for visualizing statistically significant islands. the performance of our method is better than many other well known methods in terms of their sensitivity and accuracy, and in terms of specificity, it is comparable to other methods. 