Abstract
Orthology detection requires more effective scaling algorithms. In this paper, a set of gene pair features based on similarity measures (alignment scores, sequence length, gene membership to conserved regions, and physicochemical profiles) are combined in a supervised pairwise ortholog detection approach to improve effectiveness considering low ortholog ratios in relation to the possible pairwise comparison between two genomes. In this scenario, big data supervised classifiers managing imbalance between ortholog and nonortholog pair classes allow for an effective scaling solution built from two genomes and extended to other genome pairs. The supervised approach was compared with RBH, RSD, and OMA algorithms by using the following yeast genome pairs: Saccharomyces cerevisiae-Kluyveromyces lactis, Saccharomyces cerevisiae-Candida glabrata, and Saccharomyces cerevisiaeSchizosaccharomyces pombe as benchmark datasets. Because of the large amount of imbalanced data, the building and testing of the supervised model were only possible by using big data supervised classifiers managing imbalance. Evaluation metrics taking low ortholog ratios into account were applied. From the effectiveness perspective, MapReduce Random Oversampling combined with Spark SVM outperformed RBH, RSD, and OMA, probably because of the consideration of gene pair features beyond alignment similarities combined with the advances in big data supervised classification.
Introduction
Orthologs are defined as genes in different species that descend by speciation from the same gene in the last common ancestor [1] . Their probable functional equivalence has made them important for genome annotation, phylogenies, and comparative genomics analyses. Ortholog detection (OD) algorithms should distinguish orthologous genes from other types of homologs such as paralogs evolving from a common ancestor through a duplication event. A great deal of unsupervised graph-based [2] [3] [4] [5] [6] [7] [8] , tree-based [9] [10] [11] [12] [13] , and hybrid approaches [14, 15] have been developed to identify orthologs resulting in corresponding repositories for precomputed orthology relationships.
Introduction
Focusing on the graph-based approach, orthogroups are generally built from the comparison of genome pairs by using BLAST searches [16] and then the application of some "nearest neighbor" heuristics such as Best BLAST Hit (Bet) [2] , Bidirectional Best Hit (BBH) [17] , Reciprocal Best Hits (RBH) [18] , Reciprocal Smallest Distance (RSD) [19] , or Best Unambiguous Subset (BUS) [20] to find potential pairwise orthology relationships. Subsequently, algorithms can return pairwise relationships, if they perform pairwise ortholog detection (POD) such as RBH [18] and RSD themselves [19] , and Comprehensive, Automated Project for the Identification of Orthologs from Complete Genome Data (OMA) Pairwise [21] , or they can apply clustering to predict orthogroups from the score of the alignment process.
Introduction
When OD is based only on sequence similarity, it has been limited by evolutionary processes such as recent paralogy events, horizontal gene transfers, gene fusions and fissions, domain recombinations, or different genetic events [22, 23] . In fact, the identification of homologs is a difficult task in the presence of short sequences, those that evolved in a convergent way and the ones that share less than 30% of amino acid identities (twilight zone). Algorithm failures have been particularly shown in benchmark datasets from Saccharomycetes yeast species that underwent whole genome duplications (WGD) and, certainly, present rampant paralogy and differential gene losses [24] .
Introduction
To tackle these shortcomings for OD, some OD solutions may integrate the conserved neighborhood (synteny) of genes in the inference process for related species. Currently, there is a tendency of merging sequence similarity with synteny [20, 25, 26] genome rearrangements [27, 28] , protein interactions [15] , domain architectures [29] , and evolutionary distances [19] . However, so far there is no report that combines such features in a supervised approach to increase POD effectiveness.
Introduction
On the other hand, the integration of different gene or protein information and the massive increase in complete proteomes highly increase the dimensionality of the OD problem and the total number of proteins to be classified. In a thorough paper from the Quest for Orthologs consortium [30] , the authors emphasize the idea that this increase in proteome data brings out the need to work out not only efficient but effective OD algorithms. As they mention, the increase in computational demands in sequence analyses is not easily met by an increase in computational capacities but rather calls for new approaches or algorithmic implementations [30] . In this sense, they summarized some methodological shortcuts implemented by the existing orthology databases to deal with the scaling problem.
Introduction
Considering all these previous remarks about OD, we propose a new supervised approach for pairwise OD (POD) that combines several gene pairwise features (alignmentbased and synteny measures with others derived from the pairwise comparison of the physicochemical properties of amino acids) to address big data problems [30] . Our big data supervised POD approach allows scaling to related species and data imbalance management (low ortholog ratio found in two or more genomes) for an effective OD. The methodology consists of three steps:
Introduction
(i) The calculation of gene pair features to be combined.
Introduction
(ii) The building of the classification model using machine learning algorithms to deal with big data from a pairwise dataset.
Introduction
(iii) The classification of related gene pairs.
Introduction
Since traditional supervised classifiers cannot scale large datasets, the supervised classification for the POD problem should be addressed as a big data classification problem according to [31] [32] [33] and big data solutions should be applied for binary classification in imbalanced data such as the ones presented in [34] based on MapReduce [35] .
Introduction
Finally, we evaluate the application of several big data supervised techniques that manage imbalanced datasets [34, 36] such as cost-sensitive Random Forest (RF-BDCS), Random Oversampling with Random Forest (ROS + RF-BD), and the Apache Spark Support Vector Machines (SVM-BD) [36] combined with MapReduce ROS (ROS + SVM-BD). The effectiveness of the supervised approach is compared to the well-known unsupervised RBH, RSD, and OMA algorithms following an evaluation scheme that takes data imbalance into account. All the algorithms were evaluated on benchmark datasets derived from the following yeast genome pairs: S. cerevisiae and K. lactis, S. cerevisiae and C. glabrata [24] , and S. cerevisiae and S. pombe [37] . The S. cerevisiae and C. glabrata pair is particularly complex for OD since both species had undergone WGD. We found that our supervised approach outperformed traditional methods, mainly when we applied ROS combined with SVM-BD.
Materials and Methods

Gene Pair Features.
Starting from two genome representations being 1 = { 1 , 2 , . . . , } and 2 = { 1 , 2 , . . . , }, with and annotated gene sequences or proteins, respectively, we define gene pair features in Table 1 [40] . First, each amino acid that lies in a matching region without "gaps" between two aligned sequences is replaced by its contact energy [42] . The average Local and global alignment
Gene Pair Features.
max (swalign ( , , , go, ge)) ,
Gene Pair Features.
M-substitution matrix and go, ge-GOP, and GEP
Gene Pair Features.
Membership to locally collinear blocks
Gene Pair Features.
Mauve software parameters Physicochemical profile
Gene Pair Features.
W-moving average window size of each spectrum of this physicochemical feature in the predefined window size , called the moving average for each spectrum, is then calculated. Next, the similarity measure Corr( , ) between the two spectral representations in a matching region is calculated by using the Pearson correlation coefficient and the corresponding significance level. Finally, the significant similarities of the regions without "gaps" are aggregated considering the length len of each region. From our previous studies presented in [43, 44] , we have considered three features for the physicochemical profile with values of 3, 5, and 7.
Big Data Supervised Classification Managing Data Imbal-
ance. Given a set = { ( , )} of gene pair features or attributes as discrete or continuous values of gene pair similarity measure functions, previously specified, we represent a POD decision system DS = ( , ∪ { }), where = {( , )}, ∀ ∈ 1 and ∀ ∈ 2 , is the universe of the gene pairs and ∉ is the binary decision attribute obtained from a curated classification. This decision attribute defines the extreme data imbalance. Given an underlying function : → {0, 1} defined on the set of gene pair instances, the learning process produces a set of learning functions Γ = {̂: → {0, 1} | ⊂ } that approximate from the train set . The goal is to find the best approximation function from Γ having a fitness function or a classification evaluation metric. In this case, the evaluation metric should take into account the low ratio of orthologs to the total number of possible gene pairs in the test set ( -). The big data supervised classification divides into train and test instance to build a learning model̂and to classify the instances by means of a big data supervised algorithm managing the imbalance between classes.
Big Data Supervised Classification Managing Data Imbal-
The proposed big data processing framework is shown in Table 2 . We use the open-source project Hadoop [45] with its highly scalable and fault-tolerant Hadoop Distributed File System (HDFS). We also utilize the scalable Mahout data mining and machine learning library [46] with machine learning algorithms adapted according to the MapReduce scheme as the MapReduce implementation of the RF algorithm [47] . Finally, we use the Apache Spark framework [36] interacting with HDFS, when the implementation of SVM-BD in the scalable MLLib machine learning library [48] is combined with the MapReduce ROS implementation [34] .
Evaluation Scheme Considering Data Imbalance.
For the evaluation of POD algorithms, we compare the supervised solutions and the unsupervised ones represented by the reference RBH, RSD, and OMA algorithms following the evaluation scheme in Figure 1 . The process separates the pairs into train and test sets and calculates pairwise similarity measures for the pairs of both sets. The sequences of the test sets should be used to run the unsupervised reference algorithms. The train set should be used for building the supervised models to be tested only with the test set.
Evaluation Scheme Considering Data Imbalance.
The performance quality evaluation involves the calculation of the following evaluation metrics for imbalanced datasets.
Evaluation Scheme Considering Data Imbalance.
The geometric mean ( -Mean) [49] is defined as -Mean = √sensitivity * specificity,
Evaluation Scheme Considering Data Imbalance.
where sensitivity = TP/(TP + FN) and TN Rate = specificity = TN/(FP + TN) are calculated from true positives (TP), false negatives (FN), false positives (FP), and true negatives (TN). The Area Under the ROC Curve (AUC) [50] is computed obtaining the area of the ROC graphic. Concretely, we approximate this area using the average of true positive rate and false positive rate values by means of the following equation:
Evaluation Scheme Considering Data Imbalance.
where TP rate = TP/(TP + FN) corresponds to the percentage of positive instances correctly classified and FP rate = FP/(FP+ TN) corresponds to the percentage of negative instances misclassified. We use -Mean seeking to maximize the accuracy of the two classes (orthologs and nonorthologs) by achieving a good balance between sensitivity and specificity that consider misclassification costs and AUC to show the classifier performance over a range of data distributions [51] . Tables 3, 4 , and 5, were built S. cerevisiae-S. pombe dataset contains ortholog pairs representing 95.18% of the union of the Inparanoid7.0 and GeneDB classifications described in [37] . On the other hand, S. cerevisiae-K. lactis and S. cerevisiae-C. glabrata datasets contain all ortholog pairs in the gold groups reported in [24] . When we built the set of instances with all possible pairs, we just excluded 89 genes from S. cerevisiae, 37 from C. glabrata,and 1403 from K. lactis since we did not find their genome physical location data in the YGOB database [52] , required for the LCB feature calculation. Tables 3, 4 , and 5 summarize the characteristics of the four datasets including the total number of gene pairs (#Ex.), the number of attributes (#Atts.), the labels for majority and minority classes (Class (maj; min)), the number of pairs in both classes (#Class (maj; min)), the percentage of pairs in majority and minority classes (%Class (maj; min)), and the imbalance ratio (IR).
Experiments for Building and Testing the
The calculation of gene pair features or attributes (average of local and global alignment similarity measures, length of sequences, gene membership to conserved regions (synteny), and physicochemical profiles within 3, 5, and 7 window sizes) was specified in the previous section.
Algorithms and Parameter
Values. The supervised algorithms compared in the experiments and the parameter values are specified in Table 7 . Additionally, Table 8 summarizes the parameter values and the implementation details for the unsupervised algorithms.
Results and Discussion
In this section, we first analyze the supervised approaches based on big data technologies, and later we compare the best supervised solution with the classical unsupervised methods. Table 9 for the Blosum50, Blosum621, Blosum622, and Pam250 datasets. The best values are in boldface. TheMean values of the supervised algorithms change only slightly with the selection of different alignment parameters. The stability of these classification results may be caused either by the aggregation of global and local alignment scores in a single similarity measure or by the appropriate combination of scoring matrices and gap penalties in relation to the sequence diversity between the two yeast genomes. The selection of the four scoring matrices was aimed at finding homologous protein sequences in a wide range of amino acid identities between both genomes. For example, Blosum50 and Pam250 scoring matrices are frequently used to detect proteins sharing less than 50% of amino acid identities [53] . In addition, the selected gap penalties values are not low enough to affect the sensitivity of the alignment [53] .
Supervised Classifiers: Analysis of Big Data Based
The average results of AUC and -Mean obtained in Experiments 1 and 2 for the supervised algorithms with different parameter values are shown in Table 10 . The average TP Rate and TN Rate are also depicted in Figure 2 . SVM-BD has been left out from the table due to its very poor performance in -Mean caused by its imbalance between TP Rate and TN Rate as shown in Figure 2 . Both Table 10 and Figure 2 prove that big data supervised classifiers managing imbalance outdo their corresponding big data supervised versions.
Supervised Classifiers: Analysis of Big Data Based
The ROS preprocessing method for big data makes SVM-BD useful for POD and improves the performance of RF-BD even more with a higher value for the resampling size parameter of 130% [54] . In contrast, both experiments show that the variation in this parameter value from 100% to 130% does not significantly influence the performance of the SVM-BD classifier with different regulation values.
Supervised Classifiers: Analysis of Big Data Based
Specifically, RF-BDCS shows the best performance in S. cerevisiae-C. glabrata and S. cerevisiae-K. lactis when the classification quality is measured by -Mean and AUC metrics, because it enhances the learning of the minority class. The criterion used to select the best tree split is based on the weighting of the instances according to their misclassification costs, and such costs are also considered to calculate the class associated with a leaf [34] . This cost treatment does not explicitly change the sample distribution and avoids the possible overtraining that it is present in the ROS solutions due to replicated cases. The election of the cost values ( (+ | −)= IR and (− | +) = 1) may also define the success of the algorithm.
Supervised Classifiers: Analysis of Big Data Based
In the case of SVM-BD, the fixed regularization parameter defines the trade-off between the goal of minimizing the training error (i.e., the loss) and minimizing the model complexity to avoid overfitting. The higher its value, the simpler the model. Nonetheless, setting an intermediate value or one close to zero may produce a better performance in classification [48] . This is the case of the ROS (RS: 100%) + SVM-BD (regParam: 0.5) classifier that exhibits the best AUC and -Mean values in S. cerevisiae-S. pombe and the best balance between TP Rate and TN Rate in the three datasets ( Figure 2) .
Supervised Classifiers: Analysis of Big Data Based
In order to balance time with classification quality, time consumption is another aspect to have in mind when comparing big data solutions. Table 11 contains run time in seconds for all big data solutions in each dataset and the faster algorithms are highlighted in boldface. These results allow us to prove that the time required is directly related to the operations needed for each method, as well as to the size of the datasets used to build the model. The fastest algorithm considering the average run time is SVM-BD followed by SVM-BD combined with ROS. Thus, the fastest algorithms coincide with the ones with better performance. In general, the ROS (RS: 100%) + SVM-BD (regParam: 0.5) classifier can be considered the best supervised solution considering both performance and time.
Comparison of Supervised versus Unsupervised Classifiers.
The average results of AUC and -Mean obtained for the best supervised algorithms and the unsupervised algorithms with different parameter values are shown in Table 12 for Experiments 1 and 2. The average TP Rate and TN Rate are also depicted in Figure 3 . The supervised classifiers outperform the unsupervised ones. Among the unsupervised algorithms, RSD reaches the highest G-Measure value by setting -value = 1 − 05 and = 0.8 (recommended values in [55] ) in S. cerevisiae-C. glabrata where similar results can also be seen for AUC and TP Rate values. On the contrary, OMA was the best among the unsupervised algorithms in S. cerevisiae-S. pombe datasets (Table 12) .
Comparison of Supervised versus Unsupervised Classifiers.
In general, the performance of all classifiers declined in S. cerevisiae-S. pombe datasets due to the fact that S. pombe is a distant relative of S. cerevisiae [56] . The supervised classifiers performance is affected for the same reason and also by the difference in data distribution between the train and test sets [57] . Conversely, ROS (RS: 100%) + SVM-BD (regParam: 0.5) remained stable in S. cerevisiae-C. glabrata and S. cerevisiae-S. pombe datasets when considering the balance between TP Rate and TN Rate . Superior results in S. cerevisiae-C. glabrata are outstanding, since both genomes underwent WGD and a subsequent differential loss of gene duplicates, so that algorithms are prone to produce false positives. Thus, this dataset contains "traps" for OD algorithms [24] .
Comparison of Supervised versus Unsupervised Classifiers.
The reduced quality shown by RBH, RSD, and OMA, mainly in the case of RBH, could be caused by their initial assumption that the sequences of orthologous genes/proteins are more similar to each other than they are to any other genes from the compared organisms. This assumption may produce classification errors [22] , mainly in RBH, that infer orthology relationships simply based on reciprocal BLAST Best Hits, in spite of the fact that BLAST parameters can be tuned as has been recommended in [58] .
Comparison of Supervised versus Unsupervised Classifiers.
Conversely, RSD not only compares the sequence similarity of query sequence of genome against all sequences of genome using the BLASTp algorithm, but also separately aligns sequence against the corresponding set of hits resulting from a BLAST search. Those pairs that satisfy a divergence threshold (defined as the fraction of the alignment total length) are used for the calculation of evolutionary distances. From this step, sequence yielding the shortest distance with sequence is retained and then used as query for a reciprocal BLASTp against genome . Thus, the algorithm is repeated in the opposite direction, and if finds as its best reciprocal short distance hit, then the pair ( , ) can be assumed as an ortholog pair and their evolutionary distance is retained. In sum, the RSD procedure relies on global sequence alignment and maximum likelihood estimation of evolutionary distances to detect orthologs between two genomes, and as a result, it finds many putative orthologs missed by RBH because it is less likely than RBH to be misled by existing close paralogs.
Comparison of Supervised versus Unsupervised Classifiers.
The OMA algorithm also displays advantages over RBH, corroborated in both Experiments 1 and 2. It uses evolutionary distances instead of alignment scores. This algorithm allows the inclusion of one-to-many and many-tomany orthologs. It also considers the uncertainty in distance estimations and detects potential differential gene losses.
Comparison of Supervised versus Unsupervised Classifiers.
From the point of view of the intrinsic information managed by the algorithms, the success of big data supervised classifiers managing imbalance over RSD and OMA may be explained by feature combinations calculated for the datasets together with the learning from curated classifications. That is, the assembling of alignment measures together with the comparison of sequence lengths, the membership of genes to conserved regions (synteny), and the physicochemical profiles of amino acids improves the supervised classification results on the test sets, even in those built from two species that underwent WGD.
Comparison of Supervised versus Unsupervised Classifiers.
With the aggregation of global and local alignment scores, we are combining protein structural and functional relationships between sequence pairs, respectively. Besides, we incorporate other gene pair features: (i) the periodicity of the physicochemical properties of amino acids which allows us to detect similarity among protein pairs in their spectral dimension [59] ; (ii) the conserved neighborhood information, which considers that genes belonging to the same conserved segment in genomes of different species will probably be orthologs; and (iii) the length of sequences that can be seen as the relative positions of nucleotides/amino acids within the same gene/protein in different species and in duplicated genomic regions within the same species.
Comparison of Supervised versus Unsupervised Classifiers.
In order to obtain (i), each of the two aligned sequences is first represented as an ordered arrangement of moving average values of amino acids contact energies in a window frame of the aligned regions without gaps. Then, each spectrum is correlated to obtain the pair similarity value. This feature may allow us to deal with sequences having functional similarities despite their low amino acid sequence identities (<35%). These sequences may affect OD in S. cerevisiae-S. pombe which are moderately related and their orthologs may be diverged.
Comparison of Supervised versus Unsupervised Classifiers.
In feature (ii), two genes from different genomes are more likely to be orthologs when they share a high sequence similarity and they are placed in the same LCB (conserved segment that does not seem to be altered by genome rearrangements [60] ). The detection of authentic orthologs is frequently impaired by genome rearrangements and other large-scale evolutionary events like WGD.
Comparison of Supervised versus Unsupervised Classifiers.
With regard to sequence length (iii), it is disturbed by insertion and deletion of stretches of DNA over evolutionary time. This makes more distant relatives have a higher likelihood of sequence length difference [61] . In this way, the genomes involved in this study are relatives and length similarities may complement the detection of homology.
Conclusions
The development of effective supervised algorithms for POD in a big data scenario was made possible by (i) the availability of curated databases (authentic orthologs), (ii) the combination of traditional alignment measures with other gene pair features (sequence length, gene membership to conserved regions, and physicochemical profiles) to complement homology detection, and (iii) the treatment of the low ratio of orthologs to the total possible gene pairs between two genomes. By applying evaluation metrics such asMean, AUC, and the balance between TP Rate and TN Rate , our results show that gene pairwise feature combinations provide excellent POD in a big data supervised scenario that considers data imbalance. The SVM-BD classifier combined with the ROS (RS: 100%) preprocessing with regulation parameter 0.5 outdid the rest of the big data supervised solutions and the popular unsupervised (RBH, RSD, and OMA) algorithms even when the supervised model was extended to datasets containing "traps" for OD algorithms. The classification performance of the supervised algorithms measured byMean and AUC metrics did not significantly change in the four test sets obtained with different alignment parameter settings. When the balance between time and classification quality is considered, ROS (RS: 100%) + SVM-BD (regParam: 0.5) also proves to be the algorithm of choice.
Conclusions
In future research, the introduction of new gene pair features might improve the effectiveness and efficiency of the supervised algorithms for POD.

{'paper_id': '8260510', 'title': 'An Effective Big Data Supervised Imbalanced Classification Approach for Ortholog Detection in Related Yeast Species', 's2_url': 'https://api.semanticscholar.org/CorpusID:8260510', 'source': 'S2ORC'}