dataesr/scientific-paragraphs-categorization huggingface dataset:
Background: An important problem in computational biology is the automatic detection of protein families (groups of homologous sequences). Clustering sequences into families is at the heart of most comparative studies dealing with protein evolution, structure, and function. Many methods have been developed for this task, and they perform reasonably well (over 0. 88 of F-measure) when grouping proteins with high sequence identity. However, for highly diverged proteins the performance of these methods can be much lower, mainly because a common evolutionary origin is not deduced directly from sequence similarity. To the best of our knowledge, a systematic evaluation of clustering methods over distant homologous proteins is still lacking. Results: We performed a comparative assessment of four clustering algorithms: Markov Clustering (MCL), Transitive Clustering (TransClust), Spectral Clustering of Protein Sequences (SCPS), and High-Fidelity clustering of protein sequences (HiFix), considering several datasets with different levels of sequence similarity.
Conclusions: The results reveal low clustering performance for the highly divergent datasets when the standard measure was used. However, the novel measure based on profile-profile comparisons substantially improved the performance of the four methods, especially when very low sequence identity datasets were evaluated. We also performed a parameter optimization step to determine the best configuration for each clustering method. We found that TransClust clearly outperformed the other methods for most datasets. This work also provides guidelines for the practical application of clustering sequence methods aimed at detecting accurately groups of related protein sequences.
Background Protein family detection is of fundamental importance in structural and functional genomics. Well-characterized protein families can contribute significantly to the delineation of functional diversity of homologous proteins, providing valuable evolutionary insights. In general, a out an all-against-all sequence-sequence similarity search using the BLAST program  [1]  to construct a similarity matrix that is then used by the clustering method to form protein groups. A number of clustering methods have been proposed to detect protein families, but to the best of our knowledge, the performance of most of them have been evaluated only on datasets containing homologous sequences with high identity. For instance, the GOLD dataset  [2] , which contains enzymes that were assigned manually to protein families, is often used to evaluate the performance of clustering methods.
We argue that this benchmark is a relatively less complex case for clustering methods because, in general, members of the same protein family or super-family (groups of related families) are closer to each other than to any other family/super-family, as showed in Figure  1a. Conversely, when we used the SCOP dataset  [3] , a reference database that is used to study distantly related homologous proteins, we found that it was much more difficult to group the homologous proteins with very low sequence identity, as shown in Figure  1b  where the curves are inverted compared with the curves in Figure  1a. This finding shows that members of the same family are so distant that members of different families seem to be closer to each other. Thus, the existing clustering methods yield adequate results for close homologs, but they are likely to fail in identifying distant evolutionary relatedness.
Here, we performed an extensive evaluation of clustering methods on distantly related homologous proteins to determine whether sequence-clustering algorithms can effectively detect remote homologous protein families. We evaluate four state-of-the-art methods: Markov Clustering (MCL)  [4] , Transitive Clustering (TransClust)  [5] , Spectral Clustering of Protein Sequences (SCPS)  [6]  and High-Fidelity clustering of sequences (HiFix)  [7]. These four methods were assessed on various datasets with different level of difficulty (i. e. , the datasets represent different sequence identity percentages) and on two clustering scenarios (i. e. , family and super-family). The parameters were varied for each algorithm to find the best results of the clustering methods. We also determined whether The GOLD dataset (a) is a collection of enzymes that were manually assigned to protein families/super-families.
A-10 (b) is an ASTRAL subset of the SCOP database that contains only sequences with identities less than 10%. For each protein in both datasets, we considered the e-value to the nearest neighbor from its own family/superfamily (intra curves) and the e-value to the nearest neighbor from any other family/superfamily (inter curves). the performance of sequence clustering methods could be improved using a profile-profile search instead of the traditional pairwise sequence search. We used HHblits  [8]  to build a profile for each sequence in the datasets, and we compared pairs of profiles instead of pairs of sequences to provide a similarity measure for each protein pair. Our results show that the traditional similarity measure based on sequence-sequence comparisons, which is often used to feed sequence-clustering methods, is not suitable for detecting remote homologous protein families and super-families.
Results and discussion We assessed the performance of four clustering methods on eight different datasets by considering two clustering scenarios (family and super-family). Two types of similarity matrices were used to evaluate the performance of the algorithms. The first matrix was based on sequence-sequence comparisons obtained from BLAST (Section 'Sequence-sequence comparisons'). The second matrix was based on profile-profile comparisons (performed by HHblits and HHsearch), which was developed and used here for the first time (Section 'Profile-profile comparisons'). To obtain the best possible results for each method, we performed a parameter optimization step to obtain the ideal set of parameters for each clustering algorithm (Section 'Parameter optimization'). Finally, we discuss how the methodology proposed here could be employed to improve the results in practical applications (Section 'Practical usage').
Indeed, all three methods produced the poorest performances on dataset A-10 (the most difficult case). The A-20 and A-30 datasets were also poorly clustered and none of the methods achieved a F-measure greater than 0. 7. In general, TransClust, HiFix, and MCL did not produce performances over 0. 77 on the ASTRAL datasets that contained many remote homologous proteins. On the other hand, the three methods efficiently and accurately clustered proteins in the GOLD dataset, which contains sequences with very high identity. TransClust outperformed the other three algorithms in terms of their general performance over all the datasets tested. Table  1  (bottom) shows the performance of the four clustering methods for super-family detection. Overall, poorer F-measures were obtained for super-family detection compared with the values obtained for family detection.
It is more difficult to group super-family members because, compared with a family, for a super-family group a common evolutionary origin cannot be deduced directly from sequence similarity. Therefore, clustering methods that use sequence-sequence similarity to form groups will not be able to detect distantly related proteins. As a consequence, the four methods produced poor performances over all the ASTRAL subsets; indeed, the F-measures were all less than 0. 66 with TransClust producing the highest value. On the other hand, all four clustering methods achieved performances over 0. 82 with the GOLD dataset, with HiFix producing the best performance.
Profile-profile comparisons To try to improve the performance of the clustering methods on remote homologous datasets, we construct a similarity matrix by extracting e-values from Profile-Profile Comparisons (PPCs), see Section 'Profile-profile comparisons'. Using this new similarity measure, we found that the performance of all four clustering methods improved substantially across all the datasets for both family and super-family detection, see Table  2  and Figure  2a. The biggest improvement was obtained for the less similar dataset (A-10). A remarkable improvement was obtained in the clustering of super-family members (Figure  2b ), showing that super-family detection can be improved using profile-profile comparisons. These results show that family and super-family detection depends crucially on the accuracy of the sequence searches and that search tools that embed evolutionary conserved properties produce better results than tools based on SSCs alone.
It is interesting that the performance of the clustering methods with the GOLD dataset also improved for family and super-family detection. For super-family detection, all four methods properly clustered almost all members in the datasets, achieving F-measures of at least 0. 97. Thus, even on datasets with very high sequence identity,   PPCs provide a more accurate similarity measure than SSCs resulting in better family detection. These improvements were expected, once similarity measures based on PPC can better separate members of a given protein family/super-family (intra distances) from members of other families/super-families (inter distances), as visualized in Figures 3 (families) and 4 (super-families). Clearly, the areas between the PPC curves are larger than the areas between the SSC curves for most of the datasets in Figure  3  and for all datasets in Figure  4.
Parameter optimization We tested 18371 proteins divided into eight datasets with the four clustering algorithms and two different clustering scenarios (family and super-family) by extensive experimentation and parameter variation. A total of 5776 experiments were performed. The parameters used in each clustering algorithm are given in parenthesis in Tables  3  and 4  and the range of parameters used is given in Table  5. Although there was a set of parameters for each clustering algorithm, most of time only one of the parameters drastically affected the results and this parameter was essentially related to the number of clusters obtained. For some of the algorithms, this special parameter was the initial threshold for sequence similarity that was used to group two proteins into the same cluster.
1 to 6. 0 in increments of 0. 1, which is the maximum interval suggested in the program's help file. I affects the granularity of the clusters that are produced; that is, I is related to the number of clusters obtained and cannot be determined directly by the frequency distribution of the e-values as was done for TransClust. To overcome this problem, a common approach is to use a validation subset (a dataset for which the correct family/super-family clusters are   known) and to determine the I that produces the best performance. For SCPS, the maximum number of clusters (c parameter) were varied from 90% to 120% (in increments of 5%) of the real number of families/super-families in the tested datasets. A natural choice for c would be the size of the dataset (number of proteins), but this would be time-consuming and may result in one protein per cluster, which is rarely a realistic clustering solution.
Protein function prediction Understanding protein functions is essential for comprehending the complex cellular machinery of living organisms. Functional characterization of newly discovered proteins is often performed by scanning databases for proteins that share sequence similarities with the new protein. Sequence similarity may suggest a common evolutionary origin between known function proteins and newly discovered ones. Thus, the new protein is annotated by transferring the annotation from closely related proteins. Clustering methods have also been used for protein function prediction, because proteins in the same cluster are likely to share the same function  [9, 10]. As input, clustering methods require a list of possible homologous sequences that can be obtained by comparing the target sequence to a database of annotated proteins, as described above.
Construction of protein family databases Protein family databases are repositories of protein sequences organized according to one of the following criteria: their evolutionary relationships, their structural properties (e. g. , structural classes, folds, 3D-motifs, and topology), or their sequence patterns (functional domains and motifs). Most protein family databases employ automatic clustering algorithms to group homologous proteins into families that are then analyzed manually by curators. The PPC methodology proposed here could be used to improve the quality of clusters detected automatically, thereby reducing the laborious work of experts.
Conclusion We measured the performance of four graph-based algorithms in clustering homologous protein sequences. In our analysis, we used several datasets with different degrees of sequence similarity to evaluate the capability of clustering methods in detecting remote homologous proteins, where homology relationships may not be apparent from sequence similarities alone. To group proteins, clustering methods need to establish a similarity measure to evaluate the closeness of a protein pair. This measure is directly related to quality and to the number of clusters produced by each algorithm. Generally, the similarity measure is derived from pairwise sequence alignments obtained from an all-against-all comparison with BLAST. However, pairwise sequence alignments do not produce an appropriate similarity measure for related proteins with very low sequence identity, as showed in Table  1.
To circumvent these limitations, we have proposed a new similarity measure based on PPCs using HHblits and HHsearch (see Section 'Profile-profile comparisons'). We carried out extensive experiments using the standard SSC and the new PPC measures to evaluate the performance of clustering methods. Our experimental results show that the PPCs outperform the SSCs in measuring the similarity of highly divergent proteins. The new PPC measure improved the performance of all four clustering methods over all the datasets tested, as reported in Table  2. The improvements shown in Figure  2  were expected because it is well known that profiles capture evolutionary conserved properties in a set of related proteins that cannot be easily detected by pairwise sequence alignments. For large datasets, profile construction can be a time-consuming task; however, this task can be run in parallel executions.
Clustering algorithms have parameters that can be tuned to produce better results. We performed a parameter optimization step to determine the best configuration for each clustering method. We observed that the choice of these parameters is often completely empirical and the default parameters (sometimes suggested by the software packages) do not always produce the best results. As discussed above, these parameters can be determined by intrinsic information in the dataset (when it can be computed) or by a cross validation approach  [12]. This work provides guidelines for the practical application of clustering sequence methods aimed at detecting homology relationships accurately. The resulting clusters constitute a useful information source for predicting the function and evolution of proteins.
Datasets Two distinct datasets were used in this study. One dataset was based on subsets from SCOP (Structural Classification of Proteins)  [3] , and was used to measure the performance of sequence clustering algorithms on distantly related homologous proteins. SCOP classifies all protein domains of known structure into a hierarchy with four levels: class, fold, super-family, and family. In this work, we used version 1. 75 and considered the family and super-family levels. A SCOP family groups proteins with a clear evolutionary relationship, while a super-family groups families for which a common evolutionary origin was not obvious from sequence identity but are deemed probable based on an analysis of structure and from functional features. Because the SCOP dataset contains many redundant domains, we used the ASTRAL repository  [14]  to select non-redundant subsets.
We extracted seven subsets of proteins from ASTRAL over a range of sequence identity thresholds and named them Astral-95 (A-95), Astral-90 (A-90), Astral-70 (A-70), Astral-50 (A-50), Astral-30 (A-30), Astral-20 (A-20), and Astral-10 (A-10), where A-x indicates that any pair of sequences in that subset shared at most x% sequence identity. We removed all singleton family/super-family from each subset so that there are no families or super-families with only one protein sequence. This step was necessary because singletons constitute an important percentage of the original ASTRAL dataset and may have subverted the results. For instance, 75% of families in A-10 were singletons; thus, if a clustering method created one cluster for each protein in A-10, it would have correctly group 75% of the dataset.
Our aim was to evaluate the performance of clustering algorithms in grouping at least two remote homologous proteins into the same cluster. The other dataset, GOLD  [2] , is a standard collection of homologous proteins and has been widely used to evaluate the performance of sequence clustering methods. The GOLD dataset contains 866 enzymes that were assigned manually to 91 protein families and five superfamilies. We included this dataset to show that sequenceclustering methods perform over 0. 88 of F-measure when the homologous proteins in the dataset have high identity. Table  6  lists the number of sequences, families, and super-families in the ASTRAL subsets and GOLD dataset. Note that we did not remove singletons from the GOLD dataset because we wished to reproduce experiments that have been reported previously  [5, 7, 15].
Similarity measures A crucial step in the application of clustering algorithms is how to measure the similarity between a pair of proteins. This measure is used by clustering algorithms to form clusters of homologous proteins. Most methods perform an all-against-all BLAST comparison of a given dataset and then use e-values or percentage of sequence identity as a distance measure between two sequences. However, more sensitive sequence comparison methods that uses multiple sequence alignments represented as Hidden Markov Models or sequence profiles have been proposed  [16]. In this study, we investigated whether similarity measures based on PPCs yielded better results than the standard SSC similarity measure.
Sequence-sequence comparisons BLAST is a program that is widely used to compare protein sequences. It performs pairwise sequence alignments using a heuristic approach that locates short matches between a pair of sequences rather than comparing whole sequences. The heuristic algorithm makes BLAST much faster than other methods that calculate optimal alignments. For this reason, it is commonly used in clustering sequence methods to provide sequence similarities. Most of the currently available sequence clustering methods use e-values as the similarity measure rather than sequence identities. BLAST outputs can display several hits for a pair of sequences and their e-values can differ. Clustering algorithms that use e-values make some assumptions: 1) uniqueness (only one similarity value for a given protein pair), and 2) symmetry (the similarity between two proteins i and j is equal to the similarity between j and i).
Thus, e-values must be pre-processed before being used as similarity measures. Typically, the highest, lowest, or average value of hits for an aligned protein pair are used  [5]. For each dataset, we conducted an all-against-all BLAST search with a permissive e-value threshold of 100 and with all other parameters as default values  [17]. The BLAST output was then used as input for each clustering algorithm that transformed e-values into unique and symmetric similarity measures before using them to form groups. Details about e-values transformation can be found in the original papers (see Section 'Clustering approaches').
Here, we investigated whether similarity measures based on PPCs could yield better protein clusters than the standard SSCs. We used two tools from the HHsuite package  [20] : HHblits  [8]  and HHsearch  [16]. HHblits is an iterative method that builds a profile for a query sequence from a special profile database (built from the UniProt and NCBI nr databases and provided in the HHsuite package), and HHsearch compares profiles (it takes a profile and searches for similar ones in a profile library). First, we used HHblits (with default parameters) to construct a profile for each sequence in our datasets. Then, we conducted an all-against-all profile-profile search using HHsearch (with default parameters), which provided e-values similar to what BLAST does. Because most sequence clustering algorithms cannot interpret HHsearch outputs, we converted them to match the output format used by BLAST.
Comparing the performance of the four sequence clustering methods Various quality measures have been proposed to evaluate the quality of a given clustering method. To the best of our knowledge, no quality measure optimally captures the notion of a natural cluster; i. e. , a cluster that reflects a real group of common elements. Moreover, it is a well known that for each quality measure there is an example where it fails as a measure  [28]. Also, no polynomialtime algorithm for the optimization of these measures is currently available. However, each quality measure captures at least one aspect of a natural cluster; therefore, these measures can be used as criteria for distinguishing efficient clustering methods from others that are less efficient. Here, we used the F-measure to evaluate the performance of sequence clustering methods on the GOLD and ASTRAL datasets.
The F-measure integrates both precision and recall and has been used widely to measure the correctness of clustering algorithms  [6, 7, 21]. We first define precision and recall and then we describe how the F-measure is computed. Let n be the total number of proteins in a given dataset, n f the number of proteins within the f th family or superfamily, n g the number of proteins placed in the gth cluster, and n fg the number of proteins shared by both the f th family/super-family and the gth cluster. The precision of cluster g with respect to f th family/super-family is then defined as p fg = n fg /n g. Precision measures the fraction of proteins in cluster g that are present in the f th family/super-family. In addition, the recall measures the fraction of proteins of the f th family/super-family detected by the gth cluster.
The human genome is the only other primate genome curated to this degree of detail for chromosomal accuracy. To annotate the vervet genome for gene content, we utilized the collective methods deployed at NCBI (http://www. ncbi. nlm. nih. gov/genome/annotation_euk/process/), taking as input RNA sequencing (RNA-seq) data from total RNA and small RNA cDNA libraries derived from a diverse set of tissue types, as well as human RefSeq and GenBank transcripts and primate proteins. The currently identified set of protein coding genes (21,128) and noncoding genes (8520) is comparable in number to that observed for other primate genomes (http://www. ncbi. nlm. nih. gov/genome/ annotation_euk/Chlorocebus_sabaeus/100/; Supplemental Table  S2 ). We aligned 97. 9% of 46,823 human known RefSeq  (Pruitt et al.