genomic islands ( gis ) are clusters of foreign genes acquired from nongenealogical organisms through horizontal gene transfer ( hgt ) . previous studies have elucidated some hgt mechanisms , including ( i ) transformation , ( ii ) conjugation , ( iii ) transduction , and ( iv ) gene transfer agent . the occurrences of hgt make considerable contribution to genome evolution , which is especially evident in pathogenic organisms   or antibiotic resistant organisms [ 6 , 7 ] . such quantum - leap evolution can cause drastic changes to species , especially in bacteria , and shape the world where humans live [ 810 ] . therefore , it is practically significant to explore origins of gis ( i.e. , donors of gis ) . besides , the occurrence of hgt between highly divergent organisms has great impact on phylogenetics , which can disclose the evolutionary relationship of organisms . the acquired gis or biological features may contaminate the correctness of phylogenetic realtions therefore , exploring the origin donor of gis can also contribute to the analysis of genealogical phylogenetics . some previous research works of constructing donor - recipient network based on individual genes have been carried out [ 11 , 12 ] , where the network is composed of a set of vertices ( i.e. , organisms ) and edges , which connect vertices and reveal the occurrences of hgt between organisms . by studying the visualized networks , the researchers could uncover the hidden mechanisms of hgt such as genomic biases or barriers , dna repair bypasses , and eukaryotes origins and evolutions . while using individual genes for studying donor - recipient network can reveal the mechanisms of hgt to some degree , a hgt event usually occurs in a cluster of sequential genes instead of single genes separately . therefore , it may not truly reflect the donor - recipient networks accurately if using single - gene - based analysis . available gi detection tools these days make it possible to generate donor - recipient network based on gis . current gi prediction tools can be grouped into three categories : ( 1 ) sequence composition based approach , ( 2 ) comparative genome analysis approach , and ( 3 ) integrative approach . the most representative signatures include g + c content , dinucleotide biases , codon usage , mobility genes ( including transposases and integrases ) , and trna genes [ 14 , 15 ] . related tools using this kind of approach include alienhunter , centroid , gidetector , gihunter , pai ida , and sigi - hmm . comparative genome approach uses the phylogenetically close species as reference genomes and identifies subsequences that are unique in the query genomes and treats them to be gis . the integrative approach uses the prediction results of the above programs to obtain census gis . the availability of these gi tools , thus , provides us with a chance to study donor - recipient relationship through gis . in this paper , we propose using gis to trace the origins of gis and study donor - recipient networks across organisms . to make our donor - recipient networks meaningful , we model edges as weighted , which can be represented by the number of gis that a donor genome contributes to a recipient genome . in a previous study , it was hypothesized that if a hgt happened between two organisms , a series of subsequent directional transfers should be very likely to arise . therefore , it is reasonable to hypothesize that if two nongenealogical organisms harbor more occurrences of hgt , the more confident donor - recipient relationship is between them . in this study , we would also like to check whether donor - recipient relationship is random or biased . previous studies have shown that hgt is not a random event but of preferences to occur . it has been found that hgt occurs among organisms which share similar factors such as genome size , genome g / c composition , carbon utilization , and oxygen tolerance . , we will describe the dataset and our computational framework in detail ( it is freely available for noncommercial use at http://www5.esu.edu/cpsc/bioinfo/software/gidonor ) . in section 3 , we will illustrate the usage of computational framework on three case studies and discuss our predicted results with visualized networks . finally , we draw a conclusion in section 4 and discuss our possible future work . genbank , an open - access resource which is established and maintained by the national center of biotechnology information ( ncbi ) , houses all publicly available biological sequences such as genomic sequences and protein sequences . to trace gi donors , we collected all available prokaryotic nucleotide sequences from genbank , which covered 162 million sequences with 150 billion nucleotides bases in total . genbank provides different data formats for feeding different programs . for local based blast   search in our framework , this format is small in terms of size , so that it is convenient to download , and it can also be transformed into fasta format . for alienhunter , used for gi detection in our framework , we used fasta format . more specifically , we fed alienhunter with fasta nucleic acid files with the extension of essentially , our framework relies on two kinds of bioinformatics tools , sequence similarity search tool and gi prediction tool . we used blast as the sequence similarity tool since it is accurate and efficient in terms of computing time . we used sequence composition based gi tools for predicting gis in our framework because this kind of approach can be applied to any query genome sequence . by integrating multiple bioinformatics tools , our framework can process sequenced genomic data automatically and obtain final predicted donor organisms . the framework consists of five steps ( also shown in figure 1 ) , includingobtaining gis in a query genome with sigi - hmm;collecting initial candidate donor genomes by blast;predicting complete gi lists in candidate donor genomes using alienhunter;obtaining final donor genomes through overlapping;visualizing donor - recipient relationships.each step of our computational framework will be described in the following subsections . obtaining gis in a query genome with sigi - hmm ; collecting initial candidate donor genomes by blast ; predicting complete gi lists in candidate donor genomes using alienhunter ; obtaining final donor genomes through overlapping ; visualizing donor - recipient relationships . sigi - hmm , an open - source program , is based on genome composition analysis and is available for local installation , as well as web gui on islandviewer . sigi - hmm first analyzes the codon usage of each gene , provides the score for each gene based on the codon usage , and thus can find alien genes based on codon usage scores . because sigi - hmm produces the highest precision rate , guaranteeing the predicted gis to be true gis , we adopted it as the gi prediction tool in query genomes . because islandviewer has provided predicted gis by the program of sigi - hmm , we took advantage of it and obtained predicted gis for any query genome from islandviewer . in order to automatically collect gis provided by islandviewer , we developed a perl script to send out query genome information to islandviewer 's server and extract gi ranges from the islandviewer server . blast is extensively used in sequence similarity measurement due to its efficient computation , high accuracy , and the availability of cross - platforms . therefore , blast was incorporated into the framework for searching initial candidate donor genomes , which should contain genomic fragments similar to gi sequence in the query genomes . in blast , the cutoff value e is used to evaluate the similarity between genome sequences . in this study , we set e value of 10 as the cutoff to find our candidate donors . the blast output contains information of genome sequence alignments , alignment score , and e values , and such information can be processed systematically through open source of bioperl . therefore , we wrote a perl script that uses bioperl modules to extract relevant information from blast outputs . the initial candidate donor genomes obtained by blast search may contain some false positive donors ( i.e. , the genome fragments similar to those gis in the query genome are also transferred from donor genomes ) ; thus a filtering process should be conducted to remove such false positives and obtain final donor genomes . theoretically , the final candidates should possess a characteristic ; that is , the detected similar genomic fragments from blast should be original ( in other words , they are not gis ) in the corresponding hosts . in order to check whether such genomic fragments are original or not , we must use gi tools to check whether they are gis or not . we incorporated a gi tool alienhunter   in our framework to extract a complete list of gis for all initial candidate donor genomes . we chose the alienhunter tool in this step because previous assessment study on available gi tools   had shown that alienhunter possesses the highest recall rate , compared with other sequence compositions including sigi - hmm , islandpath , pai ida , and centroid . in other words , alienhunter can predict the most complete lists of gis in any candidate donor genome . this is very crucial because we can filter out more initial candidate donors and guarantee the final identified donors to true donors . in that sense , final donor genomes were obtained by filtering out initial candidate genomes ( obtained from section 2.2.2 ) , where genomic fragments similar to recipients of gis were also predicted as gis from section 2.2.3 . more formally , let a set {g , s , g } represent the information from previous steps , where g denotes the set of gis of a query genome obtained from sigi - hmm , s denotes the set of initial candidate donor genomes obtained from blast , and g denotes the set of gis on initial candidate genomes predicted from alienhunter . furthermore , for each of them,(i)g = { gii  0 } , 
 ( ii)s = { s(i , j)i , j  0 } , 
 ( iii)g = { gi , j ,   0 } , 
 where gi denotes the ith gi in query genome , s(i , j ) denotes the jth initial candidate donor for potentially donating ith gi ( gi ) on query genome , and g denotes uth gi for a candidate donor ( s(i , j ) ) . g = { gi , j ,   0 } , 
  for any given query genome , a list of final candidate donor genomes can be obtained by running the previous steps in our framework . in order to quantitatively visualize the number of donations from donors , we intended to produce a donor - recipient weighted network , where nodes denote donors and the recipient and the weights corresponding to edges are the number of hgt occurrences ( i.e. , quantified by the gi transfers ) between two organisms . by looking at heavy weighted edges in networks therefore , we utilized it to generate the donor - recipient network in our framework . we have applied our computational framework on three bacterial cases , including donor prediction of mycobacterium tuberculosis h37rv , herminiimonas arsenicoxydans , and a hgt network establishment of three species in thermoanaerobacter ( t. pseudethanolicus atcc 33223 , t. tengcongensis , and t. strain x514 ) . the possible hgt mechanisms of these species had been studied previously , and thus our predicted results could be investigated by comparing previous studies . mycobacterium tuberculosis ( m. tuberculosis ) is a bacterial species that causes most cases of tuberculosis ( tb ) . m. tuberculosis h37rv is the best characterized strain of m. tuberculosis and had been sequenced and analyzed biologically . previous work that combined genome - wide parametric analysis showed that m. tuberculosis encompassed 48 gis , which consist of 4.5% of the genome ( 199  kb ) , and include 256 genes [ 35 , 36 ] . through applying our framework in m. tuberculosis h37rv , we hope to reveal the origins of gis and provide a complete list of gi donors to substantially enrich the information of mycobacterial pathogenicity . figure 3 displays all predicted final candidate donors from our framework , where species with the same genus have been dyed with the same colors and positioned next to each other for better visualization . as shown in figure 3 , the predicted donor genus which contributed the most is gordonia , followed by nocardia and rhodococcus in descending rank . the number of gis , in which each genus of donors contributed to the recipient h37rv , has been summarized in figure 4 . when comparing our predicted donors of h37rv 's gis with the predicted potential donors from previous studies , we found that there are a lot of matching predictions . for instance , three donors with the highest donations , including gordonia , nocardia , and rhodococcus , were also detected as their potential origins of gis ( figures 3 and 4 ) . besides , we also incorporated bradyrhizobium and corynebacterium into our final candidate donors . in addition , our framework has detected a new potential donor , bifidobacterium animalis , which has not been reported in previous studies . we strongly believe in this as one of the high potential donors since b. animalis resides in the body of most mammals including humans , which may interact with m. tuberculosis and transfer genes to m. tuberculosis . herminiimonas arsenicoxydans ( h. arsenicoxydans ) is an arsenite - oxidizing bacterium that belongs to heterotrophic betaproteobacterium . it was isolated from heavy - contaminated sludge with arsenic and other heavy metals from industrial wastewater treatment plants . under aerobic conditions , it can oxidize arsenite to arsenate and produce at least two arsenate reductases . it was revealed to be able to resist against numerous heavy metals such as se , mn , cr , cd , sb , and ni . all of those competences enable its widely ecological usage in arsenical polluted environment . a better understanding of h. arsenicoxydans can be beneficial for arsenical polluted remediation . like previous network , species of the same genus have the same colors , and they are placed next to each other in the network . as we can see in the network of figure 5 , janthinobacterium marseille ( j. marseille ) is a highly frequent donor ( the occurrence of hgts is 11 times ) . actually , j. marseille belongs to the order burkholderiales , which has been reported to be the major gene donation source for h. arsenicoxydans . both our predicted results and previous studies strongly indicate that this is the donor for h. arsenicoxydans . we also notice that the number contributed by the genus of ralstonia is 16 times , which is also very significant . these findings strongly indicate that species in the burkholderiales order are major contributors to gis found in h. arsenicoxydans . another noticeable gis contributor was from the pseudomonadales order ( figures 5 and 6 ) , which was also consistent with previous study . therefore , we can conclude that the origins of gis in the genome of h. arsenicoxydans are from burkholderiales and pseudomonadales . thermoanaerobacter is a genus that contains a cluster of thermophilic and anaerobic bacteria distributed in high - temperature surroundings like springs . they can absorb heat from surroundings as their source of energy to drive their metabolism . therefore , it will be particularly interesting to study the adaptability of thermophile , examine the evolution path , and ultimately uncover the origins of such special features . a simplified directed network of donor - recipient relationship has been generated in previous work . the directed network was focused on three members of thermoanaerobacter , including t. pseudethanolicus strain atcc33223 , t. tengcongensis , and t. strain x514 . we extended the previous network with more predicted donors as shown in figures 7 and 8 . as you can see , our directed network has expanded previously studied network on a basically consistent condition . for instance , we predicted one gi in t. strain x514 that originally belongs to clostridium thermocellum atcc 27405 . this is consistent with their predicted result even though they considered it as a mediator , which played an agent role in the transfer . we also detected seven gi transfers between t. pseudethanolicus strain atcc33223 and t. strain x514 and one gi transfer from t. pseudethanolicus strain atcc33223 to t. tengcongensis mb4 . most noticeably , t. brockii finnii ako-1 was present as the donor for all three query genomes as shown in figure 5 . we hypothesize that t. brockii finnii ako-1 interacts with these three thermoanaerobacter species and may contribute heat - resistant related genes to these species . hgt has provided organisms apportunities to obtain special features from foreign organisms . in order to reveal genetic sources of hgt , the predicted results in this study were consistent with previous studies , strongly indicating the correctness of our computational framework overall . in addition , our framework has also discovered some new donors not reported in previous studies , and further investigation of these new discoved donors indicates that they are possible donors in the biological and evolutionary perspective . while there is no standard benchmark to measure the accuracy of our framework , it should be noted that the accuracy of our framework depends on the performance of other prediction tools . on the one hand , on the other hand , we adopted sequence composition analysis tools , which is generally applicable to any sequenced query genome , but the prediction is not the most accurate one when compared to comparative genome analysis gi tools . for instance , a genome with a typic genome size will take about one hour to complete the entire process of gi search . thus , for a query genome , it could generate dozens of initial candidate donor genomes , and thus it takes about a day and night to complete the whole process . in this study , we just studied three query genomes , for the purpose of testing the correctness of our computational framework . in the next stage , we will use a cluster of computers or superpower computers , to predict hgt donors for all sequenced bacterial and archaea genomes using our framework . we will build a large - scale donor - recipient network based on all the results . we believe that such kind of networks will reveal a panoramic view of gene transfer information across microbial organisms and provide some insights into evolutionary biologists to study genome evolution .
genomic islands ( gis ) are chunks of genomic fragments that are acquired from nongenealogical organisms through horizontal gene transfer ( hgt ) . 
 current researches on studying donor - recipient relationships for hgt are limited at a gene level . as more gis have been identified and verified , the way of studying donor - recipient relationships can be better modeled by using gis rather than individual genes . in this paper , we report the development of a computational framework for detecting origins of gis . 
 the main idea of our computational framework is to identify gis in a query genome , search candidate genomes that contain genomic regions similar to those gis in the query genome by blast search , and then filter out some candidate genomes if those similar genomic regions are also alien ( detected by gi detection tools ) . 
 we have applied our framework in finding the gi origins for mycobacterium tuberculosis h37rv , herminiimonas arsenicoxydans , and three thermoanaerobacter species . 
 the predicted results were used to establish the donor - recipient network relationships and visualized by gephi . 
 our studies have shown that donor genomes detected by our computational approach were mainly consistent with previous studies . 
 our framework was implemented with perl and executed on windows operating system .