Traditional protein annotation methods describe known domains with probabilistic models representing consensus among homologous domain sequences. However, when relevant signals become too weak to be identified by a global consensus, attempts for annotation fail. Here we address the fundamental question of domain identification for highly divergent proteins. By using high performance computing, we demonstrate that the limits of state-of-the-art annotation methods can be bypassed. We design a new strategy based on the observation that many structural and functional protein constraints are not globally conserved through all species but might be locally conserved in separate clades. We propose a novel exploitation of the large amount of data available: 1. for each known protein domain, several probabilistic clade-centered models are constructed from a large and differentiated panel of homologous sequences, 2. a decision-making protocol combines outcomes obtained from multiple models, 3. a multi-criteria optimization algorithm finds the most likely protein architecture. The method is evaluated for domain and architecture prediction over several datasets and statistical testing hypotheses. Its performance is compared against HMMScan and HHblits, two widely used search methods based on sequence-profile and profile-profile comparison. Due to their closeness to actual protein sequences, clade-centered models are shown to be more specific and functionally predictive than the broadly used consensus models. Based on them, we improved annotation of Plasmodium falciparum protein sequences on a scale not previously possible. We successfully predict at least one domain for 72% of P. falciparum proteins against 63% achieved previously, corresponding to 30% of improvement over the total number of Pfam domain predictions on the whole genome. The method is applicable to any genome and opens new avenues to tackle evolutionary questions such as the reconstruction of ancient domain duplications, the reconstruction of the history of protein architectures, and the estimation of protein domain age. Website and software: http: //www. lcqb. upmc. fr/CLADE.
The evolutionary history of eukaryotic proteins involves rapid sequence divergence, addition and deletion of protein domains, fusion and fission of genes. This implies that protein repertoires of distantly related species differ greatly (new architectures, that is combinations of domains, are many), while domain repertoires do not (new domains are few) [1]. To account for the great diversity of domain contexts in eukaryotes, an effort was made to categorize coding regions into protein domains and domain families. An important contribution issued by this effort is the Pfam database [2], a large collection of protein families, each represented by multiple sequence alignments (MSAs) and hidden Markov models (HMMs). Pfam also provides protein domain architectures and higher-level groupings of related domains (clans). It highlighted that different architectures give rise to the diversity of proteins found in nature, and that identifying domains of a protein can provide insights into its function. Hence, the complexity of protein annotation can be simplified by focusing on domains, even though the problem of unraveling domain organization (domain architecture) still remains. Proteins sharing more than 30% of sequence identity have a high probability also to share the same fold [3,4]. Thus, since fold and function of a protein have generally an intimate relationship [5], strong sequence similarity is exploited by conventional alignment methods to reconstruct families of functionally related proteins and to accomplish genome annotations. Unfortunately, the complete sequencing of several organisms differing in physiology, habitat and genetics, as Plasmodium falciparum, brought to light the weakness of homology-based approaches to annotation [6–8]. This limitation is challenged even more by the large prokaryotic and eukaryotic metagenomic samples generated today. Radically new homology-based annotation approaches combine information from physico-chemical properties of sequences and conserved amino acid positions in MSAs, together with sophisticated inference methods to extract a general profile (typically a profile HMM, in short pHMMs [9,10]) of a protein domain family and use it as a signature for homology detection [8,11–17]. This profile represents a consensus of signals characterizing a given domain in a multitude of different species. We shall speak of sequence consensus model, in short SCM. Conversely, other approaches [18–20] associate to each protein domain family several different profiles, built from a sample of diversified homologous sequences. The resulting set of profiles, for all protein domain families, is approximately six or seven times larger than the number of domain families, depending on the method. For instance, SUPERFAMILY [18] constructs 15 438 models for 1 962 SCOP superfamilies [21], and Gene3D [20,22] constructs 16 933 models for 2 738 domain families. Such sets of domain families are rather small compared to the number of distinct Pfam domains (14 831 for Pfam version 27) and one would like to generate and handle multiple models representing all Pfam domains. The co-occurrence of domains within a protein was also shown to be very powerful to accurately identify domains in divergent protein sequences [23] and especially for the P. falciparum genome [24–27]. Nevertheless, the 37% of P. falciparum proteins still completely lack domain annotation and one of the main reasons is that relevant signals in sequences might become too weak to be identified by consensus if sequence divergence is too important or if the pool of sequences is biased (too small or overrepresented by certain clades). Another reason is that proteins without predicted domains might belong to novel families completely missing in Pfam and other databases. Based on the observation that structural and functional constraints might not be globally conserved through all species, we propose a novel pipeline, called CLADE (CLoser sequences for Annotations Directed by Evolution), that identifies domains in proteins by using all known Pfam domains and the large quantity of available genomic data spanning through a large panel of species. The idea is to “decompose” the signal of consensus shared by homologous sequences, collected at the scale of the entire phylogenetic tree, into several consensus signals coming from homologous sequences collected at the scale of species within clades (we shall speak of clade-centered models, in short CCM), and possibly of species that are phylogenetically distant from the genome considered. To do this, we construct several profiles for each Pfam domain, starting from a large and differentiated panel of homologous sequences in a protein domain family, and we use CCMs and SCMs to search for homologous sequences in the genome to annotate. The outcomes of these models are processed and transformed into features used to train a meta-classifier, that is a Support Vector Machine (SVM) [28], that assigns a confidence score to each domain prediction. Based on this score (defined later) and on other properties, such as domain co-occurrence, CLADE finds the most probable architecture for each protein sequence by using DAMA [27], a tool that finds best domain architectures based on multi-objective optimization criteria. By using high performance computing (HPC), CLADE demonstrates that the limits in annotation reached by current methods can be bypassed. In fact, HPC makes it possible to construct and explore a large number of profiles (a few millions) and to search, within them, for the appropriate evolutionary patterns that match the protein sequences to annotate. The idea to explore a large space of profiles and to combine the information coming from them for the prediction of domains within proteins has never been developed before and turned out to be a winning strategy that opens up new hopes and directions for the development of accurate annotation systems. In CLADE, each domain is represented by about three hundred and fifty profiles, a number that is hundreds times larger than what has been previously proposed [18–20]. In total, about 2. 5 million profiles are used to annotate a genome. The information issued by these models is merged and CLADE finds agreement among models, takes into consideration their phylogenetic origin, and combines potential annotations in an accurate reconstruction of domain architectures. Both the profile-based search and the analysis of the resulting annotations require HCP. By using grid computing, we could annotate proteins lying in the twilight zone [29] of the P. falciparum genome, remarkably rich in A and T, and advance on the fundamental question of how to identify domains for proteins that are highly diverged. The P. falciparum protein annotation represents a very difficult case study. More than 44% of open reading frames in this genome remains without any putative annotation [30–32] in PlasmoDB v11. 1 that reports 2 464 proteins with unknown or hypothetical function over 5 542 genes. Our methodology shows a striking improvement over current annotation approaches. No specific property of the P. falciparum genome, besides its localization within the Alveolata clade, is used and the method can be applied to any other genome. We show that because of their closeness to actual protein sequences, CCMs are more specific and more functionally predictive than the broader Pfam family models, based on consensus. The accurate domain annotation reached with CCMs has important implications also for protein evolution studies. In fact, we show that CCMs provide novel information that can be exploited to explore the landscape of protein domain evolution. We shall argue that CCMs can help to trace ancient domain duplications, to reconstruct the history of protein architectures, and to better estimate protein domain age.
To predict domains in protein sequences, CLADE pipeline is organized in three main steps (Fig 1). The input is a set of protein sequences coming from the same genome or from different ones. In the latter case, each sequence is accompanied by its NCBI taxon code. To demonstrate that “multi-source” domain modeling is more appropriate than “mono-source” domain modeling for capturing remote homology, we consider several datasets: 1. three datasets of single-domain sequences constructed from the SCOP database [21] as gold standard, 2. four datasets of randomly generated single-domain sequences satisfying different statistical hypotheses, 3. two datasets of randomly generated multi-domain sequences satisfying different statistical hypotheses. We evaluate the improvement in using an annotation that exploits multi-source domain modeling by comparing the performance of CLADE, that favors the multi-source strategy, to the performance of HMMScan and HHblits, that favor the mono-source one. We recall that HMMScan and HHblits are widely used search methods based on sequence-profile and profile-profile comparison, respectively. We estimate the false discovery rate (FDR) for the three methods. Also, with the SCOP datasets, we show that agreement among models is an important feature present in CLADE, and missing in existing multi-source domain approaches, like SUPERFAMILY. Note that CLADE skips its third step (DAMA) on datasets 1 and 2 because they comprise single-domain sequences. Upheld by CLADE performance on the SCOP benchmark datasets and the FDR tests, we checked whether CLADE could significantly contribute to the identification of domains within the full set of P. falciparum proteins. A large number (2464) of P. falciparum proteins has no identified domain in PlasmoDB and it remains with no domain identification (2068) even after the analysis of existing in silico predictive methods [2,24,26]. We performed a large scale domain prediction and compared CLADE results against annotations obtained with HMMScan. All evaluations reported below were realized with the same CLADE parameters (with an E-value cut-off at 1e-3 and by adopting a specific SVM probability cut-off for each domain). See section “CLADE pipeline, parameter settings and tools used in CLADE” in Methods.
When sequences in a protein domain family are too divergent, signals of homology are easier to trace with CCMs rather than with models based on the consensus of homologous sequences spanning the entire phylogenetic tree (reminiscent ideas were presented in [7,18–20,45]). CLADE shows that, by combining in a unique tool CCMs and consensus models, the predictive power can be highly reinforced. In CLADE, CCMs have been constructed for domains in the Pfam database. In this respect, it is worth to highlight that CCMs are basically different from: 1. Pfam models characterizing Pfam clans [46] whose purpose is to group different families together, possibly new protein families that appear to have arisen from a single evolutionary origin; 2. Pfam models characterizing Pfam domain families (called SCMs in CLADE). Compared to both Pfam family models, CCMs are much closer to actual protein sequences, therefore more specific and more functionally predictive. In fact, one can think of CCMs as forming a new layer of models situated at the very bottom of the Pfam hierarchy and associated to FULL sequences within Pfam domain families. The example reported in Fig 8C and 8E illustrates how CCMs are closer to sequences than Pfam family models. Standard approaches, like Pfam, are limited to consensus within seeds only, and CCMs showed to model evolutionary information differently. Below, we propose several ways to revisit basic evolutionary questions based on CCMs. CCMs can be used to analyze ancient duplications. Modern sequences evolved in the context of full genome and local duplications. The fate of the duplicated domains could be different for several reasons. The most important one is domain organization within architectures, where the accomplishment of different cooperative functional purposes might induce duplicated domains to reach possibly very divergent sequence profiles. CCM can help to model these parallel profiles (created by domain divergence) better than a consensus approach. The example on clathrin domains illustrated in Fig 8 highlights the parallel co-existence in the Metazoa and Amoebozoa clades of CCMs characterized by two distinguished profiles, suggesting that an ancient duplication took place before the Metazoa-Amoebozoa phylogenetic divergence and gave origin to the two kinds of domains observed today in the two clades. The existence of two distinguished copies (fitting the two profiles) of the clathrin domain in the P. falciparum genome, reveals that this duplication is even older and places it before the Metazoa-Amoebozoa-Alveolata divergence. CCMs can be used for large scale explorations of parallel profiles evolution. Multiple CCMs can be used to analyse domain evolution. Whether the actual number of evolutionary pathways for a domain family is relatively small or not remains an open question. The large number of CCMs associated to a domain D characterizes the evolutionary landscape of D, and highlights the viability of different evolutionary processes. The mathematical description of the models, as probabilistic profiles, can be used to explicitly address quantitative questions on the landscape variability. For instance, a measure of how different CCMs are, one from the other, can be developed and used to bring an estimation on the number of distinct evolutionary pathways associated to a domain. Do different domains have a sensibly different number of evolutionary pathways associated to them? Does the distribution of distances between probabilistic profiles of a given domain have a small/large variance? Can we suggest a graph-like relational structure among CCMs and exploit the structure of the graph to infer functional consequences? These questions do not have an answer today but they seem fundamental to the understanding of the evolutionary landscapes we observe. CCMs and their impact on functional annotation. The interest of an accurate genomic mapping of protein domains and protein architectures is multiple. It directly implies the possibility to develop: 1. a more precise functional analysis of domains and architectures within genomes; 2. a comparative analysis of domains and architectures between species within clades. Based on it, pangenomic differences of phylogenetically close microbial species (strains or genomes) can be defined at the domain level, and species variability carefully assessed. By using domains as the building blocks of proteins functional activity, we can assert that the presence of the same domains within different architectures in different species/strains might guarantee a similar functional activity for the organism. In this sense, a relaxed notion of pangenomic variability can be defined, closer in spirit to the functional activity of the species. Similar observations apply to microbial communities, where domains, more than proteins, appear to be useful building blocks for functional annotation; 3. a comparative analysis of domains and architectures between species across distant clades. This could help to improve estimating the age of domains and architectures [47,48]; 4. an accurate identification of gene homology between pairs of genomes. This will directly benefit synteny blocks reconstruction and chromosomal rearrangement analyses; 5. an improved tracing of gene acquisition for bacterial species, where lateral gene transfer is much present. This will imply a more precise reconstruction of reticulate evolution. CCMs and domain architectures identification. The way protein architectures form is an important factor to understand protein evolution. A quantification of the elementary events affecting protein architectures, such as domain (s) insertion/deletion, duplication and exchange, was done [49] but, yet, little is known about the relationships between these elementary events [50] and the molecular mechanisms they originate from. Finer domain mapping (obtained with more precise annotation tools as CLADE) on all proteins of completely sequenced genomes will contribute precise information on the evolution of protein architectures. This means, for instance, a more precise estimation of the rate of insertion, deletion, duplication and exchange of domains within proteins in a given species. In general, it would be interesting: 1. to establish whether the process of generation of an architecture follows constraints or not, 2. to pinpoint such constraints, if they exist, and 3. to verify whether they are species specific or not. This information turns out to be useful in the context of phylogenetic profiles prediction [51]. The role of the Alveolata and other clades in P. falciparum domain annotation. An a posteriori analysis of our predictions highlights that: 1. species in the Alveolata clade are preferably chosen for domain identification (54%), 2. a significant number of identifications (46%) are suggested by species that lie outside the Alveolata clade (that is, far from P. falciparum) and yet providing acceptable E-values for predicted domains (Fig 5C). The first point confirms the strength and importance of considering phylogenetic signals in annotation, and the second point highlights the limitations of the idea of phylogenetic proximity. Besides the observation that many P. falciparum sequences are more easily identifiable by CCMs generated by phylogenetically distant species rather than CCMs coming from Alveolata species, other observations strongly reinforce the interest in looking at different clades while identifying domains: 1. multi-domain proteins identified with CCMs originated in different clades, suggest processes of domain evolution that are independent within each protein (see the three domains identified with models constructed from Alveolata, Amaebozoa and Cryptophyta sequences in Fig 8); 2. new domain families are periodically added to databases like Pfam and annotation becomes gradually more precise as a function of this addition (see the impact of the Pfam27 enrichment on the Chlamydomonas reinhardtii protein architecture compared to Pfam24 in Fig 7A and 7C); 3. CCMs coming from bacterial and archaeal species should allow to check for ancient lateral gene transfer. On CLADE methodological improvements. On the methodological side, the use of agreement among models (handled by SVMs) and of co-occurrence (handled by DAMA) in CLADE improves predictions up to 19. 6% on the P. falciparum sequences (S4 Table), over a score system based on best E-values (CLADEBEv) and this highlights that criteria other than sequence similarity, play a key role in the identification of protein domains. The usage of multiple criteria to reach agreement among models, allows for new predictions and plays an important role in the evaluation of the confidence in a prediction, with improved scores that can help the biologist to annotate sequences. Several ways could be envisaged to improve further our methodological approach. These methodological improvements are general, independent from specific genome characteristics, and guarantee the strategy to be applied to any genome. They will likely be able to address at least a part of the 28% of P. falciparum proteins that are still missing a domain identification and the protein architectures that should be enriched with new domains (among the 2394 single domain proteins, 1214 of them contain a domain that covers less than the half of the protein length, and for these proteins we expect multiple domains to lie together). Some unannotated proteins in P. falciparum likely contain completely novel domains, which are evolutionarily unrelated to domains present in the existing domain family databases. If that is so, CLADE would not find them, at least not until existing databases grow enough to cover more of that domain space. CCMs and computational power. By using HPC, CLADE demonstrates to push the limits in annotation reached by current methods. The first step of CLADE, generating CCMs, is the highly expensive one. It is performed once for all genomes to be annotated. All CCMs used to realize P. falciparum annotation have been constructed in 3. 7 months of computer time by using 250 CPUs (and they are made publicly available). The two subsequent steps (2 and 3), dedicated to genome annotation, are relatively fast. For example, CLADE steps 2 and 3 ran in about 1 hr on 100 CPUs for the entire P. falciparum genome. CLADE domain library is expected to be regularly updated on new domains appearing in databases. This means that only CCMs for new domains need to be constructed and added to the existing library. This step can be realized independently from steps 2 and 3. In years to come, the expected improvements in HPC and in CLADE implementation (with a thoughtful selection of domain models) will render CLADE more computationally accessible.
Our method extends Pfam, an important collection of protein domains, that has been widely used for annotating proteins with unknown function. We use Pfam v27 (Pfam27, downloaded from http: //pfam. sanger. ac. uk), containing 14 831 protein domains. In order to assess the performance of our method, we apply it to the set of all P. falciparum proteins. For this, we use PlasmoDB (http: //PlasmoDB. org), that is the official repository of the P. falciparum proteins used as a reference database by malaria researchers. PlasmoDB v11. 1 contains 5 542 proteins. We used the UniProtKB database [56]: 1. to extract NCBI taxonomy for sequences and the list of known domain architectures. 2. to recover the Pfam domain organization of all proteins in UniProt 15. 6 (Swiss-Prot 57. 6 and SP-TrEMBL 40. 6); we downloaded the dataset ftp: //ftp. ebi. ac. uk/pub/databases/Pfam/releases/Pfam27. 0/swisspfam. gz and used it to analyze co-occurrence in CLADE annotations. (In our tables and figures, “Cooc”, abbreviating “predictions supported by domain co-occurrence”, and “Cooc-CCM”, abbreviating “predictions identified by a CCM and supported by domain co-occurrence”, count architectures whose domain pairs belong to already known architectures.) A reference list of clades has been extracted from NCBI (http: //www. ncbi. nlm. nih. gov/taxonomy) and used for selecting a representative set of sequences in the construction of CCMs. Clades have been specified for Bacteria, Archaea, Viruses and Eukaryotes in S1 Table. We used the SCOP v1. 75 [41] database to compare CLADE, based on the multi-source strategy, with the mono-source strategy of HMMScan [2,33] and HHblits [17]. Also, the SCOP datasets allowed us to compare CLADE with the computational strategy employed in SUPERFAMILY, a system that builds multiple hidden Markov models, for each protein superfamily, to realize sequence search. The SUPERFAMILY sequence search method is built on 1 962 superfamilies (from classes a to g), while CLADE relies on Pfam27 containing 14 831 protein domains. To realize the comparative analyses, we considered SCOP domains whose associated sequences are coming from at least 10 species, and constructed a three testing sets from the ASTRAL95 dataset, containing 255 domain families and 8 633 sequences with at most 95% sequence identity, from ASTRAL30, made of 66 domain families and 1 251 sequences with at most 30% sequence identity, and from ASTRAL10 made of 18 domain families and 306 sequences with at most 10% sequence identity. ASTRAL95, ASTRAL30 and ASTRAL10 are subsets of SCOP [21] and can be downloaded from http: //scop. berkeley. edu/astral/subsets/ver=1. 75. Tests with HHblits required the use of HHdb, a database built from the UniProt and NCBI NR databases, and provided in the HH-suite package [17,42]. HMMScan was run with default parameters and curated inclusion thresholds. The option –cut_ga, for model-specific thresholding (using profile’s GA gathering cutoffs to set all thresholding), was used. HMMScan is included in the HMMer 3. 0 package [33] downloadable at http: //hmmer. janelia. org/software. HHblits was run with default parameters. It is part of the HH-suite package—version 2. 0. 15 [17,42] downloadable at https: //github. com/soedinglab/hh-suite. First, we detail how Pfam methodology works and how we modify it by including additional models, called clade-centered models (CCM). Then, we describe how to combine those models to produce reliable predictions. In the final step, we apply DAMA, an algorithm especially designed to take into account domain co-occurrence, to find the most likely domain architecture. To realize the comparison experiment on the three SCOP datasets, we used a leave-one-out strategy as follows. Given a domain family FD in one of the ASTRAL datasets, we considered the set of n sequences, coming from different species and associated to FD in ASTRAL, to create n test-sets for FD. Each test-set takes n − 1 sequences for training and leaves one sequence out for the test. Then, we tested whether the sequence that was left out could be annotated by a model (or models) constructed without using it, and counted the correct identification of the domain as a true positive (TP), the identification of an erroneous domain as a false positive (FP) and the identification of no domain as a false negative (FN). Note that a domain is “correctly” identified when it belongs to the domain family FD. This same procedure, was implemented for all systems we wanted to compare: HMMScan, HHblits, CLADE, CLADEBEv, CLADE_HHblits, CLADEBEvHHblits. For HMMScan (run with default parameters), each test-set of n − 1 training sequences was first aligned with Clustal W (version 2. 1) [65,66]. Then we used hmmbuild to construct a probabilistic model (a profile) from the alignment. To compare profiles and test sequences we used hmmsearch that employs a composition bias filter by default for eliminating false positives. All tools can be found in the HMMer package—version 3. For HHblits (run with default parameters), we also constructed a profile from each test-set of n − 1 aligned sequences (it is the same alignment as for the HMMScan experiment) but using hhmake. In HHblits experiment, test sequences must be represented by profiles and we used hhblits on HHdb (the HHblits database) to construct them. Profiles were compared with hhsearch [42]. All tools can be found in the HH-suite package—version 2. 0. 15. For CLADE, we considered the profile constructed from the test-set of n − 1 aligned sequences in the HMMScan experiment, and we constructed additional profiles, one for each sequence in the n − 1 set. This was done by using PSI-BLAST and the NR database (see details in Methods). To combine the outputs of the n profiles, we trained a SVM by using as positive set the same n − 1 sequences and as negative set other sequences never used in training nor test. The negative sequences were chosen randomly into the same SCOP dataset of the positive ones, and by avoiding sequences sharing the same SCOP fold. The SVM was trained with an equal number of positive and negative sequences. The third step of CLADE, handling architectures with DAMA, was not used. For CLADEBEv, the version of CLADE that does not include the SVM filter and that considers a score system based on best E-values only, the procedure is the same as for CLADE. The domain-specific cut-offs were learned based on E-values of positive and negative training sets. For CLADE_HHblits, we carried out the same profile construction as for CLADE, but we replaced PSI-BLAST and HMMScan profiles by HHblits models. Like before, we trained a SVM for combining profile outputs. The only difference is that we used profile-profile comparison to generate the meta-features for training the SVM instead of using sequence-profile comparison like in CLADE. The domain specific cut-offs used in CLADE were computed for the HHblits models using the same learning procedure as that employed for CLADE. For CLADEBEvHHblits, the procedure is the same as for CLADE_HHblits, with cut-offs computed for HHblits models that are domain specific but based on E-values (as done for CLADEBEv). Estimating the number of false predictions is an essential step for evaluating the performance of domain identification methods. The basic principle is to estimate the probability that a potential domain has been randomly predicted. We computed the False Discovery Rate (FDR) in two different ways, based on different random models of sequence generation. The key idea is that domain predictions on random sequences arise by chance alone, that predictions on real sequences give us the total number of predictions (true or false), and that their ratio approximate the false discovery rate. For evaluating CLADE (but also HMMScan and DAMA), we run it on real sequences concatenated to its reshuffled ones. The first random model takes a protein and generates 20 different reshuffling of the protein sequence producing new sequences that have the same residue content of the original one and the same length. We call this model “1-mer”. The second random model takes a protein and generates 20 different reshuffling of k-mers in the original sequence, for k = 4. We call this model “4-mer”. The idea behind this last model is that small k-mers within a protein sequence might be more likely to occur than random k-mers, since protein sequences might contain repetitive patterns (for instance, blocks of hydrophobic amino-acids or other compositional biases). Given the original set of protein sequences P and its associated shuffled sequences S, let P + S be the set of concatenated sequences. Note that the set P + S is a set containing 20 times more sequences than P because from each sequence in P, we generated 20 sequences. Then, we computed the number of CLADE domain predictions within the P-portion (saying R) and the number of predictions within the S-portion (saying A) of the P + S sequences, and set the FDR = A/R for the dataset. This calculation is repeated 20 times, with respect to 20 different reshuffling and the FDR for the 1-mer experiment is considered to be the average of the FDRs of the 20 datasets. The same for the 4-mer experiment. The same strategy was used in [26,27] (see section “FDR curves” in Methods). The random reshuffling was realized with the perl function List: : Util: : shuffle (). The performances of CLADE, CLADEBEv (a version without the SVM filter, introduced in the second step of CLADE, and considering a score system based on best E-values only), HMMScan [33] and HHblits [17,42] have been evaluated by using two standard measures: positive predictive value PPV = TP/ (TP + FP) (also called precision) and sensitivity Sen = TP/ (TP + FN) (also known as recall), where TP, FP and FN are true positives, false positives and false negatives, respectively. To give the overall performance for each method, we computed the F-score (also called F-measure) combining PPV and Sen, and defined as F-score = 2 * PPV * Sen/ (PPV + Sen). The F-score can be interpreted as the harmonic mean of PPV and Sen, reaching its best value at 1 and worst score at 0. TP, FP and FN are defined as follows: let s be a protein sequence, A be its domain architecture and T be the evaluated method; a true positive is a domain in A that is correctly predicted by T, a false positive is a domain detected by T that overlaps a different domain in A, and a false negative is a domain in A that is not detected by T. The method T can detect other domains along s that do not overlap domains in A, and we shall refer to them as “additional” domains. CLADE is a pipeline that involves several different tools, and its formal time complexity is hard to establish. The model construction step takes relatively long time due to the time of generation of more than 2 millions (2 389 235) models defining the CLADE library. Namely, each domain construction takes about 30 minutes, and the overall model construction step can be realised in about 3,7 months on 250 CPUs. Once the models are constructed, domain identification is fast (that is, less than an hour on 100 CPUs for about 5000 proteins). CLADE software and the entire library of CCMs used for the applications presented in this article are available at the address: http: //www. lcqb. upmc. fr/CLADE. The CCMs that we generated can be used for annotating any genome and they avoid running the first step of CLADE again. For P. falciparum, CLADE website provides access to a downloadable xls file containing the full list of annotations for the 5542 P. falciparum proteins (AllDomains. xls). The file also contains the annotations obtained with HHblits and HMMScan, and for each hit, it reports its position, the PlasmoDb accession number, the Pfam domain name, the Pfam clan (if any), and the E-value. The list of disagreeing hits between CLADE and HHblits/HMMScan is also given. A HHblits/HMMScan hit disagrees with CLADE for two reasons: 1. either the hit does not overlap CLADE hits, 2. or the hit overlaps (with an overlapping of any size) a CLADE hit of a different domain and a different clan.
Current sequence databases contain hundreds of billions of nucleotides coding for genes and a classification of these sequences is a primary problem in genomics. A reasonable way to organize these sequences is through their predicted domains, but the identification of domains in very divergent sequences, spanning the entire phylogenetic tree of species, is a difficult problem. By generating multiple probabilistic models for a domain, describing the spread of evolutionary patterns in different phylogenetic clades, we can effectively explore domains that are likely to be coded in gene sequences. Through a machine learning approach and optimization techniques, coding for expected evolutionary constraints, we filter the many possibilities of domain identification found for a gene and propose the most likely domain architecture associated to it. The application of this novel approach to the full genome of Plasmodium falciparum, to a dataset of sequences from three SCOP datasets highlights the interest of exploring multiple pathways of domain evolution in the aim of extracting biological information from genomic sequences. Our new computational approach was developed with the hope of providing a novel tier of accurate and precise tools that complement existing tools such as HMMer, HHblits and PSI-BLAST, by exploring in a novel way the large amount of sequence data available. The existence of powerful databases for sequences, domains and architectures help make this hope a reality.
sequencing techniques
taxonomy
parasite groups
plasmodium
parasitology
apicomplexa
phylogenetics
data management
genome analysis
sequence motif analysis
molecular biology techniques
research and analysis methods
sequence analysis
computer and information sciences
genomics
sequence alignment
proteins
biological databases
molecular evolution
evolutionary systematics
molecular biology
biochemistry
sequence databases
database and informatics methods
protein domains
genetics
biology and life sciences
computational biology
evolutionary biology
genomic databases
Improvement in Protein Domain Identification Is Reached by Breaking Consensus, with the Agreement of Many Profiles and Domain Co-occurrence