The gene family-free median of three

Abstract

Background: The gene family-free framework for comparative genomics aims at providing methods for gene order analysis that do not require prior gene family assignment, but work directly on a sequence similarity graph. We study two problems related to the breakpoint median of three genomes, which asks for the construction of a fourth genome that minimizes the sum of breakpoint distances to the input genomes.

Methods: We present a model for constructing a median of three genomes in this family-free setting, based on maximizing an objective function that generalizes the classical breakpoint distance by integrating sequence similarity in the score of a gene adjacency. We study its computational complexity and we describe an integer linear program (ILP) for its exact solution. We further discuss a related problem called family-free adjacencies for k genomes for the special case of [Formula: see text] and present an ILP for its solution. However, for this problem, the computation of exact solutions remains intractable for sufficiently large instances. We then proceed to describe a heuristic method, FFAdj-AM, which performs well in practice.

Results: The developed methods compute accurate positional orthologs for genomes comparable in size of bacterial genomes on simulated data and genomic data acquired from the OMA orthology database. In particular, FFAdj-AM performs equally or better when compared to the well-established gene family prediction tool MultiMSOAR.

Conclusions: We study the computational complexity of a new family-free model and present algorithms for its solution. With FFAdj-AM, we propose an appealing alternative to established tools for identifying higher confidence positional orthologs.

Keywords: Breakpoint median; Family-free genome comparison; Positional orthology.

Fig. 1

a Illustration of the score of a candidate median gene. b Gene similarity graph of three genomes G, H, and I. Colored components indicate candidate median genes $m_1=(g_1,h_1,i_2)$, $m_2=(g_2,h_2,i_1)$, $m_3=(g_3,h_3,i_2)$, and $m_4=(g_4,h_3,i_3)$. Median gene pairs $m_1,m_3$ and $m_3,m_4$ are conflicting

Fig. 2

The effect of duplication and deletion of a single gene in problem FF-Median. Colored arcs correspond to potential median adjacencies

Fig. 3

The seven valid types of components of a partial 3-matching

Fig. 4

Program FF-Median, an ILP for solving problem FF-Median

Fig. 5

Algorithm ICF-SEG

Fig. 6

Program FFAdj-3G, an ILP for solving FF-Adjacencies for three genomes

Fig. 7

The implications of Constraint (C.02) on combinations of saturated edges. Parts a–p visualize all 16 possibilities that are valid under Constraint (C.01). The parts show how edges incident to genes i and h are effected by the first case of Constraint (C.02) that acts on edges $\{g,h\}$ and $\{g,i\}$ (green lines). Saturated edges are indicated by thick continuous lines, unsaturated edges by dashed lines. Dotted gray lines are not considered by the constraint and can be either saturated or unsaturated. Only combinations shown in Parts h, l, and p violate constraint (C.02)

Fig. 8

Top Precision and recall of a FF-Median and b FFAdj-AM in comparison with MultiMSOAR in simulations; Middle agreement, compatibility and disagreement of positional orthologs inferred by c FFAdj-AM and d MultiMSOAR with the OMA database; Bottom e statistical assessment of CARs and median genes inferred by FF-Median on real datasets; f histogram of fragile orthologies in results obtained by FFAdj-AM and MultiMSOAR