BACKGROUND
genomic and metagenomic projects provide an increasing amount of molecular data with a considerable genetic diversity.
a portion of these nucleic and proteic data is amenable to standard computationally expensive phylogenetic analyses, through the use of multiple alignments and the construction of individual or concatenated gene phylogenies  <cit> .
however, evolutionary analyses of many of these sequences can be carried out using other, less time consuming and more inclusive, approaches  <cit> .
typically, phylogenetic reconstruction is suited for analyzing subsets of homologous genes that can be aligned with confidence.
distant homologs are thus generally absent from these analyses  <cit> .
moreover, even though classic phylogenetic analyses only require that sequences to be compared are alignable, they often focus on the genealogical relationships between entities from the same level of biological organization  resulting from the process of vertical descent.
however, gene trees affected by processes of introgressive descent such as lateral gene transfer   <cit>  pose significant challenges to the reconstruction of a universal tree  <cit>  or phylogenetic network of life  <cit> .
in particular, it is difficult to study the incongruence between the histories of gene families with uneven distribution among microbial genomes.
in addition, it is difficult to represent the transfer of dna between donors and hosts, while including the vectors responsible for these genetic exchanges on a single representation  <cit> .
viruses  are indeed most often not considered to be related to cellular beings, and their evolution as well as that of their genes is generally not described along the organismal species tree  <cit> .
thus some evolutionary information contained in genomic and metagenomic data is not readily exploited in standard phylogenetic analyses.
consistently, a new suite of methods is becoming increasingly popular, in order to handle more of the complexity of such data.
network-based approaches, that display similarity in a wealth of molecular sequences, have started to offer a valuable complement to improve our evolutionary knowledge on the processes responsible for lgt, as well as on the sources of genetic diversity.
they provide useful tools to analyze mosaic sequences  <cit> , genomes harbouring sequences from multiple origins  <cit>  and the migration of dna across metagenomes  <cit> .
network-based approaches also provide an additional framework in which the genetic diversity of sequences, genomes, or metagenomes can be compared and quantified using graph estimators, even for highly divergent sequences  <cit> .
in general terms, we describe an evolutionary  network  as any graph connecting nodes representing individual sequences, individual genomes or metagenomes, by edges, when these objects present some similarity according to various combinations of operational criteria .
for the moment, due to the lack of user-friendly freely distributed dedicated software, the construction and analysis of sequence similarity networks requires a certain amount of computer programming skills, and remain less accessible  to biologists than standard phylogenetic approaches.
here, we introduce a simple but powerful software program, egn , for the reconstruction of similarity networks from large molecular datasets that may expand the toolkit of evolutionary biologists.
egn is programmed in perl v <dig> .
<dig>  it is fast, portable, and runs on linux and osx systems.
egn automates the construction of gene and genome networks from nucleic and proteic sequences, coupled to simple statistics describing genetic diversity in these samples, for various user-defined thresholds of similarities.
we illustrate some of the options available in egn, and the novel type of data it exploits.
then, as a proof of concept, we show how egn can be used to study the complexity of evolutionary processes affecting microbial evolution.
we tested whether plasmids were always used as genetic couriers, moving dna from one lineage to another.
our null hypothesis was therefore that plasmids should always connect to more than one lineage in a gene sharing network in our dataset of  <dig> proteic sequences, sampled in genomes from the three domains of life and mobile genetic elements.
our network approaches were able to reject this null hypothesis by identifying a set of plasmids in borrelia that is not being used as such couriers.
in this case, plasmids appear to have a different function – that of “evolutionary sandbox”-that contributes to the creation of genetic diversity within their bacterial host lineage.
implementation
egn is implemented in perl.
v <dig> .
<dig>  the script and a user guide are freely available under the gnu gpl license as additional file  <dig> or at http://evol-net.fr.
network construction steps are presented in a simple contextual menu.
egn handles massive datasets of nucleic and/or proteic sequences from fasta files in defline format.
it automates the identification of homologous sequences using user-defined homology search software .
in short, the identification of similar sequences relies on parameters defining relevant hits , and on parameters tagging the hit quality .
in egn, these parameters can be defined by the user.
after a step of all against all comparison, clusters of sequences with significant similarities are identified using the exhaustive simple link algorithm  <cit> , so that any sequence in a cluster presents at least a significant similarity with another sequence of the cluster, and no similarity with any sequence outside the cluster.
graph-wise, these clusters are called connected components.
egn provides several statistical information for each network as an output file: the average percentage of sequences identity, size , number of connected components, and a global estimate of the clustering within each component, called graph density, implemented as:
g=2*numberofedgesnumberofnodes*numberofnodes− <dig>
graph density is comprised between  <dig> and  <dig> .
the distribution of these connected components in each species/samples is also compiled in a tabulated text outfile.
moreover, egn produces files that are importable in the popular cytoscape  <cit>  and gephi  <cit>  network visualization software programs, in which gene and genomes networks can be further analyzed.
egn also generates fasta files of sequences in each connected component.
these files can be used to generate alignments and standard analyses of selection or phylogenetic analyses.
for details, we refer to the user guide.
RESULTS
egn analytical workflow
egn is a script implemented in perl.
v <dig> .
<dig> on the linux and macosx platforms for generating evolutionary gene and genome networks from molecular data .
a simple menu allows users to easily manage the step by step procedure and set up relevant parameters for their analyses.
however, blastall   <cit>  or blat  <cit>  must be installed on the computer where egn is executed, and their directory locations properly specified in the os.
once egn is installed, it will take as input one or many files of sequences  located in a working directory, chosen by the user .
the extension of these files must be either .fna, for dna and rna sequences, or .faa, for protein sequences.
in the case of unique sequence type, user can choose between blast or blat homology searches to compare these sequences.
if the dataset is composed of both nucleic and proteic sequences, blast will be chosen and egn will automatically run blastn for nucleic sequences comparison, blastp for proteic sequences comparison, while comparisons between nucleic and proteic sequences will be performed by blastx and tblastn.
to this end, egn must simply be invoked using the command line ‘perl egn.pl’.
the software then proposes several analyses, organized in a stepwise fashion .
first, egn parses the fasta infiles present in the working directory to i) check that their format is correct , ii) to extract useful information about the sequences that will figure in the nodes of the networks under reconstruction , and iii) to assign a local egn identifier to each sequence in order to speed up the next calculation steps.
once this step of creation of properly formatted input files  is successfully achieved, the user can perform two kinds of similarity searches between sequences in these files , either by selecting blastall  <cit> , or blat  <cit> , a faster software program, that speeds up the analysis of very large sequence infiles, but may be less accurate.
the user can edit the egn.config file to modify the search parameters of each of these programs or use the wizard implemented in egn.
on multi-core computers, the speed of the blast search can be enhanced by changing the number of processors .
likewise, we implemented the parallelization of multiple blat processes in egn .
in order to reconstruct a comprehensive similarity network, all sequences can be compared against all.
to this end, a third step of egn  parses the results of the similarity search according to a set of properties that any pair of sequences showing similarity must satisfy to be included in a gene or genome network.
this parsing step can be optimized since the user can select between two algorithms, depending on the amount of available memory on his/her computer.
egn offers a ‘quicker’ parsing step , requiring a maximum amount of memory, and a ‘slower’ parsing step , needing less memory, but more free disc space.
under both parsing options, the same large number of desired conditions is available to select relevant sequences and similarity relationships in the edges file creation menu.
option  <dig> of this menu allows the user to determine a maximal e-value threshold to discard sequences that show too little similarity to be further considered.
this decision is facilitated by a simple text interface .
moreover, important additional levels of stringency concerning features of the hit  can likewise be specified.
option  <dig> can be used to impose a minimal percentage of identity over the hit .
in addition, option  <dig> can be applied to filter out edges between sequences, when the number of identical bases represents more than a minimal percentage of the shortest sequence length .
option  <dig> can be used to perform a similar operation since it eliminates edges in which the hit has a minimal absolute length .
finally, two other properties can also be used to label pairs of similar sequences satisfying the above conditions, and build gene and genome networks.
option  <dig> evaluates the strength of the similarity between pairs of sequences.
in order to determine when two sequences a and b are best-reciprocal hits, egn computes the e-value of the sequence b in the blast  search where sequence a is used as a seed, with the e-value of sequence a in the blast  search where sequence b is used as a seed.
sequences a and b may not be each other first best hits in these searches, but when their evalues are no more than a certain used defined percentage away from the top scoring hit in these searches, then sequences a and b are considered as best-reciprocal.
by default, this percentage is set to  <dig>  this distinction matters to reconstruct networks based on “best-reciprocal” similarity edges vs networks based on any similarity edges, be they “best reciprocal” or not.
option  <dig> provides a second qualifier for pairs of similar sequences.
it allows the user to filter for the extent of the pairwise similarity, i.e.
whether a hit spans a great or a small portion of each of the similar sequences.
by default, pairs of sequences for which the hit corresponds to ≥ 90% of each sequence length are considered as “homology” edges.
such similarity is not limited to a fragment of any of these sequences, which could happen when significant similarity occurs only for a short region of the sequence, e.g.
partial similarity caused by the sharing of a domain.
after these criteria have been set, and the parsing has been carried out, egn can effectively generate outfiles for two kinds of networks: gene and genome networks .
this step of network reconstruction also allows the user the option of setting additional selection criteria concerning the edges that will be retained.
by default, edges corresponding to hits with a maximal blast e-value of 1e- <dig>  20% identity, and longer than 20% of the smallest similar sequence will feature in gene networks, and be used to reconstruct clusters of similar sequences .
if two samples/genomes contain sequences belonging to the same cluster, egn will produce an edge in the genome network between these samples/genomes.
in this last construction step, egn not only generates network outfiles in cytoscape  <cit>  and/or gephi format  <cit> , it also optimizes the content of these outfiles.
typically, gene networks may contain hundreds of thousands of subgraphs, corresponding to the cluster of similar sequences, or connected components in graph terms .
thus, to ease the visualization of these connected components in cytoscape and gephi, egn distributes them in files called  cc_#x_to_#y.txt, organizing these subgraphs by decreasing number of edges, and  att_ cc_#x_to_#y.txt, in which all important attributes describing these nodes and edges  have been automatically summarized.
these attribute files provide useful information for coloring the nodes and edges in the visualization network tools.
finally, egn also provides some statistics about the sequences, and the connected components comprising of similar sequences.
these text outfiles are created in subdirectories with explicit names, describing the exact parameters retained to perform the network reconstruction .
in particular, the gpcompo.txt outfile indicates for each cluster of similar sequences how many representative sequences it contains, and from which sample/genome these sequences originate.
the gpstat.txt outfile provides further information about genetic divergence of these sequences: how much they cluster with one another in the network, the mean and standard deviation hit % identity between sequences in the cluster, the mean and standard deviation of % identity between the hit and the shortest sequence considered in each pairwise comparison, and the mean and standard deviation of the e-value between sequences of the cluster.
as the user is guided along the various steps of the intuitive egn menus, this wizard provides a tool with which users will be able to analyze their data under the framework of similarity networks.
egn automates the analysis of a significant data type
egn produces a useful network-based type of data for evolutionary analyses.
this data type is different from the usual phylogenetic trees, for at least two reasons.
first, while trees are always acyclic graphs, networks are generally cyclic graphs.
second, while phylogenetic trees usually aim at inferring the relationships between homologous sequences and their hypothetical ancestors, sequence similarity networks instead display significant resemblances between any sequences  or any entities , in a topologically less constrained, and in practice much more inclusive, framework.
the usual data type used in phylogenetics is a tree , while it is a connected component in a sequence similarity network.
in these latter networks, no explicit orthology relationship needs to be assumed.
it is important to establish the distinction between these two data types, because it would be a logical mistake to evaluate connected components using the standards of phylogenetic trees, e.g.
as if they were trees, which they are not.
sequence similarity networks are founded on a different theoretical background than phylogenetic analyses, which implies that the splits and edge lengths have different meanings than those observed in a phylogenetic tree or network.
in fact, connected components are better understood by reference to “family resemblances” .
just like family members in humans present various overlapping and criss-crossing resemblances, i.e.
in their build, features, colours of eyes, organized in such ways that it is eventually possible and useful to distinguish different families, connected components in sequence similarity networks group sets of sequences, whose members show significant similarity according to a criterion , so that these sequences cannot be mistaken for other sequences, presenting a different pattern of “family resemblance”.
for instance, sequences coding for translation initiation factors sui <dig> and for restriction modification type  <dig> endonucleases fall into distinct connected components in gene networks  <cit> .
in this regard, it is interesting to note that phylogenetic gene trees are a particular display of one very particular instance of ‘family resemblance’.
such trees group sequences that are sufficiently similar to be aligned together, because they come from a single last common ancestor.
however, sequences can also  display significant similarities that do not meet the particular criteria retained in phylogenetics.
for instance, sequences resulting from fusion or recombination events will show bona fide similarities introduced by processes of introgressive descent  <cit> .
sequences evolving by vertical descent from a single ancestor can also become too divergent to be aligned with their homologs, and therefore to be included in a gene tree.
such distant similarities, and resemblances originating from processes of introgressive descent, however can be analyzed through the definition of connected components, as automated by egn.
for example, when the parameters selected for the reconstruction of the gene networks are very stringent, imposing that the hit between sequences covers a high percentage of their length, and that the similar sequences show both a high e-value and % identity, allows to include divergent homologs in connected components.
unlike conserved homologs that will be all connected together , divergent homologs will only connect to some of the sequences within the component; i.e.
divergent bacterial genes will only bond to some of their bacterial homologs, while less divergent bacterial genes will all be joined to one another.
consistently, the data type that is obtained by structuring molecular data in connected components of sequences in sequence similarity networks , contributes in a different way than phylogenetics to extend the scope of evolutionary analyses.
evolutionary biologists can take advantage of this additional data type to explore and explain the various causes of their ‘family resemblances’.
processes of introgressive descent  and vertical descent can be investigated simultaneously through these graphs.
phylogenetic relationships however will generally still require the reconstruction of a tree.
furthermore, this novel data type also provides an original comparative framework, which must not be confused with the phylogenetic framework.
more precisely, egn networks make it possible to compare sequence similarities for sequences of interest in connected components, i.e.
by quantifying the distances and topological properties of sequences from two genomes in the network.
this comparison cannot be equated with the phylogenetic resolution required to identify where a particular sequence  should be placed in a gene  tree, but it can be useful in other situations.
among the most recent examples, a comparative analysis of the behavior of sequences in gene networks was carried out by bhattacharya et al.
<cit>  to investigate the modular genomic structure of a novel marine cyanophage in a protist single cell metagenome assembly.
sequences from these novel mosaic viruses presented a pattern of connection that was typical of that presented by sequences from mosaic cyanophages in the gene network.
the use of a network proved particularly well-suited, offering much more detail concerning the complex evolution of such mosaic objects than allowed by the proposition of a single branching point in a viral tree for the novel virus.
one main interest of network studies is therefore that they can employ an additional, very inclusive, relevant - although non-phylogenetic - data structure for evolutionary analyses.
application to real data
we used egn to illustrate how its various options areuseful for devising and testing evolutionary hypotheses, while taking into account a large amount of data structured according to this data type.
we tested whether plasmids were always used as genetic couriers, moving dna from one lineage to another in a dataset of  <dig>  protein sequences .
we first used egn  to reconstruct a genome network of  <dig> cellular organisms,  <dig>  plasmids and  <dig>  viral genomes, harboring either cellular chromosomes or genomes of mobile genetic elements at its nodes, connected when they shared sequences from the same similarity cluster, as in halary et al.
<cit> .
in the genome network, some plasmids displayed markedly distinct behaviors and patterns of connections, identifying two extreme sorts of plasmids.
on the one hand, many plasmids had a broad range of connections with a diversity of distantly related genetic partners.
these plasmids act as genetic couriers  <cit> , contributing to exchanges of dna material.
on the other hand, some other plasmids were very isolated in the network, showing a very limited and sometimes even no genetic partnerships outside a limited gene sharing with the plasmids or the chromosomes of their host lineage.
plasmids of this second type typically use a closed dna pool, and seem to rarely transit between different hosts cells and lineages, and even to rarely exchange genetic material with the chromosome of their hosts.
rather than being mobile vessels of genetic exchange, our network suggests that these non-promiscuous plasmids may fulfill a functional role of evolutionary significance distinct from that of the plasmids that are key players for lateral gene transfer.
the best examples are offered by the plasmids of the bacterial genus borrelia, which display a very low conductance .
indeed, the corresponding/respective nodes are extremely isolated in the genome network, and are linked to it just by edges with nodes of the borrelia chromosomes .
borrelia’s plasmids do not share a single gene family with any other plasmids outside these hosts , and only harbor six genes , that are also found on borrelia’s main chromosome , consistently with the literature  <cit> .
in agreement with tamminen et al.
<cit> , our genome network identifies that the flow of dna material in and out of borrelia plasmids is lower than for many other plasmids.
this remarkable genetic isolation may be explained by biological considerations, prompted by the detection of this network structure.
borrelia is an obligate pathogen  <cit> .
this lifestyle entails that these bacteria have fewer opportunities to meet a diversity of genetic partners  than the majority of the bacteria growing in biofilms  <cit> .
borrelia genetic diversity must come from within the lineage, rather than from adaptative gene transfer from other microbes, even though borrelia’s plasmids are able to transfer  <cit> .
moreover, borrelia’s lifestyle imposes a strong selective pressure on these parasitic cells that must constantly evolve to escape their host immune system.
plasmids within borrelia play a role in this evasion process  <cit> , and we hypothesize that it is because they provide a genetic compartmentalization inside the cells that allows borrelia to partition dna on two distinct kinds of molecules with distinct evolutionary regimes  <cit> .
most of the genes are located on a slow evolving linear chromosome, heavily constrained in its structure, while other genes are stored on the more flexible, fast evolving, and heavily recombining plasmids <cit> .
we propose that this partition helps borrelia cells to survive in a hostile environment.
the chromosomes are highly streamlined and optimized to support borrelia’s parasitic life, while the plasmids would be the locus of substantial rearrangements, recombination and gene conversion, producing necessary variations on genes coding for outer surface proteins , genes that repress the cytolitic activity of host’s serum , and genes coding for antigenic variation  to escape borrelia’s host immune system  <cit> .
to further this hypothesis - that some plasmids act as compartments of dna material and intracellular organs of genetic innovation rather than vectors of mobile dna - we used the hit coverage option of egn’s gene network reconstruction, that we set to > 90%.
this option allowed us to distinguish two types of edges in sequences network.
we used egn to detect and quantify “full homology” edge links between borrelia’s sequences.
sequences connected by “full homology” edges have probably progressively diverged by the combined effects of small mutations, natural selection and drift, because their sequences greatly overlap, and can be aligned all along their length.
by contrast, when sequences are not only evolving in a tree-like fashion, i.e.
when segments of divergent sequences fuse to form a single a gene, or when segments within genes recombine through illegitimate recombination, sequences are connected by edges that are not necessarily “full homology” edges  <cit> .
these sequences do not come entirely from a single ancestral gene copy, but various segments of these sequences have a diversity of sources.
such sequences, produced by more complex processes than vertical descent alone, do not neatly align all along their sequences, but are at best only connected through local regions of similarity.
such similar segments, as opposed to similarity overall their dna, are also detected in egn analyses: they constitute a second type of edge in gene networks .
interestingly, we observed that connected components of borrelia’s chromosomes were largely connected by “full homology” edges , but that connected components on borrelia’s plasmids were largely connected by “partly similar edges”, and therefore seemed to be subjected to more complex evolutionary processes.
these processes result in a large amount of genetic diversity in the plasmids.
this result, based on a gene network,  strengthens our hypothesis that a structural partition of dna within borrelia’s cells  is coupled with a “partition” of the processes affecting this dna, in that case contributing to the recruitment of borrelia’s plasmids as “organs of genetic innovation”.
in other words, borrelia’s plasmids and their genes can be seen as private goods of the borrelia lineage  <cit> : they benefit to this lineage but are not shared with others.
of course, quite a few other prokaryotic genera contain plasmids with low conductances, such sodalis, coxiella , and buchnera  .
we do not wish to elaborate here on whether the lifestyle of these bacteria may explain this relative genetic isolation.
sodalis are intra and intercellular symbionts, buchnera are obligate intracellular symbionts and coxiella are obligate intracellular pathogens.
however, we want to underscore the fact that sequence similarity network can be a great tool to foster this type of hypothesis.
CONCLUSIONS
the use of similarity networks appears as a compelling complement to standard phylogenetic analyses in order to perform comparative analyses of an increasing amount of molecular sequences from genomic and metagenomic projects.
several publications have already benefited from this analytical framework  <cit> .
however, such network analyses still require more programming skills than is usually necessary to carry out phylogenetic analyses, for which users can rely on a diversity of user-friendly software.
by contrast, few  user friendly software programs, running on desktop computers, explicitly designed to reconstruct distinct kinds of similarity networks from nucleic and/or proteic data have yet been made available to the biology community.
we introduce egn in the hope that it might constitute a timely opportunity to provide network construction tools to a broader audience.
we are confident that software like egn will enhance the exploitation of the evolutionary signal of genomic and metagenomic projects.
genomic datasets and analysis parameters
we sampled  <dig>  protein sequences from the chromosomes of  <dig> eubacterial complete genomes,  <dig> archaebacterial complete genomes, and  <dig> eukaryotic genomes, covering the diversity of cellular life, as well as from the genomes of two types of mobile genetic elements:  <dig>  protein sequences from all the available plasmids and phages at the time of this analysis from the ncbi .
we first used egn  to construct a genome network, harboring either cellular chromosomes or genomes of mobile genetic elements at its nodes, connected when they shared sequences belonging to the same cluster of similar sequences, as in halary et al.
<cit> .
to test whether plasmids hosted in a bacterial lineage were connected to genomes in multiple other lineages, we estimated the conductance of their nodes  in the genome network.
for instance, for plasmids of borrelia, we estimated c as the number of edges connecting borrelia’s nodes to non-borrelia’s nodes / number of edges connecting borrelia’s nodes to any node  <cit> .
we assessed whether the observed value for c was significantly different and lower than the conductance obtained by chance for the same number of nodes in the genome network by shuffling node labels on the same network topology for  <dig>  replicates, which estimates the various conductances expected by chance alone in a network of same size and with the same topology.
in order to test whether genes within borrelia chromosomes and plasmids had been affected by different evolutionary processes, we then reconstructed the similarity network of borrelia genes using the same parameters, but setting up the hit coverage condition at > 90% .
number of ‘positive’ and ‘negative’ edges linking plasmidic gene to plasmidic gene, plasmidic gene to chromosomal gene, and chromosomal gene to chromosomal gene were quantified.
over- or under- representation of such edges was also estimated by shuffling node labels on the same network topology for  <dig>  replicates.
availability and requirements
•project name:egn
•project home page:http://www.evol-net.fr/index.php/fr/downloads
•operating system: linux platform and osx
•programming language: perl.
v <dig> .1
•other requirements: blast + versions ≥ v <dig> .
<dig> or blast all versions ≥ v <dig> .
<dig> or blat
•license: gnu gpl
•any restrictions to use by non-academics: none
availability of supporting data
the dataset supporting the results of this article is available in the repository of http://www.evol-net.fr/index.php/fr/downloads.
the egn script and a user guide are also available at this address and as additional file  <dig>
abbreviations
egn: evolutionary gene and genome network; c: conductance.
competing interests
the authors declare that they have no competing interest.
authors’ contributions
eb, pl and sh designed the software.
sh implemented the software.
eb, pl and jmi designed the experiment.
eb, pl, jom and sh analyzed the results.
eb, jom, and sh wrote the paper.
all authors read and approved the final manuscript.
supplementary material
additional file 1
a zip archive containing the egn script and a user guide.
click here for file
additional file 2: table s1
an xls table including the summary of the conductance analyses for all plasmids and plasmids of all the prokaryotic genera present in our analyses.
click here for file
additional file 3: figure s1
a tif file with the graphical representation of the conductance analyses for all plasmids and plasmids of all the genera present in our analyses.
y-axis corresponds to the conductance value  of these plasmids.
each dot corresponds to a class of plasmids.
dots colored in red, black, green and purple correspond to plasmids hosted in borrelia, sodalis, coxiella and buchnera, respectively.
click here for file
acknowledgments
sh was supported by the genome canada/genome quebec research grant genorem granted to f. lang  and among other co-applicants, m. st-arnaud and m. hijri.
eb, pl and jom were supported by a phc ulysses  <dig> grant .

 genomic and metagenomic projects provide an increasing amount of molecular data with a considerable genetic diversity. a portion of these nucleic and proteic data is amenable to standard computationally expensive phylogenetic analyses, through the use of multiple alignments and the construction of individual or concatenated gene phylogenies. however, evolutionary analyses of many of these sequences can be carried out using other, less time consuming and more inclusive, approaches. typically, phylogenetic reconstruction is suited for analyzing subsets of homologous genes that can be aligned with confidence. distant homologs are thus generally absent from these analyses. moreover, even though classic phylogenetic analyses only require that sequences to be compared are alignable, they often focus on the genealogical relationships between entities from the same level of biological organization resulting from the process of vertical descent. however, gene trees affected by processes of introgressive descent such as lateral gene transfer pose significant challenges to the reconstruction of a universal tree or phylogenetic network of life. in particular, it is difficult to study the incongruence between the histories of gene families with uneven distribution among microbial genomes. in addition, it is difficult to represent the transfer of dna between donors and hosts, while including the vectors responsible for these genetic exchanges on a single representation. viruses are indeed most often not considered to be related to cellular beings, and their evolution as well as that of their genes is generally not described along the organismal species tree. thus some evolutionary information contained in genomic and metagenomic data is not readily exploited in standard phylogenetic analyses. consistently, a new suite of methods is becoming increasingly popular, in order to handle more of the complexity of such data. network-based approaches, that display similarity in a wealth of molecular sequences, have started to offer a valuable complement to improve our evolutionary knowledge on the processes responsible for lgt, as well as on the sources of genetic diversity. they provide useful tools to analyze mosaic sequences, genomes harbouring sequences from multiple origins and the migration of dna across metagenomes. network-based approaches also provide an additional framework in which the genetic diversity of sequences, genomes, or metagenomes can be compared and quantified using graph estimators, even for highly divergent sequences. in general terms, we describe an evolutionary network as any graph connecting nodes representing individual sequences, individual genomes or metagenomes, by edges, when these objects present some similarity according to various combinations of operational criteria. for the moment, due to the lack of user-friendly freely distributed dedicated software, the construction and analysis of sequence similarity networks requires a certain amount of computer programming skills, and remain less accessible to biologists than standard phylogenetic approaches. here, we introduce a simple but powerful software program, egn, for the reconstruction of similarity networks from large molecular datasets that may expand the toolkit of evolutionary biologists. egn is programmed in perl v. it is fast, portable, and runs on linux and osx systems. egn automates the construction of gene and genome networks from nucleic and proteic sequences, coupled to simple statistics describing genetic diversity in these samples, for various user-defined thresholds of similarities. we illustrate some of the options available in egn, and the novel type of data it exploits. then, as a proof of concept, we show how egn can be used to study the complexity of evolutionary processes affecting microbial evolution. we tested whether plasmids were always used as genetic couriers, moving dna from one lineage to another. our null hypothesis was therefore that plasmids should always connect to more than one lineage in a gene sharing network in our dataset of proteic sequences, sampled in genomes from the three domains of life and mobile genetic elements. our network approaches were able to reject this null hypothesis by identifying a set of plasmids in borrelia that is not being used as such couriers. in this case, plasmids appear to have a different function – that of “evolutionary sandbox”-that contributes to the creation of genetic diversity within their bacterial host lineage. implementation egn is implemented in perl. v. the script and a user guide are freely available under the gnu gpl license as additional file or at http://evol-net.fr. network construction steps are presented in a simple contextual menu. egn handles massive datasets of nucleic and/or proteic sequences from fasta files in defline format. it automates the identification of homologous sequences using user-defined homology search software. in short, the identification of similar sequences relies on parameters defining relevant hits, and on parameters tagging the hit quality. in egn, these parameters can be defined by the user. after a step of all against all comparison, clusters of sequences with significant similarities are identified using the exhaustive simple link algorithm, so that any sequence in a cluster presents at least a significant similarity with another sequence of the cluster, and no similarity with any sequence outside the cluster. graph-wise, these clusters are called connected components. egn provides several statistical information for each network as an output file: the average percentage of sequences identity, size, number of connected components, and a global estimate of the clustering within each component, called graph density, implemented as: g=2*numberofedgesnumberofnodes*numberofnodes− graph density is comprised between and. the distribution of these connected components in each species/samples is also compiled in a tabulated text outfile. moreover, egn produces files that are importable in the popular cytoscape and gephi network visualization software programs, in which gene and genomes networks can be further analyzed. egn also generates fasta files of sequences in each connected component. these files can be used to generate alignments and standard analyses of selection or phylogenetic analyses. for details, we refer to the user guide.  egn analytical workflow egn is a script implemented in perl. v. on the linux and macosx platforms for generating evolutionary gene and genome networks from molecular data. a simple menu allows users to easily manage the step by step procedure and set up relevant parameters for their analyses. however, blastall or blat must be installed on the computer where egn is executed, and their directory locations properly specified in the os. once egn is installed, it will take as input one or many files of sequences located in a working directory, chosen by the user. the extension of these files must be either.fna, for dna and rna sequences, or.faa, for protein sequences. in the case of unique sequence type, user can choose between blast or blat homology searches to compare these sequences. if the dataset is composed of both nucleic and proteic sequences, blast will be chosen and egn will automatically run blastn for nucleic sequences comparison, blastp for proteic sequences comparison, while comparisons between nucleic and proteic sequences will be performed by blastx and tblastn. to this end, egn must simply be invoked using the command line ‘perl egn.pl’. the software then proposes several analyses, organized in a stepwise fashion. first, egn parses the fasta infiles present in the working directory to i) check that their format is correct, ii) to extract useful information about the sequences that will figure in the nodes of the networks under reconstruction, and iii) to assign a local egn identifier to each sequence in order to speed up the next calculation steps. once this step of creation of properly formatted input files is successfully achieved, the user can perform two kinds of similarity searches between sequences in these files, either by selecting blastall, or blat, a faster software program, that speeds up the analysis of very large sequence infiles, but may be less accurate. the user can edit the egn.config file to modify the search parameters of each of these programs or use the wizard implemented in egn. on multi-core computers, the speed of the blast search can be enhanced by changing the number of processors. likewise, we implemented the parallelization of multiple blat processes in egn. in order to reconstruct a comprehensive similarity network, all sequences can be compared against all. to this end, a third step of egn parses the results of the similarity search according to a set of properties that any pair of sequences showing similarity must satisfy to be included in a gene or genome network. this parsing step can be optimized since the user can select between two algorithms, depending on the amount of available memory on his/her computer. egn offers a ‘quicker’ parsing step, requiring a maximum amount of memory, and a ‘slower’ parsing step, needing less memory, but more free disc space. under both parsing options, the same large number of desired conditions is available to select relevant sequences and similarity relationships in the edges file creation menu. option of this menu allows the user to determine a maximal e-value threshold to discard sequences that show too little similarity to be further considered. this decision is facilitated by a simple text interface. moreover, important additional levels of stringency concerning features of the hit can likewise be specified. option can be used to impose a minimal percentage of identity over the hit. in addition, option can be applied to filter out edges between sequences, when the number of identical bases represents more than a minimal percentage of the shortest sequence length. option can be used to perform a similar operation since it eliminates edges in which the hit has a minimal absolute length. finally, two other properties can also be used to label pairs of similar sequences satisfying the above conditions, and build gene and genome networks. option evaluates the strength of the similarity between pairs of sequences. in order to determine when two sequences a and b are best-reciprocal hits, egn computes the e-value of the sequence b in the blast search where sequence a is used as a seed, with the e-value of sequence a in the blast search where sequence b is used as a seed. sequences a and b may not be each other first best hits in these searches, but when their evalues are no more than a certain used defined percentage away from the top scoring hit in these searches, then sequences a and b are considered as best-reciprocal. by default, this percentage is set to this distinction matters to reconstruct networks based on “best-reciprocal” similarity edges vs networks based on any similarity edges, be they “best reciprocal” or not. option provides a second qualifier for pairs of similar sequences. it allows the user to filter for the extent of the pairwise similarity, i.e. whether a hit spans a great or a small portion of each of the similar sequences. by default, pairs of sequences for which the hit corresponds to ≥ 90% of each sequence length are considered as “homology” edges. such similarity is not limited to a fragment of any of these sequences, which could happen when significant similarity occurs only for a short region of the sequence, e.g. partial similarity caused by the sharing of a domain. after these criteria have been set, and the parsing has been carried out, egn can effectively generate outfiles for two kinds of networks: gene and genome networks. this step of network reconstruction also allows the user the option of setting additional selection criteria concerning the edges that will be retained. by default, edges corresponding to hits with a maximal blast e-value of 1e- 20% identity, and longer than 20% of the smallest similar sequence will feature in gene networks, and be used to reconstruct clusters of similar sequences. if two samples/genomes contain sequences belonging to the same cluster, egn will produce an edge in the genome network between these samples/genomes. in this last construction step, egn not only generates network outfiles in cytoscape and/or gephi format, it also optimizes the content of these outfiles. typically, gene networks may contain hundreds of thousands of subgraphs, corresponding to the cluster of similar sequences, or connected components in graph terms. thus, to ease the visualization of these connected components in cytoscape and gephi, egn distributes them in files called cc_#x_to_#y.txt, organizing these subgraphs by decreasing number of edges, and att_ cc_#x_to_#y.txt, in which all important attributes describing these nodes and edges have been automatically summarized. these attribute files provide useful information for coloring the nodes and edges in the visualization network tools. finally, egn also provides some statistics about the sequences, and the connected components comprising of similar sequences. these text outfiles are created in subdirectories with explicit names, describing the exact parameters retained to perform the network reconstruction. in particular, the gpcompo.txt outfile indicates for each cluster of similar sequences how many representative sequences it contains, and from which sample/genome these sequences originate. the gpstat.txt outfile provides further information about genetic divergence of these sequences: how much they cluster with one another in the network, the mean and standard deviation hit % identity between sequences in the cluster, the mean and standard deviation of % identity between the hit and the shortest sequence considered in each pairwise comparison, and the mean and standard deviation of the e-value between sequences of the cluster. as the user is guided along the various steps of the intuitive egn menus, this wizard provides a tool with which users will be able to analyze their data under the framework of similarity networks. egn automates the analysis of a significant data type egn produces a useful network-based type of data for evolutionary analyses. this data type is different from the usual phylogenetic trees, for at least two reasons. first, while trees are always acyclic graphs, networks are generally cyclic graphs. second, while phylogenetic trees usually aim at inferring the relationships between homologous sequences and their hypothetical ancestors, sequence similarity networks instead display significant resemblances between any sequences or any entities, in a topologically less constrained, and in practice much more inclusive, framework. the usual data type used in phylogenetics is a tree, while it is a connected component in a sequence similarity network. in these latter networks, no explicit orthology relationship needs to be assumed. it is important to establish the distinction between these two data types, because it would be a logical mistake to evaluate connected components using the standards of phylogenetic trees, e.g. as if they were trees, which they are not. sequence similarity networks are founded on a different theoretical background than phylogenetic analyses, which implies that the splits and edge lengths have different meanings than those observed in a phylogenetic tree or network. in fact, connected components are better understood by reference to “family resemblances”. just like family members in humans present various overlapping and criss-crossing resemblances, i.e. in their build, features, colours of eyes, organized in such ways that it is eventually possible and useful to distinguish different families, connected components in sequence similarity networks group sets of sequences, whose members show significant similarity according to a criterion, so that these sequences cannot be mistaken for other sequences, presenting a different pattern of “family resemblance”. for instance, sequences coding for translation initiation factors sui and for restriction modification type endonucleases fall into distinct connected components in gene networks. in this regard, it is interesting to note that phylogenetic gene trees are a particular display of one very particular instance of ‘family resemblance’. such trees group sequences that are sufficiently similar to be aligned together, because they come from a single last common ancestor. however, sequences can also display significant similarities that do not meet the particular criteria retained in phylogenetics. for instance, sequences resulting from fusion or recombination events will show bona fide similarities introduced by processes of introgressive descent. sequences evolving by vertical descent from a single ancestor can also become too divergent to be aligned with their homologs, and therefore to be included in a gene tree. such distant similarities, and resemblances originating from processes of introgressive descent, however can be analyzed through the definition of connected components, as automated by egn. for example, when the parameters selected for the reconstruction of the gene networks are very stringent, imposing that the hit between sequences covers a high percentage of their length, and that the similar sequences show both a high e-value and % identity, allows to include divergent homologs in connected components. unlike conserved homologs that will be all connected together, divergent homologs will only connect to some of the sequences within the component; i.e. divergent bacterial genes will only bond to some of their bacterial homologs, while less divergent bacterial genes will all be joined to one another. consistently, the data type that is obtained by structuring molecular data in connected components of sequences in sequence similarity networks, contributes in a different way than phylogenetics to extend the scope of evolutionary analyses. evolutionary biologists can take advantage of this additional data type to explore and explain the various causes of their ‘family resemblances’. processes of introgressive descent and vertical descent can be investigated simultaneously through these graphs. phylogenetic relationships however will generally still require the reconstruction of a tree. furthermore, this novel data type also provides an original comparative framework, which must not be confused with the phylogenetic framework. more precisely, egn networks make it possible to compare sequence similarities for sequences of interest in connected components, i.e. by quantifying the distances and topological properties of sequences from two genomes in the network. this comparison cannot be equated with the phylogenetic resolution required to identify where a particular sequence should be placed in a gene tree, but it can be useful in other situations. among the most recent examples, a comparative analysis of the behavior of sequences in gene networks was carried out by bhattacharya et al. to investigate the modular genomic structure of a novel marine cyanophage in a protist single cell metagenome assembly. sequences from these novel mosaic viruses presented a pattern of connection that was typical of that presented by sequences from mosaic cyanophages in the gene network. the use of a network proved particularly well-suited, offering much more detail concerning the complex evolution of such mosaic objects than allowed by the proposition of a single branching point in a viral tree for the novel virus. one main interest of network studies is therefore that they can employ an additional, very inclusive, relevant - although non-phylogenetic - data structure for evolutionary analyses. application to real data we used egn to illustrate how its various options areuseful for devising and testing evolutionary hypotheses, while taking into account a large amount of data structured according to this data type. we tested whether plasmids were always used as genetic couriers, moving dna from one lineage to another in a dataset of protein sequences. we first used egn to reconstruct a genome network of cellular organisms, plasmids and viral genomes, harboring either cellular chromosomes or genomes of mobile genetic elements at its nodes, connected when they shared sequences from the same similarity cluster, as in halary et al.. in the genome network, some plasmids displayed markedly distinct behaviors and patterns of connections, identifying two extreme sorts of plasmids. on the one hand, many plasmids had a broad range of connections with a diversity of distantly related genetic partners. these plasmids act as genetic couriers, contributing to exchanges of dna material. on the other hand, some other plasmids were very isolated in the network, showing a very limited and sometimes even no genetic partnerships outside a limited gene sharing with the plasmids or the chromosomes of their host lineage. plasmids of this second type typically use a closed dna pool, and seem to rarely transit between different hosts cells and lineages, and even to rarely exchange genetic material with the chromosome of their hosts. rather than being mobile vessels of genetic exchange, our network suggests that these non-promiscuous plasmids may fulfill a functional role of evolutionary significance distinct from that of the plasmids that are key players for lateral gene transfer. the best examples are offered by the plasmids of the bacterial genus borrelia, which display a very low conductance. indeed, the corresponding/respective nodes are extremely isolated in the genome network, and are linked to it just by edges with nodes of the borrelia chromosomes. borrelia’s plasmids do not share a single gene family with any other plasmids outside these hosts, and only harbor six genes, that are also found on borrelia’s main chromosome, consistently with the literature. in agreement with tamminen et al., our genome network identifies that the flow of dna material in and out of borrelia plasmids is lower than for many other plasmids. this remarkable genetic isolation may be explained by biological considerations, prompted by the detection of this network structure. borrelia is an obligate pathogen. this lifestyle entails that these bacteria have fewer opportunities to meet a diversity of genetic partners than the majority of the bacteria growing in biofilms. borrelia genetic diversity must come from within the lineage, rather than from adaptative gene transfer from other microbes, even though borrelia’s plasmids are able to transfer. moreover, borrelia’s lifestyle imposes a strong selective pressure on these parasitic cells that must constantly evolve to escape their host immune system. plasmids within borrelia play a role in this evasion process, and we hypothesize that it is because they provide a genetic compartmentalization inside the cells that allows borrelia to partition dna on two distinct kinds of molecules with distinct evolutionary regimes. most of the genes are located on a slow evolving linear chromosome, heavily constrained in its structure, while other genes are stored on the more flexible, fast evolving, and heavily recombining plasmids. we propose that this partition helps borrelia cells to survive in a hostile environment. the chromosomes are highly streamlined and optimized to support borrelia’s parasitic life, while the plasmids would be the locus of substantial rearrangements, recombination and gene conversion, producing necessary variations on genes coding for outer surface proteins, genes that repress the cytolitic activity of host’s serum, and genes coding for antigenic variation to escape borrelia’s host immune system. to further this hypothesis - that some plasmids act as compartments of dna material and intracellular organs of genetic innovation rather than vectors of mobile dna - we used the hit coverage option of egn’s gene network reconstruction, that we set to > 90%. this option allowed us to distinguish two types of edges in sequences network. we used egn to detect and quantify “full homology” edge links between borrelia’s sequences. sequences connected by “full homology” edges have probably progressively diverged by the combined effects of small mutations, natural selection and drift, because their sequences greatly overlap, and can be aligned all along their length. by contrast, when sequences are not only evolving in a tree-like fashion, i.e. when segments of divergent sequences fuse to form a single a gene, or when segments within genes recombine through illegitimate recombination, sequences are connected by edges that are not necessarily “full homology” edges. these sequences do not come entirely from a single ancestral gene copy, but various segments of these sequences have a diversity of sources. such sequences, produced by more complex processes than vertical descent alone, do not neatly align all along their sequences, but are at best only connected through local regions of similarity. such similar segments, as opposed to similarity overall their dna, are also detected in egn analyses: they constitute a second type of edge in gene networks. interestingly, we observed that connected components of borrelia’s chromosomes were largely connected by “full homology” edges, but that connected components on borrelia’s plasmids were largely connected by “partly similar edges”, and therefore seemed to be subjected to more complex evolutionary processes. these processes result in a large amount of genetic diversity in the plasmids. this result, based on a gene network, strengthens our hypothesis that a structural partition of dna within borrelia’s cells is coupled with a “partition” of the processes affecting this dna, in that case contributing to the recruitment of borrelia’s plasmids as “organs of genetic innovation”. in other words, borrelia’s plasmids and their genes can be seen as private goods of the borrelia lineage: they benefit to this lineage but are not shared with others. of course, quite a few other prokaryotic genera contain plasmids with low conductances, such sodalis, coxiella, and buchnera. we do not wish to elaborate here on whether the lifestyle of these bacteria may explain this relative genetic isolation. sodalis are intra and intercellular symbionts, buchnera are obligate intracellular symbionts and coxiella are obligate intracellular pathogens. however, we want to underscore the fact that sequence similarity network can be a great tool to foster this type of hypothesis.  the use of similarity networks appears as a compelling complement to standard phylogenetic analyses in order to perform comparative analyses of an increasing amount of molecular sequences from genomic and metagenomic projects. several publications have already benefited from this analytical framework. however, such network analyses still require more programming skills than is usually necessary to carry out phylogenetic analyses, for which users can rely on a diversity of user-friendly software. by contrast, few user friendly software programs, running on desktop computers, explicitly designed to reconstruct distinct kinds of similarity networks from nucleic and/or proteic data have yet been made available to the biology community. we introduce egn in the hope that it might constitute a timely opportunity to provide network construction tools to a broader audience. we are confident that software like egn will enhance the exploitation of the evolutionary signal of genomic and metagenomic projects. genomic datasets and analysis parameters we sampled protein sequences from the chromosomes of eubacterial complete genomes, archaebacterial complete genomes, and eukaryotic genomes, covering the diversity of cellular life, as well as from the genomes of two types of mobile genetic elements: protein sequences from all the available plasmids and phages at the time of this analysis from the ncbi. we first used egn to construct a genome network, harboring either cellular chromosomes or genomes of mobile genetic elements at its nodes, connected when they shared sequences belonging to the same cluster of similar sequences, as in halary et al.. to test whether plasmids hosted in a bacterial lineage were connected to genomes in multiple other lineages, we estimated the conductance of their nodes in the genome network. for instance, for plasmids of borrelia, we estimated c as the number of edges connecting borrelia’s nodes to non-borrelia’s nodes / number of edges connecting borrelia’s nodes to any node. we assessed whether the observed value for c was significantly different and lower than the conductance obtained by chance for the same number of nodes in the genome network by shuffling node labels on the same network topology for replicates, which estimates the various conductances expected by chance alone in a network of same size and with the same topology. in order to test whether genes within borrelia chromosomes and plasmids had been affected by different evolutionary processes, we then reconstructed the similarity network of borrelia genes using the same parameters, but setting up the hit coverage condition at > 90%. number of ‘positive’ and ‘negative’ edges linking plasmidic gene to plasmidic gene, plasmidic gene to chromosomal gene, and chromosomal gene to chromosomal gene were quantified. over- or under- representation of such edges was also estimated by shuffling node labels on the same network topology for replicates. availability and requirements •project name:egn •project home page:http://www.evol-net.fr/index.php/fr/downloads •operating system: linux platform and osx •programming language: perl. v.1 •other requirements: blast + versions ≥ v. or blast all versions ≥ v. or blat •license: gnu gpl •any restrictions to use by non-academics: none availability of supporting data the dataset supporting the results of this article is available in the repository of http://www.evol-net.fr/index.php/fr/downloads. the egn script and a user guide are also available at this address and as additional file abbreviations egn: evolutionary gene and genome network; c: conductance. competing interests the authors declare that they have no competing interest. authors’ contributions eb, pl and sh designed the software. sh implemented the software. eb, pl and jmi designed the experiment. eb, pl, jom and sh analyzed the results. eb, jom, and sh wrote the paper. all authors read and approved the final manuscript. supplementary material additional file 1 a zip archive containing the egn script and a user guide. click here for file additional file 2: table s1 an xls table including the summary of the conductance analyses for all plasmids and plasmids of all the prokaryotic genera present in our analyses. click here for file additional file 3: figure s1 a tif file with the graphical representation of the conductance analyses for all plasmids and plasmids of all the genera present in our analyses. y-axis corresponds to the conductance value of these plasmids. each dot corresponds to a class of plasmids. dots colored in red, black, green and purple correspond to plasmids hosted in borrelia, sodalis, coxiella and buchnera, respectively. click here for file acknowledgments sh was supported by the genome canada/genome quebec research grant genorem granted to f. lang and among other co-applicants, m. st-arnaud and m. hijri. eb, pl and jom were supported by a phc ulysses grant.
increasingly, similarity networks are being used for evolutionary analyses of molecular datasets. in order to ease the use of similarity networks in the community of evolutionary biologists, we introduce a software program, egn, that runs under linux or macosx. these networks are very useful, in particular for the analysis of gene sharing, lateral gene transfer and for the detection of distant homologs. egn also implements statistics describing genetic diversity in these samples, for various user-defined thresholds of similarities. rather than being genetic couriers involved in lateral gene transfer, borrelia’s plasmids and their genes act as private genetic goods, that contribute to the creation of genetic diversity within their parasitic hosts. egn automates the reconstruction of gene and genome networks from nucleic and proteic sequences. in the interest of studying the complexity of evolutionary processes affecting microbial evolution, we applied egn to a dataset of proteic sequences from the three domains of life and from mobile elements.
 increasingly, similarity networks are being used for evolutionary analyses of molecular datasets. these networks are very useful, in particular for the analysis of gene sharing, lateral gene transfer and for the detection of distant homologs. currently, such analyses require some computer programming skills due to the limited availability of user-friendly freely distributed software. consequently, although appealing, the construction and analyses of these networks remain less familiar to biologists than do phylogenetic approaches.  in order to ease the use of similarity networks in the community of evolutionary biologists, we introduce a software program, egn, that runs under linux or macosx. egn automates the reconstruction of gene and genome networks from nucleic and proteic sequences. egn also implements statistics describing genetic diversity in these samples, for various user-defined thresholds of similarities. in the interest of studying the complexity of evolutionary processes affecting microbial evolution, we applied egn to a dataset of proteic sequences from the three domains of life and from mobile elements. we observed that, in borrelia, plasmids play a different role than in most other eubacteria. rather than being genetic couriers involved in lateral gene transfer, borrelia’s plasmids and their genes act as private genetic goods, that contribute to the creation of genetic diversity within their parasitic hosts.  egn can be used for constructing, analyzing, and mining molecular datasets in evolutionary studies. the program can help increase our knowledge of the processes through which genes from distinct sources and/or from multiple genomes co-evolve in lineages of cellular organisms. similarity networkevolutionborreliaplasmidgenomicsgraphpathogenlateral gene transferintrogressive descent 