Inferring hierarchical orthologous groups from orthologous gene pairs

Abstract

Hierarchical orthologous groups are defined as sets of genes that have descended from a single common ancestor within a taxonomic range of interest. Identifying such groups is useful in a wide range of contexts, including inference of gene function, study of gene evolution dynamics and comparative genomics. Hierarchical orthologous groups can be derived from reconciled gene/species trees but, this being a computationally costly procedure, many phylogenomic databases work on the basis of pairwise gene comparisons instead ("graph-based" approach). To our knowledge, there is only one published algorithm for graph-based hierarchical group inference, but both its theoretical justification and performance in practice are as of yet largely uncharacterised. We establish a formal correspondence between the orthology graph and hierarchical orthologous groups. Based on that, we devise GETHOGs ("Graph-based Efficient Technique for Hierarchical Orthologous Groups"), a novel algorithm to infer hierarchical groups directly from the orthology graph, thus without needing gene tree inference nor gene/species tree reconciliation. GETHOGs is shown to correctly reconstruct hierarchical orthologous groups when applied to perfect input, and several extensions with stringency parameters are provided to deal with imperfect input data. We demonstrate its competitiveness using both simulated and empirical data. GETHOGs is implemented as a part of the freely-available OMA standalone package (http://omabrowser.org/standalone). Furthermore, hierarchical groups inferred by GETHOGs ("OMA HOGs") on >1,000 genomes can be interactively queried via the OMA browser (http://omabrowser.org).

Figure 1. Hierarchical orthologous groups and their relationship to the orthology graph and the underlying gene and species trees.

In this example, the hierarchical groups for the taxonomic range are drawn in orange. By definition, these groups correspond to the sets of leaves attached to the speciation nodes of the gene tree coloured in orange.

Figure 2. Illustration of Lemma 1: the taxonomic range induces a set of speciation node (left) and associated hierarchical orthologous groups (centre).

Likewise, it also induces an orthology subgraph with set of connected component (right). Lemma 1 establishes the one-to-one correspondence between and (which we prove by viewing it as composition of the one-to-one correspondences and ).

Figure 3. Example of an orthology graph.

An example orthology graph from the OMA database where two false positive prediction merges two well-defined orthologous groups. At the level of vertebrates, the NOX family forms 4 different orthologous groups. Because of two spurious predictions, the NOX1 and NOX2 clusters get weakly connected. The minimum cut algorithm will split them, as there are only two edges to cut.

Figure 4. Validation on simulated data: precision-recall plots of COCO-CL, LOFT and the algorithm introduced here (GETHOGs) on two datasets of 30 simulated genomes (200 genes each).

The two datasets show average rates of 4 independent runs of genome simulations with fixed parameters. The difference between the two datasets are essentially different gene duplication rates (see Method section for details). As a point of reference, we also show the performance of pairwise orthologs inferred in OMA (OMA Pairwise). The colour gradient corresponds to various parameter values for GETHOGs and bootstrap value for COCO-CL.

Figure 5. Validation on empirical data: precision-recall plot of our newly proposed GETHOGs, COCO-CL, LOFT, EggNOG and OrthoDB on orthologous and paralogous gene relationships for the 3 gene families (3,783 relationships in total) analysed in Boeckmann et al.

. Predictions for GETHOGs and COCO-CL are computed using the default parameters (respectively and bootstrap). The points for EggNOG and OrthoDB are from the original analysis (Reference [9],table 2).