BACKGROUND
bacteria are the most abundant domain of life that exists on earth   <cit> .
the species we see today are highly diverse, reflecting adaptations to a wide range of environments over billions of years.
one of the major sources of adaptability for bacteria is the ability to obtain genes horizontally from other sources, including other prokaryotes, viruses, and even eukaryotes  <cit> .
analysis of bacterial genomic sequences has indicated that many of the horizontal gene transfer  events observed in bacteria involve clusters of genes.
collectively, these genomic regions are referred to as genomic islands   <cit> .
gis, which range in size from ~5– <dig> kb, have become of significant interest, since they are frequently observed to encode genes involved in particular adaptive functions of medical and environmental importance  <cit> .
the concept of gis was derived from the term pathogenicity island, which was initially coined by hacker and colleagues to describe a genomic region of uropathogenic escherichia coli that harbours clusters of virulence factors that can be spontaneously deleted  <cit> .
these regions also exhibit other sequence and annotation features that can be used to distinguish them from the rest of the genomes, as described below  <cit> .
subsequently, the term gi was adapted to describe genomic regions that contain similar features as pais but encode gene products of other functions.
reflecting the wide variety of genes found in gis, function-specific terms such as "antibiotic resistance islands" , "fitness islands" and "metabolic islands"  have been invented to describe different types of gis  <cit> .
previous characterization of gis has identified many sequence and annotation features that are frequently associated with gis, such as differing sequence composition , flanking direct repeats, and the presence of mobility and trna genes in the region  <cit> .
computational tools have therefore been developed to aid the identification of islands in genomic sequences that are based on sequence composition analysis  <cit> .
these tools rely on the observation that different organisms exhibit different nucleotide pattern preferences that constitute their genome signatures.
more closely related organisms are assumed to share similar preferences and, therefore, have more similar signatures.
as a result, for a gene-cluster whose signature deviates from the genome signature, a plausible explanation is that this gene cluster has a foreign origin and its signature reflects that of the original donor.
the tools, therefore, in general calculate the frequencies of oligo-nucleotides  for a sub-region of a genome and compare these results with the expected frequencies from that genome.
one advantage of this approach is that gi prediction can be made from a single genome sequence.
however, gi predictors based on sequence composition may lead to false positive gi predictions due to other factors causing a bias in sequence composition, such as high gene expression level  <cit> .
furthermore, these approaches may miss the identification of gis that have been acquired from genomes with similar sequence composition or more ancient gi acquisition events that may have ameliorated to the host genome sequence composition over time  <cit> .
an alternative approach that is independent from sequence composition-based approaches is to use comparative genomics to identify genomic regions that have a clear phyletic pattern of non-vertical inheritance.
in these methods, putative gis are often defined as clusters of genes in one genome that are not present in a related genome.
they are based on the observation that gis are sporadically distributed among closely related species or strains and can sometimes be found between very distantly related species as judged by the degrees of sequence divergence in 16s rrnas or other orthologs  <cit> .
until recently, this approach could only be performed manually for a few species that had enough similar sequenced genomes  <cit> .
however, recent research has started to utilize the increasing number of completely sequenced genomes by constructing tools that can perform large-scale genomic comparisons, such as mobilomefinder  <cit>  and mosaic  <cit> .
mobilomefinder uses whole genome alignments to identify gis, but is similar to islander  <cit> , such that it is limited to identifying only islands that have inserted in disrupted trnas.
although mosaic identifies strain specific regions that have not necessarily inserted into a trna, it can mistakenly identify inversions and translocations between genomes as strain-specific regions.
in addition to these limitations, all current comparative genomics based gi prediction tools require the manual selection of both the query and the comparative genomes as input, which may result in inconsistent selection criteria due to the unfamiliarity of different phylogenetic distances within genera.
we now report here the development of "islandpick", the first completely automated comparative genomics approach to identify gis.
starting with all sequenced bacterial genomes as input, we use stringent but potentially flexible criteria, with distance cutoffs, to select query genomes that have a sufficient number of suitably related species or strains to conduct an analysis of gis.
we used this islandpick method to identify datasets of gis from several genomes as well as a dataset of conserved backbone genomic regions that are probable non-gis.
we evaluated how well these datasets agreed with gis reported in the literature.
we also evaluated how well these datasets agreed with those predicted using previously published sequence composition-based gi tools since our comparative genomics based method is independent of sequence composition-based methods.
analyses of gi/hgt prediction tools have been previously published, but have used either artificial datasets or real data from only a few species  <cit> .
our islandpick method reported here focuses on developing robust positive and negative datasets that can be used as an independent non-artificial benchmark for previous and future gi prediction tools.
moreover, as additional genome sequences become available, islandpick can be applied to those genomes to expand the benchmark dataset in a consistent and automated fashion.
RESULTS
genomic island predictions
in order to evaluate the sensitivity/recall of previously developed gi predictors based on sequence composition bias, we constructed a dataset of putative gis based on a high-throughput comparative genomics approach that we developed.
gis were identified as regions that were present only in the genome being queried when compared to multiple genomes from closely-related species or strains .
of the  <dig> completely sequenced microbial genomes,  <dig> chromosomes were initially used as queries in our pipeline .
<dig> of these did not have at least  <dig> related species/strains while many others did not meet our stringent criteria to do a comparative analysis.
however, as more genome sequences become available, the number of genomes matching our criteria is expected to improve.
we found that  <dig> chromosomes met our requirements for the prediction of gis and conserved backbone sequences.
a subset of  <dig> chromosomes contained gis while our method did not detect gis using our method in the other  <dig> chromosomes .
many of these  <dig> genomes may contain gis that are smaller than  <dig> kb or have other cases of hgt that were not being targeted by our approach.
the dataset was further reduced to  <dig> chromosomes, because a negative dataset could not be predicted for  <dig> chromosomes and the gi prediction tool sigi-hmm gave errors on another  <dig> chromosomes .
in total, we identified  <dig> gis, comprising  <dig>  mb and ranging in size from 8– <dig> kb, within  <dig> chromosomes from  <dig> different strains and  <dig> genera .
these putative gis contained a total of  <dig>  annotated genes with an average of  <dig>  genes/gi and  <dig>  genes/strain .
negative dataset
in order to evaluate the specificity/precision of previously developed gi predictors we constructed a dataset of genomic regions that were not likely to contain gis.
we adapted our gi prediction pipeline to identify large genomic regions that were conserved in several genomes ).
these conserved genomic regions were identified for the same  <dig> query genomes that we used for prediction of gis.
we could not identify any conserved regions larger than  <dig> base pairs for  <dig> of these chromosomes, using our conservative criteria, and so these were removed from both the positive and negative datasets.
the resulting negative dataset was about  <dig> times larger than our dataset of gis, containing approximately  <dig>  mb over  <dig> separate genomic regions .
the size difference between the negative and positive datasets was expected since the proportion of hgt versus conserved backbone in a genome is normally much smaller  <cit> .
comparison with previous literature
although, there is no gold standard dataset of gis, we wanted to examine how previously published gis overlapped with our datasets.
we identified  <dig> strains from our list of  <dig> that had published gis  <cit> .
as with the analysis of the sequence composition based gi predictors , we calculated the overlap of the published gis against our positive and negative dataset.
we found, potentially due in part to the similar manual comparative genomics methods sometimes used to identify gis in the literature dataset, that the literature gis had the most agreement with our datasets .
literature gis had the highest precision, recall, and overall accuracy of  <dig>  87%, and 96%, respectively, when using islandpick-predicted islands as the text dataset .
*results are averaged from  <dig> chromosomes in  <dig> different strains  except for the "literature" gis, which were averaged over  <dig> strains; escherichia coli o157:h <dig>  e. coli o157:h <dig> edl <dig>  salmonella enterica typhi str.
ct <dig>  s. enterica typhimurium lt <dig>  and streptococcus pyogenes mgas <dig>  <cit> .
comparison to sequence composition based approaches
the gis and the non-gis identified from our comparative genomics approach were used as positive and negative datasets, respectively, to evaluate the accuracy of several previously published sequence based gi prediction tools  <cit> .
the tools were run using their default parameters on the same  <dig> chromosomes and any overlapping regions with the negative dataset were considered false positives while overlapping regions with the positive dataset were considered true positives .
the following accuracy calculations were measured using the number of overlapping nucleotides ; although results were not significantly different when counting only gis with greater than 50% overlap .
we found that the precision and recall for the tools evaluated varied considerably .
sigi-hmm performed the best with 92% precision  whereas alienhunter had the best recall at 77% .
sigi-hmm and the islandpath/dimob tool had comparable overall highest accuracy of 86% with islandpath-dimob more suitable for analyses requiring a slightly higher recall .
all of the tools had similar overall accuracies ranging from 82–86%  except for alienhunter, which had an accuracy of only 71%.
this appeared to be primarily due to the large number of predictions being made by alienhunter  versus the other methods .
for completeness, we also calculated the accuracy of each tool using every other tool as the benchmark .
the average accuracy measurements over all benchmarks for each tool were very similar to those calculated using only our datasets indicating that the datasets generated using our comparative genomic approach may be an appropriate reference dataset for future use.
these positive and negative gi datasets, and the source code for development of these datasets, are available at .
comparison of sequence composition based approaches using additional gi datasets constructed with more relaxed criteria
islandpick defaults can be modified to allow the prediction of gis with more ancient origins, and so we created two additional datasets based on the selection of more divergent genomes for use in gi and non-gi prediction .
the first "relaxed" dataset had approximately 46% more gis predicted per genome, while as expected the negative datasets stayed about the same size with a 3% increase in the relaxed dataset.
notably, accuracy relative to the literature dataset went down slightly , indicating that our islandpick defaults do most accurately reflect literature-based gi data.
the sequence composition-based tools also all had a relative decrease in accuracy using this more relaxed dataset: accuracy decreased between  <dig>  and  <dig> % for all methods, with the exception of alien hunter  which showed the smallest decrease of  <dig> % .
using a second more relaxed dataset of parameters resulted in yet another decrease in predicted accuracy of the gi tools and the accuracy relative to the literature-based dataset also decreased further .
while the use of more relaxed criteria for gi prediction may still have its uses, our results indicate that the default settings of our islandpick method are most appropriate for predicting islands that most closely resemble what is reported in the literature.
also, the sequence composition-based methods appear to perform best when using the default islandpick-predicted gi datasets for evaluation.
discussion
we have introduced and outlined, islandpick, a novel automated method for predicting gis using comparative genomics.
we have used islandpick, with its stringent default criteria, to generate test datasets of gis and non-gi regions that are used to evaluate the accuracy of multiple sequence composition based gi predictors.
this represents the first evaluation of gi predictors based on real  gi data from several different strains of bacteria  <cit> .
for organisms that have suitable sequenced genomes for comparison, we identified very probable gis and genomic regions that were very probable non-gis.
by developing separate negative and positive datasets that were independent of sequence composition based approaches we were able to assess the accuracy of several gi predictors.
according to our analysis, sigi-hmm has the highest precision and shares comparable overall accuracy with islandpath/dimob which has higher recall at the expense of precision.
sigi-hmm is the only tool tested that measures codon usage and notably it also identifies codon usage associated with highly expressed genes and then discards such genes from the analysis.
while more study is needed, this suggests that regions displaying codon usage bias of a pattern that is not associated with highly expressed genes are more likely to be gis.
consistent with this, the islandpath/dimob method that requires both a dinucleotide bias and the presence of a mobility gene for a gi prediction does much better than the islandpath/dinuc method which measures only dinucleotide bias.
the latter can result in false positives from highly expressed genes but higher predictive recall/sensitivity.
alienhunter had the lowest precision ; however, it had by far the highest recall value  with more than twice as many predictions as any other tool.
based on these results we suggest the use of sigi-hmm for making very precise predictions where a high confidence dataset of gis is preferred while alienhunter can be used as a first-pass tool to capture most gis for further refinement.
if suitable comparative genomes are available, islandpick would be a top choice for gi prediction, however it should be emphasized that islandpick is at this time really designed for generating robust island datasets for evaluating gi predictors, rather than being a gi predictor itself.
its utility as a gi predictor could increase though as more genome sequences, suitable for a comparative genomics approach, are made available.
if comparative genomes are not available, the results generally suggest that by combining multiple features of gis, as in the islandpath/dimob dataset, and accounting for highly expressed genes, which sigi-hmm does and islandpath/dimob does indirectly, a better overall predictor could be created.
more analysis of the differences in sequence composition between true positives and false positives in this analysis could be insightful.
our results show that all gi predictors had a decrease in overall accuracy when trying to predict more ancient islands.
considering that sequence composition based predictors would have trouble detecting significant signals in older gis due to amelioration to the host genome, it was not surprising that the overall accuracy for all tools decreased  <cit> .
alien hunter had the lowest decrease in overall accuracy however it still maintained the lowest precision and overall accuracy for the prediction of this dataset and sigi-hmm still out performed the other sequence composition-based tools for predicting these more divergent islands.
it is possible that the accuracy of some of these sequence composition-based tools could be improved by optimizing their parameters.
however, out of all the tools, sigi-hmm and centroid were the only ones with a clearly defined sensitivity/statistical parameter and even for these there were no recommend suggestions besides the default.
although default parameters for all tools are presumably maximized to result in the best overall accuracy, some fine tuning may improve their results.
of course there are clear limitations to predicting gis using comparative genomics in order to produce the gi dataset used in our evaluation.
the choice of reference genomes for comparison to each query genome can result in differences in the positive and negative datasets.
in our genome selection we use several distance cutoffs to minimize this bias as much as possible .
gis could be present in the negative dataset if a gi was inserted before the divergence of all genomes being examined.
to minimize these in our datasets we require that at least  <dig> reference genomes be used for each query genome and that at least one reference genome is at least some minimal distance away from the query genome.
similarly, we minimize the number of false positives in our positive dataset by requiring that the putative gi is present only in the query genome compared to all reference genomes.
therefore, a deletion of the same genomic region would need to occur independently in  <dig> or more strains for it to be mis-predicted as a gi in our analysis.
similarly, a gi that inserted into multiple genomes would have to be conserved in all of the diverse genomes studied to be improperly placed in the negative dataset.
although using several rules in our genome selection process results in very stringent datasets of gi and non-gi regions, it does limit the number of organisms that can be used by islandpick.
relaxing the genome selection process by the removal of some of these cut-offs would allow our approach to be applicable to more genomes.
for example, by requiring only  <dig> genomes within a certain maximum distance we would increase the number of chromosomes usable by islandpick from  <dig> to  <dig>  based on the currently available genome sequences.
it should be emphasized that islandpick was not developed to be a gi prediction tool that would replace sequence-based composition tools, which can be used on any genome without the requirement of having several other comparative genomes; rather, our islandpick approach allows the testing of these tools and in certain cases can also be used for gi prediction .
the absence of large islands  in our positive dataset is probably due to the fact that only a few similar genes between genome regions would cause our method to split a large island into two smaller ones.
considering that as an island gets bigger there is a greater chance of detecting some similarity between the genomic regions being compared, we would expect that very large gis may be split into smaller ones.
as indicated in recent research, this limitation could be improved in the future by spanning together islands that are interrupted by only small regions of low similarity  <cit> .
it must also be appreciated that the gi regions identified represent a set of gis that were acquired within a particular window of divergence of the strains being examined.
any genomic regions that did not have clear evidence of gi or non-gi status were not included in either of the datasets so that tools that predicted such possible/uncertain gis were not penalized.
this would include gis that have inserted into multiple strains or those that have partial similarity with other genomic regions.
rather, our methodology penalizes tools that falsely predict gis in highly conserved backbone regions that very likely do not contain true gis, and also the method penalizes tools that don't predict a subset of gis that are very likely true positives.
in fact, our approach produced the smallest dataset of gis compared to all of the methods we used in this study  and the proportion of the genomes that are covered in both of our positive and negative datasets combined, ranges from 10%–30% per genome.
therefore, we do not make predictions for the majority  of the genome, reflecting the high accuracy of our positive and negative datasets using our cutoffs.
also, our comparative genomics-based gi datasets had the highest agreement with the smaller curated, literature-based dataset.
as an example of the islandpick approach, when salmonella enterica typhi ct <dig> is used as a query genome to identify islands using our default cutoffs, very closely related genomes including s. enterica typhi ty <dig> and s. enterica paratyphi a str.
atcc  <dig> were excluded from comparison.
therefore, we identify gis that have inserted after the divergence of s. enterica typhi ct <dig> and the next most related genome that has been sequenced, which is s. typhimurium lt <dig>  islands that inserted before the divergence of ct <dig> and lt <dig> would also not be included in our positive dataset, using these stringent cutoffs.
however, we require that at least one genome be a certain distance from the query genome , so that these more ancient gis are not improperly included in the negative dataset.
we assume that any sequences shared between the query genome  and the comparative genomes including those that meet the single distant genome cutoff  are sufficiently stable and can be considered as the conserved genome backbone.
again, distance cutoffs can be modified in islandpick to detect more ancient islands or those acquired more recently.
similar to other gi prediction tools we do not try to identify the origins or the methods of horizontal transfer for these gis.
indeed future research on many of these large regions of hgt will likely allow them to be sub-classified into known mobile elements such as conjugate transposons, integrated plasmids, integrons, and prophage; and will depend on robust prediction tools and knowledge of their strengths and weaknesses.
also, new sequence composition based gi prediction tools will likely combine components from previous methods to maximize both precision and recall  <cit> .
comparative genomics studies like this one, will aid in these areas by providing an independent method for gi prediction.
as more genomes are sequenced, the distance cutoffs used in this method should be re-evaluated, but this overall approach should only increase in utility as the number of completely sequenced microbial genomes increases into the thousands.
this analysis of the accuracy of composition-based gi predictors should aid both development and use of such predictors, which are becoming of increasing importance as the critical role of gis in microbial evolution becomes more apparent.
CONCLUSIONS
we have demonstrated, through the comparison of our islandpick method with a reference literature dataset of gis, that the prediction of gis can be performed using a fully automated comparative genomics approach.
we produce reference gi datasets  using islandpick that allow an independent analysis of the accuracy of several previously published sequence composition-based gi prediction tools.
our analyses of the accuracy of gi predictors should aid researchers in formulating an appropriate approach to identify gis, based on whether they prefer high recall/sensitivity or precision/specificity.
such gi predictors are likely to become of increasing importance in bacterial genome analysis, as appreciation grows of their significant role in adaptations of medical and environmental importance.

 bacteria are the most abundant domain of life that exists on earth. the species we see today are highly diverse, reflecting adaptations to a wide range of environments over billions of years. one of the major sources of adaptability for bacteria is the ability to obtain genes horizontally from other sources, including other prokaryotes, viruses, and even eukaryotes. analysis of bacterial genomic sequences has indicated that many of the horizontal gene transfer events observed in bacteria involve clusters of genes. collectively, these genomic regions are referred to as genomic islands. gis, which range in size from ~5– kb, have become of significant interest, since they are frequently observed to encode genes involved in particular adaptive functions of medical and environmental importance. the concept of gis was derived from the term pathogenicity island, which was initially coined by hacker and colleagues to describe a genomic region of uropathogenic escherichia coli that harbours clusters of virulence factors that can be spontaneously deleted. these regions also exhibit other sequence and annotation features that can be used to distinguish them from the rest of the genomes, as described below. subsequently, the term gi was adapted to describe genomic regions that contain similar features as pais but encode gene products of other functions. reflecting the wide variety of genes found in gis, function-specific terms such as "antibiotic resistance islands", "fitness islands" and "metabolic islands" have been invented to describe different types of gis. previous characterization of gis has identified many sequence and annotation features that are frequently associated with gis, such as differing sequence composition, flanking direct repeats, and the presence of mobility and trna genes in the region. computational tools have therefore been developed to aid the identification of islands in genomic sequences that are based on sequence composition analysis. these tools rely on the observation that different organisms exhibit different nucleotide pattern preferences that constitute their genome signatures. more closely related organisms are assumed to share similar preferences and, therefore, have more similar signatures. as a result, for a gene-cluster whose signature deviates from the genome signature, a plausible explanation is that this gene cluster has a foreign origin and its signature reflects that of the original donor. the tools, therefore, in general calculate the frequencies of oligo-nucleotides for a sub-region of a genome and compare these results with the expected frequencies from that genome. one advantage of this approach is that gi prediction can be made from a single genome sequence. however, gi predictors based on sequence composition may lead to false positive gi predictions due to other factors causing a bias in sequence composition, such as high gene expression level. furthermore, these approaches may miss the identification of gis that have been acquired from genomes with similar sequence composition or more ancient gi acquisition events that may have ameliorated to the host genome sequence composition over time. an alternative approach that is independent from sequence composition-based approaches is to use comparative genomics to identify genomic regions that have a clear phyletic pattern of non-vertical inheritance. in these methods, putative gis are often defined as clusters of genes in one genome that are not present in a related genome. they are based on the observation that gis are sporadically distributed among closely related species or strains and can sometimes be found between very distantly related species as judged by the degrees of sequence divergence in 16s rrnas or other orthologs. until recently, this approach could only be performed manually for a few species that had enough similar sequenced genomes. however, recent research has started to utilize the increasing number of completely sequenced genomes by constructing tools that can perform large-scale genomic comparisons, such as mobilomefinder and mosaic. mobilomefinder uses whole genome alignments to identify gis, but is similar to islander, such that it is limited to identifying only islands that have inserted in disrupted trnas. although mosaic identifies strain specific regions that have not necessarily inserted into a trna, it can mistakenly identify inversions and translocations between genomes as strain-specific regions. in addition to these limitations, all current comparative genomics based gi prediction tools require the manual selection of both the query and the comparative genomes as input, which may result in inconsistent selection criteria due to the unfamiliarity of different phylogenetic distances within genera. we now report here the development of "islandpick", the first completely automated comparative genomics approach to identify gis. starting with all sequenced bacterial genomes as input, we use stringent but potentially flexible criteria, with distance cutoffs, to select query genomes that have a sufficient number of suitably related species or strains to conduct an analysis of gis. we used this islandpick method to identify datasets of gis from several genomes as well as a dataset of conserved backbone genomic regions that are probable non-gis. we evaluated how well these datasets agreed with gis reported in the literature. we also evaluated how well these datasets agreed with those predicted using previously published sequence composition-based gi tools since our comparative genomics based method is independent of sequence composition-based methods. analyses of gi/hgt prediction tools have been previously published, but have used either artificial datasets or real data from only a few species. our islandpick method reported here focuses on developing robust positive and negative datasets that can be used as an independent non-artificial benchmark for previous and future gi prediction tools. moreover, as additional genome sequences become available, islandpick can be applied to those genomes to expand the benchmark dataset in a consistent and automated fashion.  genomic island predictions in order to evaluate the sensitivity/recall of previously developed gi predictors based on sequence composition bias, we constructed a dataset of putative gis based on a high-throughput comparative genomics approach that we developed. gis were identified as regions that were present only in the genome being queried when compared to multiple genomes from closely-related species or strains. of the completely sequenced microbial genomes, chromosomes were initially used as queries in our pipeline. of these did not have at least related species/strains while many others did not meet our stringent criteria to do a comparative analysis. however, as more genome sequences become available, the number of genomes matching our criteria is expected to improve. we found that chromosomes met our requirements for the prediction of gis and conserved backbone sequences. a subset of chromosomes contained gis while our method did not detect gis using our method in the other chromosomes. many of these genomes may contain gis that are smaller than kb or have other cases of hgt that were not being targeted by our approach. the dataset was further reduced to chromosomes, because a negative dataset could not be predicted for chromosomes and the gi prediction tool sigi-hmm gave errors on another chromosomes. in total, we identified gis, comprising mb and ranging in size from 8– kb, within chromosomes from different strains and genera. these putative gis contained a total of annotated genes with an average of genes/gi and genes/strain. negative dataset in order to evaluate the specificity/precision of previously developed gi predictors we constructed a dataset of genomic regions that were not likely to contain gis. we adapted our gi prediction pipeline to identify large genomic regions that were conserved in several genomes ). these conserved genomic regions were identified for the same query genomes that we used for prediction of gis. we could not identify any conserved regions larger than base pairs for of these chromosomes, using our conservative criteria, and so these were removed from both the positive and negative datasets. the resulting negative dataset was about times larger than our dataset of gis, containing approximately mb over separate genomic regions. the size difference between the negative and positive datasets was expected since the proportion of hgt versus conserved backbone in a genome is normally much smaller. comparison with previous literature although, there is no gold standard dataset of gis, we wanted to examine how previously published gis overlapped with our datasets. we identified strains from our list of that had published gis. as with the analysis of the sequence composition based gi predictors, we calculated the overlap of the published gis against our positive and negative dataset. we found, potentially due in part to the similar manual comparative genomics methods sometimes used to identify gis in the literature dataset, that the literature gis had the most agreement with our datasets. literature gis had the highest precision, recall, and overall accuracy of 87%, and 96%, respectively, when using islandpick-predicted islands as the text dataset. *results are averaged from chromosomes in different strains except for the "literature" gis, which were averaged over strains; escherichia coli o157:h e. coli o157:h edl salmonella enterica typhi str. ct s. enterica typhimurium lt and streptococcus pyogenes mgas. comparison to sequence composition based approaches the gis and the non-gis identified from our comparative genomics approach were used as positive and negative datasets, respectively, to evaluate the accuracy of several previously published sequence based gi prediction tools. the tools were run using their default parameters on the same chromosomes and any overlapping regions with the negative dataset were considered false positives while overlapping regions with the positive dataset were considered true positives. the following accuracy calculations were measured using the number of overlapping nucleotides; although results were not significantly different when counting only gis with greater than 50% overlap. we found that the precision and recall for the tools evaluated varied considerably. sigi-hmm performed the best with 92% precision whereas alienhunter had the best recall at 77%. sigi-hmm and the islandpath/dimob tool had comparable overall highest accuracy of 86% with islandpath-dimob more suitable for analyses requiring a slightly higher recall. all of the tools had similar overall accuracies ranging from 82–86% except for alienhunter, which had an accuracy of only 71%. this appeared to be primarily due to the large number of predictions being made by alienhunter versus the other methods. for completeness, we also calculated the accuracy of each tool using every other tool as the benchmark. the average accuracy measurements over all benchmarks for each tool were very similar to those calculated using only our datasets indicating that the datasets generated using our comparative genomic approach may be an appropriate reference dataset for future use. these positive and negative gi datasets, and the source code for development of these datasets, are available at. comparison of sequence composition based approaches using additional gi datasets constructed with more relaxed criteria islandpick defaults can be modified to allow the prediction of gis with more ancient origins, and so we created two additional datasets based on the selection of more divergent genomes for use in gi and non-gi prediction. the first "relaxed" dataset had approximately 46% more gis predicted per genome, while as expected the negative datasets stayed about the same size with a 3% increase in the relaxed dataset. notably, accuracy relative to the literature dataset went down slightly, indicating that our islandpick defaults do most accurately reflect literature-based gi data. the sequence composition-based tools also all had a relative decrease in accuracy using this more relaxed dataset: accuracy decreased between and % for all methods, with the exception of alien hunter which showed the smallest decrease of %. using a second more relaxed dataset of parameters resulted in yet another decrease in predicted accuracy of the gi tools and the accuracy relative to the literature-based dataset also decreased further. while the use of more relaxed criteria for gi prediction may still have its uses, our results indicate that the default settings of our islandpick method are most appropriate for predicting islands that most closely resemble what is reported in the literature. also, the sequence composition-based methods appear to perform best when using the default islandpick-predicted gi datasets for evaluation. discussion we have introduced and outlined, islandpick, a novel automated method for predicting gis using comparative genomics. we have used islandpick, with its stringent default criteria, to generate test datasets of gis and non-gi regions that are used to evaluate the accuracy of multiple sequence composition based gi predictors. this represents the first evaluation of gi predictors based on real gi data from several different strains of bacteria. for organisms that have suitable sequenced genomes for comparison, we identified very probable gis and genomic regions that were very probable non-gis. by developing separate negative and positive datasets that were independent of sequence composition based approaches we were able to assess the accuracy of several gi predictors. according to our analysis, sigi-hmm has the highest precision and shares comparable overall accuracy with islandpath/dimob which has higher recall at the expense of precision. sigi-hmm is the only tool tested that measures codon usage and notably it also identifies codon usage associated with highly expressed genes and then discards such genes from the analysis. while more study is needed, this suggests that regions displaying codon usage bias of a pattern that is not associated with highly expressed genes are more likely to be gis. consistent with this, the islandpath/dimob method that requires both a dinucleotide bias and the presence of a mobility gene for a gi prediction does much better than the islandpath/dinuc method which measures only dinucleotide bias. the latter can result in false positives from highly expressed genes but higher predictive recall/sensitivity. alienhunter had the lowest precision; however, it had by far the highest recall value with more than twice as many predictions as any other tool. based on these results we suggest the use of sigi-hmm for making very precise predictions where a high confidence dataset of gis is preferred while alienhunter can be used as a first-pass tool to capture most gis for further refinement. if suitable comparative genomes are available, islandpick would be a top choice for gi prediction, however it should be emphasized that islandpick is at this time really designed for generating robust island datasets for evaluating gi predictors, rather than being a gi predictor itself. its utility as a gi predictor could increase though as more genome sequences, suitable for a comparative genomics approach, are made available. if comparative genomes are not available, the results generally suggest that by combining multiple features of gis, as in the islandpath/dimob dataset, and accounting for highly expressed genes, which sigi-hmm does and islandpath/dimob does indirectly, a better overall predictor could be created. more analysis of the differences in sequence composition between true positives and false positives in this analysis could be insightful. our results show that all gi predictors had a decrease in overall accuracy when trying to predict more ancient islands. considering that sequence composition based predictors would have trouble detecting significant signals in older gis due to amelioration to the host genome, it was not surprising that the overall accuracy for all tools decreased. alien hunter had the lowest decrease in overall accuracy however it still maintained the lowest precision and overall accuracy for the prediction of this dataset and sigi-hmm still out performed the other sequence composition-based tools for predicting these more divergent islands. it is possible that the accuracy of some of these sequence composition-based tools could be improved by optimizing their parameters. however, out of all the tools, sigi-hmm and centroid were the only ones with a clearly defined sensitivity/statistical parameter and even for these there were no recommend suggestions besides the default. although default parameters for all tools are presumably maximized to result in the best overall accuracy, some fine tuning may improve their results. of course there are clear limitations to predicting gis using comparative genomics in order to produce the gi dataset used in our evaluation. the choice of reference genomes for comparison to each query genome can result in differences in the positive and negative datasets. in our genome selection we use several distance cutoffs to minimize this bias as much as possible. gis could be present in the negative dataset if a gi was inserted before the divergence of all genomes being examined. to minimize these in our datasets we require that at least reference genomes be used for each query genome and that at least one reference genome is at least some minimal distance away from the query genome. similarly, we minimize the number of false positives in our positive dataset by requiring that the putative gi is present only in the query genome compared to all reference genomes. therefore, a deletion of the same genomic region would need to occur independently in or more strains for it to be mis-predicted as a gi in our analysis. similarly, a gi that inserted into multiple genomes would have to be conserved in all of the diverse genomes studied to be improperly placed in the negative dataset. although using several rules in our genome selection process results in very stringent datasets of gi and non-gi regions, it does limit the number of organisms that can be used by islandpick. relaxing the genome selection process by the removal of some of these cut-offs would allow our approach to be applicable to more genomes. for example, by requiring only genomes within a certain maximum distance we would increase the number of chromosomes usable by islandpick from to based on the currently available genome sequences. it should be emphasized that islandpick was not developed to be a gi prediction tool that would replace sequence-based composition tools, which can be used on any genome without the requirement of having several other comparative genomes; rather, our islandpick approach allows the testing of these tools and in certain cases can also be used for gi prediction. the absence of large islands in our positive dataset is probably due to the fact that only a few similar genes between genome regions would cause our method to split a large island into two smaller ones. considering that as an island gets bigger there is a greater chance of detecting some similarity between the genomic regions being compared, we would expect that very large gis may be split into smaller ones. as indicated in recent research, this limitation could be improved in the future by spanning together islands that are interrupted by only small regions of low similarity. it must also be appreciated that the gi regions identified represent a set of gis that were acquired within a particular window of divergence of the strains being examined. any genomic regions that did not have clear evidence of gi or non-gi status were not included in either of the datasets so that tools that predicted such possible/uncertain gis were not penalized. this would include gis that have inserted into multiple strains or those that have partial similarity with other genomic regions. rather, our methodology penalizes tools that falsely predict gis in highly conserved backbone regions that very likely do not contain true gis, and also the method penalizes tools that don't predict a subset of gis that are very likely true positives. in fact, our approach produced the smallest dataset of gis compared to all of the methods we used in this study and the proportion of the genomes that are covered in both of our positive and negative datasets combined, ranges from 10%–30% per genome. therefore, we do not make predictions for the majority of the genome, reflecting the high accuracy of our positive and negative datasets using our cutoffs. also, our comparative genomics-based gi datasets had the highest agreement with the smaller curated, literature-based dataset. as an example of the islandpick approach, when salmonella enterica typhi ct is used as a query genome to identify islands using our default cutoffs, very closely related genomes including s. enterica typhi ty and s. enterica paratyphi a str. atcc were excluded from comparison. therefore, we identify gis that have inserted after the divergence of s. enterica typhi ct and the next most related genome that has been sequenced, which is s. typhimurium lt islands that inserted before the divergence of ct and lt would also not be included in our positive dataset, using these stringent cutoffs. however, we require that at least one genome be a certain distance from the query genome, so that these more ancient gis are not improperly included in the negative dataset. we assume that any sequences shared between the query genome and the comparative genomes including those that meet the single distant genome cutoff are sufficiently stable and can be considered as the conserved genome backbone. again, distance cutoffs can be modified in islandpick to detect more ancient islands or those acquired more recently. similar to other gi prediction tools we do not try to identify the origins or the methods of horizontal transfer for these gis. indeed future research on many of these large regions of hgt will likely allow them to be sub-classified into known mobile elements such as conjugate transposons, integrated plasmids, integrons, and prophage; and will depend on robust prediction tools and knowledge of their strengths and weaknesses. also, new sequence composition based gi prediction tools will likely combine components from previous methods to maximize both precision and recall. comparative genomics studies like this one, will aid in these areas by providing an independent method for gi prediction. as more genomes are sequenced, the distance cutoffs used in this method should be re-evaluated, but this overall approach should only increase in utility as the number of completely sequenced microbial genomes increases into the thousands. this analysis of the accuracy of composition-based gi predictors should aid both development and use of such predictors, which are becoming of increasing importance as the critical role of gis in microbial evolution becomes more apparent.  we have demonstrated, through the comparison of our islandpick method with a reference literature dataset of gis, that the prediction of gis can be performed using a fully automated comparative genomics approach. we produce reference gi datasets using islandpick that allow an independent analysis of the accuracy of several previously published sequence composition-based gi prediction tools. our analyses of the accuracy of gi predictors should aid researchers in formulating an appropriate approach to identify gis, based on whether they prefer high recall/sensitivity or precision/specificity. such gi predictors are likely to become of increasing importance in bacterial genome analysis, as appreciation grows of their significant role in adaptations of medical and environmental importance. 
our results indicate that alienhunter has the highest recall, but the lowest measured precision, while sigi-hmm is the most precise method. this represents the first evaluation, using diverse and, independent datasets that were not artificially constructed, of the accuracy of several sequence composition-based gi predictors. recently, multiple programs for automated detection of gis have been developed that utilize sequence composition characteristics, such as g+c ratio and dinucleotide bias. sigi-hmm and islandpath/dimob have comparable overall highest accuracy. using our constructed datasets, we investigated the accuracy of several sequence composition-based gi prediction tools. the approach involves 1) flexible, automated selection of comparative genomes for each query genome, using a distance function that picks appropriate genomes for identification of gis, 2) identification of regions unique to the query genome, compared with the chosen genomes and 3) identification of regions conserved across all genomes. we developed a comparative genomics approach that identifies both very probable islands and non-island regions. our comparative genomics approach, islandpick, was the most accurate, compared with a curated list of gis, indicating that we have constructed suitable datasets.
 genomic islands are clusters of genes in prokaryotic genomes of probable horizontal origin. gis are disproportionately associated with microbial adaptations of medical or environmental interest. recently, multiple programs for automated detection of gis have been developed that utilize sequence composition characteristics, such as g+c ratio and dinucleotide bias. to robustly evaluate the accuracy of such methods, we propose that a dataset of gis be constructed using criteria that are independent of sequence composition-based analysis approaches.  we developed a comparative genomics approach that identifies both very probable islands and non-island regions. the approach involves 1) flexible, automated selection of comparative genomes for each query genome, using a distance function that picks appropriate genomes for identification of gis, 2) identification of regions unique to the query genome, compared with the chosen genomes and 3) identification of regions conserved across all genomes. using our constructed datasets, we investigated the accuracy of several sequence composition-based gi prediction tools.  our results indicate that alienhunter has the highest recall, but the lowest measured precision, while sigi-hmm is the most precise method. sigi-hmm and islandpath/dimob have comparable overall highest accuracy. our comparative genomics approach, islandpick, was the most accurate, compared with a curated list of gis, indicating that we have constructed suitable datasets. this represents the first evaluation, using diverse and, independent datasets that were not artificially constructed, of the accuracy of several sequence composition-based gi predictors. the caveats associated with this analysis and proposals for optimal island prediction are discussed. 