Genetic sequences evolve through multiple processes beyond point mutations. In particular, the remodeling of genes by shuffling of genetic fragments, fusion, and fission, as well as de novo gene emergence, contributes to the creation, and diversification of gene families ([@msx283-B17]; [@msx283-B23]; [@msx283-B15]; [@msx283-B20]; [@msx283-B32]; [@msx283-B26]; [@msx283-B4]; [@msx283-B21]; [@msx283-B27]; [@msx283-B10]; [@msx283-B18]; [@msx283-B22]). Therefore, genetic sequences show similarity with one another for diverse reasons, that is, common ancestry producing homology, and/or partial sharing of component fragments ([@msx283-B31]; [@msx283-B11]). These processes must be disentangled to understand the rules and constraints on genes evolution. Although gene remodeling has been especially studied in eukaryotes ([@msx283-B17]; [@msx283-B25]; [@msx283-B6]; [@msx283-B24]; [@msx283-B22]) and in cultured prokaryotes ([@msx283-B7]; [@msx283-B19]; [@msx283-B8], [@msx283-B9]; [@msx283-B30]; [@msx283-B14]), analyses of large molecular data sets remain a computational bottleneck ([@msx283-B28]; [@msx283-B14]). For instance, a large scale investigation of how remodeled genes evolved in prokaryotes would require comparing millions of coding sequences from the thousands of complete genomes available, but previous detection methods are unable to handle such large data sets.

In this article, we present CompositeSearch, a memory-efficient, fast, and scalable method to detect composite gene families in large data sets, typically in the range of several million sequences. Composite genes are the result of the fusion of partial or complete nonhomologous DNA fragments, called components, or as a result of fission from a larger gene into dissociated persistent fragment ([fig. 1*A*](#msx283-F1){ref-type="fig"}). CompositeSearch generalizes the use of similarity networks to detect composite and component gene families with a greater recall, accuracy, and precision than recent programs, FusedTriplets and MosaicFinder ([@msx283-B14]). Moreover, it provides user-friendly quality descriptions regarding the distribution and primary sequence conservation of these gene families allowing critical biological analyses of these data, and it is used as an input for the reconstruction of multirooted gene networks ([@msx283-B11]).

![(*A*) Top: Example of a composite gene. Gene family 3 evolved from a composite of families 1 and 2**.** Bottom: Sequences from family 3 partially align with sequences from families 1 and 2. (*B*) Similarity network of a composite gene family (red) and its component gene families (green and purple). MosaicFinder will detect only the top case where composite genes form a clique, whereas CompositeSearch detects composite gene families forming a clique (top) or quasi-clique (bottom).](msx283f1){#msx283-F1}

New Approach
============

Here, we present CompositeSearch, a memory-efficient, fast, and scalable method, implemented in C ++, which detects composite gene families in large data sets (typically in the range of several million sequences). Composite genes are traditionally defined based on their apparent modularity: they are composed of segments (i.e., components) that have evolved separately in distinct gene families ([@msx283-B25]; [@msx283-B31]; [@msx283-B14]). Under this definition, composite genes can be the result of fusion of components, or involved as progenitors in fission events, after which associations of components are split in separate gene families. CompositeSearch generalizes the use of sequence similarity networks (SSN) to detect composite and component gene families. SSN are undirected graphs, where each node represents a unique sequence and each edge represents the similarity between connected sequences (given similarity criteria, such as a minimum percentage identity, BLAST *E* value; [@msx283-B2] and minimum mutual coverage, i.e., the minimal length covered by the matching parts with respect to the total length of each compared sequence) ([@msx283-B14]; [@msx283-B5]). For a given comparison between two sequences, the alignment, score, and *E* value are not symmetric. They can vary depending on which sequence is used as the query. Thus, the network is first symmetrized by considering the best match of each pairwise comparison. As the greatest asymmetry is found in the better-scoring comparisons (i.e., at a much more stringent threshold than the ones used for network reconstruction; [@msx283-B3]), this procedure does not impact the topology.

This network's structure captures much of the history of gene evolution: not only divergence by point mutations but also recombinations, fusions, and fission events ([@msx283-B1]; [@msx283-B14]). Typically, gene families form subgraphs with high connectivity, in which connected sequences display significant BLAST *E* values ≤ 1E^−5^, mutual covers ≥ 80%, and %ID  ≥ 30%. By contrast, superfamilies ([@msx283-B3]) and composite gene families ([@msx283-B31]; [@msx283-B14], [@msx283-B13]; [@msx283-B11]; [@msx283-B22]) introduce more complex informative patterns in SSNs.

Using these graphs to identify composite genes and gene families, CompositeSearch shows a greater recall, accuracy, and precision than recent programs FusedTriplets (FT) and MosaicFinder (MF). In short, these two programs are helpful but limited in scope. FT cannot handle large data sets and does not define composite gene families. MF is also unable to analyze large data sets (due to memory and speed limitations). Although it identifies composite and component gene families, MF is only meant to find highly conserved composite gene families that form minimal clique separators in sequence similarity network. The "clique" condition implies that MF misses divergent (e.g., ancient or fast evolving) composite gene families (whose members do not necessarily connect all together in sequence similarity networks) ([fig. 1*B*](#msx283-F1){ref-type="fig"}). The "separator" condition implies that composite genes will remain undetected for data sets with highly remodeled genes by MF. Indeed, the repeated use of gene components introduces cyclic paths in sequence similarity networks, which turns composite families into local, but not global separators. Beyond its larger scope and better performance, CompositeSearch can also provide quality descriptions (absent from MF and FT) regarding the size and primary sequence conservation of composite and component gene families, easing critical biological analyses of these data. CompositeSearch is available at <https://github.com/TeamAIRE/CompositeSearch>, last accessed November 2, 2017. For a detailed description of the algorithm, see [supplementary Materials and Methods](#sup1){ref-type="supplementary-material"}, [Supplementary Material](#sup1){ref-type="supplementary-material"} online.

Results
=======

Benchmark on Simulated Data
---------------------------

We tested and compared CompositeSearch with FT and MF ([@msx283-B14]) on 100 replicates of simulated data, covering a large range of parameters and simulating 2-components and 3-components composites ([supplementary fig. S4](#sup1){ref-type="supplementary-material"} and Materials and Methods, [Supplementary Material](#sup1){ref-type="supplementary-material"} online). We explored the effect of gene family divergence and multiple component reassortments on composite gene detection under the hypothesis that the more divergent gene families are, the harder they are to detect. The sensitivity and specificity of each program were summarized in [supplementary table S1](#sup1){ref-type="supplementary-material"}, [Supplementary Material](#sup1){ref-type="supplementary-material"} online. In terms of detection of composite genes, CompositeSearch performs as well as FT, with identical True Positive Rate (TPR) and False Positive Rate (FPR), but, unlike FT, CompositeSearch returns composite gene families. However, CompositeSearch has higher TPR than MF, especially for divergent composite sequences, with a similar 1% FPR. Therefore, CompositeSearch will find additional composite genes with respect to MF, thanks to the detection of composite genes forming quasi-cliques. As CompositeSearch is able to detect the number of components for each composite, we created a more detailed table ([supplementary table S2](#sup1){ref-type="supplementary-material"}, [Supplementary Material](#sup1){ref-type="supplementary-material"} online) showing the sensitivity and specificity of CompositeSearch to detect the exact number of components.

Benchmark on Real Data
----------------------

We also used a data set of 204,894 viral proteins from ([@msx283-B13]) to benchmark our software against real data. CompositeSearch detected 21,623 composite genes clustered in 5,532 families, vastly outperforming MF (5,845 composites in 1,718 families). FT found slightly more composites (23,305), but did not return any families. This slight increase in the number of composites detected by FT was mainly due to BLAST overextending matches on real data, thus producing false positives.

Performances
------------

Because its algorithm uses a dichotomous search to browse the network and because it is multithreaded, CompositeSearch outperforms both FT and MF in terms of speed and memory use, when these parameters are contrasted on a Linux machine with Intel Xeon CPU E5-2630 v2 2.60-GHz processors and 256 GB RAM, even on one CPU. This is especially noticeable for large metagenomic data sets ([table 1](#msx283-T1){ref-type="table"}). By contrast, construction the SSN composite genes and composite gene families detection runs in a few second to few minutes depending on the network's size. Table 1CompositeSearch, FusedTriplets, and MosaicFinder Performances Comparison.DataNodesEdgesSoftware\#CPURuntimeMemory (GB)1338,86871,946,457MosaicFinder1548 h 27 min82FusedTriplets170 h 47 min18CompositeSearch100 h 12 min2.5CompositeSearch1000 h 06 min2.523,166,706282,789,792MosaicFinder1------FusedTriplets1------CompositeSearch1008 h 48 min32[^2]

Discussion
==========

CompositeSearch is an efficient tool that detects composite genes and composite gene families. It allows investigating the process of gene remodeling in large data sets, for example metagenomes and/or thousands of complete genomes. Although CompositeSearch is faster than currently available software, like FusedTriplets and MosaicFinder, it still can be improved. We observed that in CompositeSearch, the most time consuming step is the detection of gene families, using a DFS algorithm than runs on a single CPU. Parallelized algorithms that detect connected components are available ([@msx283-B16]; [@msx283-B12]), but they usually require high computational resources. As CompositeSearch was developed with maximum portability in mind, these algorithms are not implemented yet could be in a future version.

Supplementary Material
======================

[Supplementary data](#sup1){ref-type="supplementary-material"} are available at *Molecular Biology and Evolution* online.

Supplementary Material
======================

###### 

Click here for additional data file.

We thank Raphaël Méheust for his helpful and constructive discussion during the development of CompositeSearch. We also thank our beta testers James O. McInerney, Mary J. O'Connell, Raymond Moran, and Rob Leigh. J.S.P. and E.B. are funded by the European Research Council (FP7/2017-2013 Grant Agreement \#615274).

[^1]: **Associate editor:** Tal Pupko

[^2]: [Note]{.smallcaps}.---We compared the performance of CompositeSearch, FusedTriplets, and MosaicFinder on the same Linux machine with Intel Xeon CPU E5-2630 v2 2.60-GHz processors and 256 GB RAM. The data (1) are an SSN from plasmids complete genomes (NCBI December 2014) and (2) HCH metagenomes ([@msx283-B29]). CompositeSearch outperform FusedTriplets and MosaicFinder even with one CPU as shown for data (1). On the data (2), FusedTriplets and MosaicFinder stop by running out of memory, which was not the case for CompositeSearch.
