Algorithm of OMA for large-scale orthology inference

Abstract

Background: OMA is a project that aims to identify orthologs within publicly available, complete genomes. With 657 genomes analyzed to date, OMA is one of the largest projects of its kind.

Results: The algorithm of OMA improves upon standard bidirectional best-hit approach in several respects: it uses evolutionary distances instead of scores, considers distance inference uncertainty, includes many-to-many orthologous relations, and accounts for differential gene losses. Herein, we describe in detail the algorithm for inference of orthology and provide the rationale for parameter selection through multiple tests.

Conclusion: OMA contains several novel improvement ideas for orthology inference and provides a unique dataset of large-scale orthology assignments.

Figure 1

Algorithm flow chart. Boxes represent the steps of the algorithm, and arrows are the input and output data for each step.

Figure 2

Tests to determine the optimum length criterion value. The fraction of candidate pairs that pass the triangle inequality test and the fraction that have the same number of domains increases with stricter (higher) length tolerance. In contrast, the number of predicted orthologous relationships decreases with stricter length tolerance. To consider only alignments that cover at least a fraction of the sequence length, a length criterion value of ℓ = 0.61 is used in this study.

Figure 3

Different methods to find potential orthologs. The mutual best alignment can be determined by similarity score or by evolutionary distance (columns), and with or without the use of a tolerance to include multiple orthologous relationships (rows).

Figure 4

Test to distinguish in-paralogs and out-paralogs. A What is the relationship of sequences y₁ and y₂ with regard to x? Identify which branch to place the root by finding an out-group sequence z. B If the root on the branch leading to x, then y₁ and y₂ are out-paralogs. C If duplication takes place after speciation, y₁ and y₂ are in-paralogs. D To test if y₁ and y₂ are in-paralogs, we confirm that the distance d of the internal branch is greater than zero.

Figure 5

Value for stable pair tolerance parameter. The fraction of stable pairs that pass the out-paralog test has a local optimum at the SP-tolerance 1.81, for five different length criteria. Increasing the tolerance value results in a larger fraction of stable pairs suspected as out-paralogs.

Figure 6

Assignment of potential paralogs. A In an evolutionary scenario, an ancestral gene is duplicated, followed by two speciation events, followed by asymmetrical gene loss of genes x₂ and y₁. The paralogous genes x₁ and y₂ could be mistaken for orthologs, but the duplicates are retained in genome Z that can act as a witness of non-orthology. B Schematic for verifying a stable pair between x₁ and y₂ using genome Z. If (x₁, z₁) and (y₂, z₂) form stable pairs and are the closest relatives then x₁ and y₂ are paralogs and were not verified. C The only possible quartet formed when (x₁, z₁) and (y₂, z₂) are the closest related sequences is shown.

Figure 7

Value for verified pair tolerance parameter. The fraction of verified pairs that passes the out-paralog test is drawn. The top curve is produced with the use of the optimal previous parameters, and the lower curves are produced at other parameter settings and also have locally optimal values, both show similar optimal values (1.53) as the best curve.

Figure 8

A An example graph containing one 4-clique, four 3-cliques, and eight 2-cliques is provided. The highest scoring partition of the graph is {w₁, x₁, z₁}, {y₂, z₂}. B A possible evolutionary scenario corresponding to the graph.

Figure 9

Evolutionary relations and corresponding classes of pairs. The hierarchy of pairs are classified according to evolutionary relations. We seek to find the borders of pairs to capture underlying evolutionary relations. Verified pairs are designed to cover all orthologs, and group pairs are a subset of the closest orthologs. Broken pairs are cases where paralogy is explicitly classified.

Figure 10

Number of pairs reported after each step. Each step of the algorithm reduces the number of pairs, and the largest reduction is observed with the formation of stable pairs.

Figure 11

Distribution of group size. The average group size is drawn for several versions of orthologous matrices. For large sets of genomes (e.g. All and Bacteria) very few groups are full (i.e. have one member from each genome).