article: Accurate genome-wide identification of orthologs is a central problem in comparative genomics, a fact reflected by the numerous orthology identification projects developed in recent years. However, only a few reports have compared their accuracy, and indeed, several recent efforts have not yet been systematically evaluated. Furthermore, orthology is typically only assessed in terms of function conservation, despite the phylogeny-based original definition of Fitch. We collected and mapped the results of nine leading orthology projects and methods (COG, KOG, Inparanoid, OrthoMCL, Ensembl Compara, Homologene, RoundUp, EggNOG, and OMA) and two standard methods (bidirectional best-hit and reciprocal smallest distance). We systematically compared their predictions with respect to both phylogeny and function, using six different tests. This required the mapping of millions of sequences, the handling of hundreds of millions of predicted pairs of orthologs, and the computation of tens of thousands of trees. In phylogenetic analysis or in functional analysis where high specificity is required, we find that OMA and Homologene perform best. At lower functional specificity but higher coverage level, OrthoMCL outperforms Ensembl Compara, and to a lesser extent Inparanoid. Lastly, the large coverage of the recent EggNOG can be of interest to build broad functional grouping, but the method is not specific enough for phylogenetic or detailed function analyses. In terms of general methodology, we observe that the more sophisticated tree reconstruction/reconciliation approach of Ensembl Compara was at times outperformed by pairwise comparison approaches, even in phylogenetic tests. Furthermore, we show that standard bidirectional best-hit often outperforms projects with more complex algorithms. First, the present study provides guidance for the broad community of orthology data users as to which database best suits their needs. Second, it introduces new methodology to verify orthology. And third, it sets performance standards for current and future approaches.
  In this study, we consider publicly available databases of orthologs that distinguish themselves by popularity, size, quality, or methodology. One of the oldest large-scale orthology database is COG [1], [18] and its eukaryotic equivalent KOG [18], which despite no recent update are still considered by many authors as the standard orthologs databases. Their reliance on manual curation make them not scalable to all complete genomes. Unsupervised orthology assignment requires more sophisticated algorithms, such as those of Inparanoid [2], [19], OrthoMCL [3] or EggNOG [8]. We also investigated the results of RoundUp [5], interesting for its relatively large size and its use of pairwise evolutionary distances between genes to detect orthology. OMA [4], [20], our own orthology assignment project, is also based on evolutionary distances but takes into account the variance of the distance estimates and try to exclude pseudo-orthologs arising from differential gene losses using third-party species. A very different approach is taken in the orthology prediction of Ensembl Compara[7], which is based on inference and reconciliation of gene and species trees. Homologene [6] uses a pairwise gene comparison approach combined with a guide tree and gene neighborhood conservation to group orthologs, but the details of their methodology are unpublished. Finally, we also compare the results to the standard approaches of bidirectional best-hits (BBH) [21], common in ad-hoc analyses, and reciprocal smallest distance (RSD) [22]. The size of the different projects is depicted in Figure 1. Orthology is a relation over pairs of genes. However, few projects (namely Ensembl Compara, OMA and RoundUp) explicitly provide output of all pairs of predicted orthologs. This representation, although precise, has practical drawbacks: on one hand, it scales poorly (quadratically with the number of genes analyzed), and on the other hand, it does not present the predictions in a particularly insightful way. To solve these issues, many projects cluster pairs of orthologs into groups. This grouping process is not trivial, because orthology, at least when the phylogeny-based definition applies, is a non-transitive relation. The most common approach (taken by all other projects) is to form groups of orthologs and “in-paralogs”. The relations in- and out-paralogs were defined by Remm et al. [2], and are used to distinguish between paralogs from recent and old duplication events respectively. Formally, these two relations are not defined over a pair, but over a triplet: two genes and a speciation event of reference. Two genes are in-paralogs with respect to a particular speciation event if they are paralogs and their duplication event occurred after that speciation event of reference. They are out-paralogs if they are paralogs and their duplication event occurred before the speciation event of reference. See Figure S1a in Supporting Information for an example. Unfortunately, the fact that in- and out-paralogy are ill-defined in the absence of a clear speciation event of reference is underappreciated in the literature. We now come back to the description of groups of orthologs and in-paralogs: such groups are constructed such that every pair of genes in the group is either orthologous or in-paralogous with respect to the last speciation event in their clade, that is, such in-paralogs are genes inside the same species resulting from a duplication event that occurred after all speciation. Consequently, in such groups, the implication is that gene pairs are orthologs if they belong to the different species, else they are paralogs. Note that this grouping approach shows its limits when one or several duplication events have occurred after the first, but before the last speciation events. In such cases, not uncommon in Eukaryotes, the non-transitive nature of orthology makes it impossible to partition all genes in such groups without losing orthologous relations (see Figure S1b for an example). In OMA for instance, groups of orthologs include less than half of all predicted pairwise orthologous relations (Table S1). This problem does not affect Inparanoid, because it provides predictions for each pair of species separately, and so in every case, there is only one speciation event. To perform a fair comparison of the different predictions, a common set of sequences must be established. Unfortunately, the different projects vary considerably in their sizes, the type of genome analyzed and the origin of the protein sequences used. In fact, some projects have no overlap at all, and therefore comparison on a common set of sequences for all projects is not possible. Instead, we performed pairwise project comparisons with OMA (which includes the largest amount of sequences), and then we repeated the tests on an intersection set with only the most competitive projects. First, sequences from the different projects were mapped to OMA' s only if they were identical, between consistent genomes. This strict requirement avoids reliance on IDs, which may refer to different sequences depending on the genome version, and also the problem of different splicing variants. Tables S1 and S2 in Supporting Information present some statistics on the mapping procedure of the sequences and the predictions. In pairwise tests, we compared the pairs of mappable proteins identified as orthologs by the different methods with those identified by OMA. In joint tests, we computed the intersection of the mappable sequences of each project under consideration, and compared pairs in this intersection set identified as orthologs by the different methods. Datasets S1, S2, S3, S4, S5, S6, S7, S8, S9, S10, S11, S12 in Supporting Information list the intersection sets we used in all analyses below.
  According to the phylogenetic definition, two homologous genes are orthologs if they diverged through a speciation event. Therefore, the phylogenetic tree of a set of orthologs (a set of genes in which any pair is orthologous) has by definition the same topology as the corresponding species tree. One of the main application of orthology is the propagation of functional annotation, because orthologs often have a similar function. In fact, this application is so prominent that many authors use the term “orthologs” to refer to genes with conserved function in different species. As mentioned in the introduction, this definition is ambiguous. Therefore, we could only test specific aspects of what can be implied by “conserved function”. The four tests presented here evaluate the similarity of predicted orthologs in terms of gene ontology annotations, enzyme classification numbers, expression level, and gene neighborhood conservation. In the following, we present and discuss their results. We now justify the absence of three other tests that have been previously reported in the literature. We did not verify orthology based on common keywords in the annotation because those are often assigned on the basis of sequence similarity or using the methods that are tested here: this would introduce circularity in the testing strategy. Nor do we test orthology based on conservation in protein-protein interaction (PPI). Though there are studies such as Bandyopadhyay et al. [33] reporting modest but measurably higher PPI between some orthologs, it remains unclear to us how current PPI data can be turn into a test of orthology for the following two reasons: first, PPI data show large variations in reliability and completeness across experiments and species, but more importantly, the general problem of matching (or “aligning”) networks is computationally hard [34]. To reduce complexity, most approaches, including Bandyopadhyay et al. [33], strongly constrain the network alignment using heuristics based on sequence similarity. In the present context, this too would introduce circularity in the validation. Finally, we do not use the latent class analysis approach of Chen et al. [10]. This approach computes maximum likelihood estimates of false-positive and false-negative rates for all the projects directly from the various ortholog predictions (the data) and a parameterized multivariate distribution of the errors (the model). This looks very attractive, because the assessment does not require any of the external information used in the tests described here. Our critique with this approach is that their results are conditional on their error model, which is not verified (at least not in the context of evaluating orthology inference projects). In a sense, the issue of validation is shifted to their error model, but remains open. The main other systematic evaluation of orthology prediction projects is from Hulsen et al. [9]. Smaller in scope, their study tested functional orthologs predictions in Human–Mouse and Human–C. elegans, using a manually curated reference set of orthologs, expression correlation and conservation of gene neighborhood. They compared BBH, Inparanoid, OrthoMCL, KOG, as well as two other methods not under analysis here (“PhyloGenetic Tree” and “Z 1 Hundred”). On the tests and data common to both studies, the results are largely consistent (data not shown). However, we observed that considering only two pairs of species can introduce significant biases in the assessment: as it turns out, the overwhelming majority (89. 1%) of all orthologous pairs predicted by Inparanoid on Human–Worm data arise from one large cluster of olfactory-type receptor proteins (cluster number 4604). This very atypical distribution explains why the results are so different from those for the HUMAN-MOUSE genome pair (see Figures 3 and 4 from [9]). They concluded that in terms of functional orthology, Inparanoid performed best overall, while also noting that the appropriate method depends on the user' s requirements in terms of sensitivity and specificity. As our results show, this trade-off remains true today, but Inparanoid is no longer the overall best performer: besides being one of the projects with fewest genomes under analysis, there are other projects with either higher specificity, or with higher sensitivity; this reduces the scope of applications in which it constitutes an appropriate choice. Accurate ortholog prediction is crucial for many applications ranging from protein annotation to phylogenetic analysis. There is a number of publicly available orthology databases but little is known about their performances. In this study we compared 11 different projects and methods by submitting them to a variety of tests with respect to both phylogenetic and functional definitions of orthology. The results obtained in the tests for both definitions are consistent, and allow us comparison of the different projects on an objective basis. In phylogenetic tests, OMA and Homologene showed the best performances. The same two projects do also best in functional tests if a high level of specificity is required. At a somewhat lower degree of specificity, but at a higher coverage, function-based tests suggest that OrthoMCL outperforms Ensembl Compara, and to a less extent Inparanoid. Finally, for applications that only require coarse-grained functional categories, EggNOG provides the largest coverage. In terms of methodology, the one project based on gene and species tree reconciliation, Ensembl, had overall decent performances, but was overperformed by some of the best pairwise approaches. This suggests that tree reconciliation, although more powerful a method in theory, is not necessarily the best method in practice. Another surprise is the good overall performance of the simple BBH approach. Although the method is restricted to 1: 1 orthologs, the derived relations show good comparative accuracy in terms of Fitch' s definition. Orthologs predicted by BBH also show close functional relatedness. This result probably explains why many people use ad-hoc BBH implementations for their analyses rather than a more sophisticated orthology method. Beyond the accuracy aspects discussed in the present work, other factors will also affect the choice of orthologs database, such as the number of genomes analyzed, the state of maintenance, the availability of the predictions, or the usability of the web-interface. There is still improvement potential in orthology inference, and we expect much development in the coming years. We hope that the present work helps setting performances standards. But it is also the responsibility of upcoming orthology assignment projects or releases to clearly state the definition of orthology they pursue, to explain their grouping strategy, and in the very least to demonstrate the improvement of their methods over basic methods such as BBH or RSD.
  All the projects included in this study are publicly available. A short description of the chosen configurations and references are given in the following. We used the default parameters unless mentioned otherwise. RoundUp: RoundUp can be downloaded from https: //rodeo. med. harvard. edu/tools/roundup/. It is available with different parameter settings to tune for the desired sensitivity. In this comparison we included the strictest parameter set (also default settings), i. e. Blast E-value cutoff 10−20 and divergence cutoff 0. 2. Inparanoid: Inparanoid is available from http: //inparanoid. sbc. su. se. We used the release 6. 0 from Aug 2007 including 35 species. Ensembl Compara: The orthology predictions from Ensembl were obtained from the Compara database version 47, which is available from http: //oct2007. archive. ensembl. org/. COG, KOG: Cluster of Orthologous Groups and its eukaryotic equivalent are available from http: //www. ncbi. nlm. nih. gov/COG/. We used the versions from Mar 2003 and Jul 2003 respectively. OrthoMCL: We obtained the version from Sep 2006 of OrthoMCL from http: //orthomcl. cbil. upenn. edu/. Homologene: Homologene is available from the NCBI webpage www. ncbi. nlm. nih. gov/HomoloGene/. For this comparison, we used built 58 from Nov 2007. EggNOG: EggNOG is available from http: //eggnog. embl. de/. We used the data from Oct 2007 including 373 species. OMA: OMA is available in various formats on http: //www. omabrowser. org. We used the the data from Nov 2007 including 550 species. OMA infer orthology at the level of pairs of sequences (“OMA Pairwise”), from which it also computes groups of orthologs (“OMA Group”). Both type of predictions are included in the comparisons. BBH: The typical Bidirectional Best Hit implementation uses BLAST for aligning the protein sequences. We used the more accurate algorithm from Smith and Waterman [35] for the alignment with the same scoring threshold as used by the OMA algorithm for the all-against-all step. RSD: Reciprocal Smallest Distance orthology relations are computed using ML distance estimates from pairwise alignments having significant alignment scores (Dayhoff score >217, the cut-off used by OMA as well) A consequence of Fitch' s definition is that trees of orthologs are congruent to the species tree (i. e. the topology, or branching order, is the same). The phylogenetic reconstruction test uses this property to test the predicted orthologs. It uses three reference species trees (see Text S1 in Supporting Information) whose branching order is well-accepted, and whose topology follows a “comb” structure, that is, completely unbalanced. Each leaf consists of one or several species. The phylogeny of species that share the same leaf is not necessarily well resolved, but this fact is irrelevant here, because, as we shall see below, the test includes at most one sequence per leaf in each tree reconstructed. Including more than one species per leaf is merely a way to include more data in the test. The eukaryotic reference tree follows the NCBI taxonomy, the bacterial one follows the lineage tree by Bern et al. [36] and the fungal reference tree follows the NCBI tree, but with correction regarding the placement of the two Candida species [37]. In each trial, a starting sequence from a random species in the innermost leaf is randomly chosen. Then, for each project under scrutiny, we try to build a set of sequences consisting of one ortholog per leaf. If a project predicts more than one sequence orthologous to the starting sequence in a leaf, one of them is picked randomly. If a project predicts no ortholog in a particular leaf, sequence from that leaf are excluded from other projects as well, such that the resulting sets of sequences are of the same size for all projects. If the orthologous groups have less than 5 sequences, the procedure restarts with another starting sequence. Else, based on each orthologous set, we build a tree (as described below) and assess its agreement with the reference species tree by computing the fraction of correct splits derived from the Robinson-Foulds metric [23]. The “comb” structure of the topology is necessary to ensure that a set of sequences orthologous to a starting sequence indeed constitutes an orthologous groups (that is, a set of sequences in which every pair is orthologous): recall that two sequences are orthologs if they split through speciation. Thus, if all bifurcations in the gene trees are speciation events, the set of sequences constitute an orthologous group. Due to the particular topology, each bifurcation is the split of the innermost sequence from another sequence. Since the innermost sequence is orthologous to all other sequences, all bifurcations are speciation events, and the conclusion follows. The sequences are aligned pairwise using Smith and Waterman [35], with joint ML estimation of all pairwise distances using the Align function of Darwin [38]. The estimated distance and variances are used to compute a least-squares distance tree using Darwin' s LeastSquaresTree function. As a second method for computing the gene tree, we use Muscle [39] as multiple sequence alignment tool in combination with RaxML-VI-HPC version 2. 2. 3 [40] as tree building package. RaxML builds maximum-likelihood trees. Muscle was run with default parameters, while RaxML was run with JTT with 4 gamma categories as amino acid substitution model. The method is repeated from ten random start topologies. The tree with the highest likelihood is taken as the resulting tree of this method. We used four different sources of manually curated orthology reference sets from the literature: (1) A reconciled tree of Pfam adenosine/AMP deaminase family (PF00962) produced by Engelhardt et al. [26], [41]. This tree contains 251 proteins from which we could map 146. (2) Results from detailed phylogenetic analysis on three different COGs presented in [24]. From the originally 116 proteins, 82 were mappable, again restricting on identical sequences. (3) Resulting trees from the phylogenetic analysis by Hughes [27] of 10 gene families. 33 of 165 proteins could be mapped. (4) The ortholog reference set proposed by Hulsen et al. [9]. From there 102 of the 167 proteins could be mapped. For every of those difficult phylogenies, we extracted the orthologous and paralogous relations. For the purpose of this study, those assignments are considered to be error free and are taken as a reference set. For every possible protein pair where both proteins are present in the common set of sequences, we determined whether the project made a true positive, a true negative, a false-positive or a false-negative prediction. Those measurements are then used to infer the true positive and the false-positive rate respectively by taking a Bayesian approach with a uniform prior. Finally, the results of the performance on the four phylogenies have been averaged.
summary: The identification of orthologs, pairs of homologous genes in different species that started diverging through speciation events, is a central problem in genomics with applications in many research areas, including comparative genomics, phylogenetics, protein function annotation, and genome rearrangement. An increasing number of projects aim at inferring orthologs from complete genomes, but little is known about their relative accuracy or coverage. Because the exact evolutionary history of entire genomes remains largely unknown, predictions can only be validated indirectly, that is, in the context of the different applications of orthology. The few comparison studies published so far have asssessed orthology exclusively from the expectation that orthologs have conserved protein function. In the present work, we introduce methodology to verify orthology in terms of phylogeny and perform a comprehensive comparison of nine leading ortholog inference projects and two methods using both phylogenetic and functional tests. The results show large variations among the different projects in terms of performances, which indicates that the choice of orthology database can have a strong impact on any downstream analysis.
keywords: genetics and genomics/genomics
  genetics and genomics/comparative genomics
  genetics and genomics/functional genomics
  computational biology/comparative sequence analysis
  computational biology/protein homology detection
  evolutionary biology/genomics
  computational biology/genomics
  evolutionary biology/bioinformatics
title: Phylogenetic and Functional Assessment of Orthologs Inference
                      Projects and Methods