PMCCPMCCPMCC

Search tips
Search criteria 

Advanced

 
Logo of amolbioBioMed CentralBiomed Central Web Sitesearchsubmit a manuscriptregisterthis articleAlgorithms for Molecular Biology : AMB
 
Algorithms Mol Biol. 2017; 12: 6.
Published online 2017 March 14. doi:  10.1186/s13015-017-0098-8
PMCID: PMC5349084

On the computational complexity of the maximum parsimony reconciliation problem in the duplication-loss-coalescence model

Abstract

Background

Phylogenetic tree reconciliation is a widely-used method for inferring the evolutionary histories of genes and species. In the duplication-loss-coalescence (DLC) model, we seek a reconciliation that explains the incongruence between a gene and species tree using gene duplication, loss, and deep coalescence events. In the maximum parsimony framework, costs are associated with these event types and a reconciliation is sought that minimizes the total cost of the events required to map the gene tree onto the species tree.

Results

We show that this problem is NP-hard even for the special case of minimizing the number of duplications. We then show that the problem is APX-hard when both duplications and losses are considered, implying that no polynomial-time approximation scheme can exist for the problem unless P = NP.

Conclusions

These intractability results are likely to guide future research on algorithmic aspects of the DLC-reconciliation problem.

Keywords: Phylogenetic reconciliation, Duplication-loss-coalescence model, NP-hardness, APX-hardness

Background

Phylogenetic tree reconciliation is a fundamental technique in the study of the evolutionary relationships of genes and species. Given a gene tree, a species tree, and the association between their leaves, we seek to explain the incongruence between the two trees using a set of evolutionary events. In the widely-used DL model, duplication and loss events are considered, while the DTL model considers horizontal transfers as well. Although these models can explain paralogous gene families, they do not address population effects. In contrast, coalescent models [1] can explain population effects but implicitly assume that all genes are orthologs. Recently, a new duplication-loss-coalescence (DLC) model has been proposed that combines the duplication-loss tree reconciliation model with a coalescent model. This DLC model has been shown to have higher accuracy of reconstructing evolutionary events than the DL model alone [2, 3].

Reconciliation is often performed using a maximum parsimony formulation in which each type of event in the model has an associated non-negative cost and the objective is to find a reconciliation of minimum total cost. Wu et al. [3] gave the first maximum parsimony algorithm for the DLC reconciliation problem. That algorithm has worst-case exponential time, leaving open the question of whether the problem can be solved in polynomial time.

In this paper, we show that the DLC parsimony problem is NP-hard and, further, has no polynomial-time approximation scheme (PTAS) unless P = NP. Specifically, we show that:

  1. The DLC parsimony problem is NP-hard even when only seeking to minimize the number of duplications (i.e., loss and coalescence events have zero cost). However, the problem of minimizing duplications alone can be approximated using a PTAS for the multicut problem [4].
  2. The DLC parsimony problem is APX-hard even when only duplications and losses are considered (i.e., coalescence events have zero cost), which implies that no PTAS exists for this problem unless P = NP.

Just as complexity results for DTL parsimony [57] guided the direction of algorithmic research on that problem, these results serve to guide future work on algorithms and heuristics for the DLC parsimony problem.

Finally, we note that while the DLC reconciliation problem considers duplications and losses, those events are treated differently from duplications and losses in the DL and DTL models due to the introduction of explicit gene loci in the DLC model. Thus, the complexity results that we offer here are not directly related to those for the DL and DTL models. The interested reader is referred to [57] for discussions of the DL and DTL models and known results about their computational complexity.

Problem statement and preliminaries

This section provides notation, definitions, and basic results that will be used throughout the paper.

Graph definitions

We begin with notation and definitions adapted from Wu et al. [3]. A tree is a rooted binary tree T = (V(T), E(T)) where V(T) denotes the set of nodes and E(T) denotes the set of directed edges, also called branches. An edge terminating at a leaf node is called a terminal edge. Denote by L(T) ⊂ V(T) the set of leaves of T, I(T) = V(T)\L(T) the set of internal nodes, and r(T) ∈ I(T) the root node. In a binary tree, leaves correspond to extant taxa whereas internal nodes correspond to ancestral taxa.

Denote by c(v) the set of children of v, p(v) the parent of v, and e(v) the directed edge (p(v), v). The partial orders T and T on V(T) are defined by uTv if u is on the path from r(T) to v and uTv if v is on the path from r(T) to u. Note that as required by a partial ordering, T and T are reflexive (uTu and uTu). If uTv and u ≠ v then u is said to be an ancestor of v and v is a descendant of u. The distance from a node u to v, where uTv, is the length of the shortest path from u to v. The least common ancestor of nodes uv, denoted lca(uv), is the node w of maximum distance from r(T) such that wTu and wTv. For two nodes uv ∈ T, we say that an edge e separates u and v if e is either on the path from lca(uv) to u or on the path from lca(uv) to v. For convenience, we also use lca as shorthand for the term “least common ancestor” when the context is clear.

Reconciliations

A leaf map is a function Le:L(G) → L(S) that associates each leaf in the gene tree with the leaf in the species tree in which that gene is found. This function need not be one-to-one nor onto; gene tree leaves that map onto the same species tree leaf correspond to paralogous genes. The labeled coalescent tree, defined below, formalizes the notion of a reconciliation in the DLC model.

Definition 1

(Labeled Coalescent Tree) Given gene tree G, species tree S, and leaf map Le:L(G) → L(S), a labeled coalescent tree (LCT) for (GSLe) is a tuple (ℳ, 𝕃, ℒ) where:

  • ℳ:V(G) → V(S) is a species map which maps each node of G to a node of S;
  • 𝕃 is a finite set, called the locus set of loci that have evolved within the gene family;
  • ℒ:V(G) → 𝕃 is a locus map that maps each node of G to a locus in 𝕃

subject to the following constraints:

  1. If g ∈ L(G), then ℳ(g) = Le(g);
  2. If g ∈ I(G), then for g ∈ c(g), ℳ(g)≤Sℳ(g);
  3. For gg ∈ L(G) where g ≠ g, if Le(g) = Le(g) then ℒ(g) ≠ ℒ(g);
  4. For  ∈ 𝕃, there exists g ∈ V(G) s.t. ℒ(g) = ;
  5. For  ∈ 𝕃, let N() = {g|g ∈ V(Gg ≠ r(G);ℒ(g) = ;ℒ(p(g)) ≠ }. Then |N()| ≤ 1, where equality holds everywhere except for = ℒ(r(g)).

Constraint 1 asserts that the species map extends the leaf map Le; constraint 2 asserts that a gene node is mapped to either the same node or an ancestor of each of its children; constraint 3 asserts that since extant gene nodes (leaves) mapped to the same extant species (leaves) are paralogs, they must be mapped to different loci; constraint 4 asserts that the locus set only includes a locus if at least one gene uses that locus; and constraint 5 asserts that each locus is created only once.1

A gene node g is said to be a speciation node with respect to map if for each child g ∈ c(g),  ℳ(g) ≠ ℳ(g). Since a branch of the gene tree may span multiple branches of the species tree for a given map , implied speciation nodes are added as follows: For each non-root internal node g ∈ I(G)\{r(G)} such that either (1) p(ℳ(g)) ≠ ℳ(p(g)) or (2) p(g) is not a speciation node and ℳ(g) ≠ ℳ(p(g)),  introduce a new node h and replace edge (p(g), g) with the pair of edges (p(g), h) and (hg) and define ℳ(h) = p(ℳ(g)). This process is repeated until there exists no node g that satisfies the conditions above. Wu et al. stipulate that the species map is defined first, then implicit speciation nodes are added as required, and finally the locus map is defined on the vertices of the gene tree, which now includes any implied speciation nodes.

The set of gene nodes mapped to a given species node s is denoted nodes(s) = {g|g ∈ V(G);ℳ(g) = s}; bottoms(s) = {g|g ∈ nodes(sg ∈ L(G) ∨ ∀ g ∈ c(g), g ∉ nodes(s)} is the subset of nodes(s) whose children are mapped to descendants of s; and tops(s) = bottoms(p(s)).2 For any set A ⊂ V(G), let loci(A) = {|∃ g ∈ A s.t. = ℒ(g)} denote the set of loci present on all genes in set A.

Next, Wu et al. define duplication and loss events. A duplication event corresponds to the creation of a new locus while a loss event corresponds to a locus that is present at either the top of a species branch, or created via a duplication within the species branch, but no longer present at the bottom of the species branch. More precisely, these events are defined as follows:

Definition 2

(Duplication and Loss Events) Let G, S, and Le denote a gene tree, species tree, and leaf map Le:L(G) → L(S), respectively, and let (, 𝕃, ) be a LCT for (GSLe).

  • Duplication events: Let g ∈ V(G), g ≠ r(G). If ℒ(g) ≠ ℒ(p(g)) then g induces a duplication event on the edge e(g) = (p(g), g).
  • Loss events: Let s ∈ V(S), s ≠ r(S). A locus  ∈ 𝕃 induces a loss event on edge e(s) = (p(s), s) if  ∈ loci(tops(s) ∪ nodes(s))\loci(bottoms(s)).

Figure 1 shows a (a) gene tree, (b) species tree, and (c) a species map and locus map with a duplication event. Figure 2 shows a subtree of a gene tree and a subtree of a species tree with the species and locus maps inducing multiple loss events.

Fig. 1
a A species tree and a b gene tree with the leaf map indicated by solid, dashed, and dotted lines. c A species and locus map for these two trees where circular nodes correspond to gene nodes in the gene tree and the rectangular node g is an implied ...
Fig. 2
A part of a gene tree mapped onto a species tree. Circular nodes correspond to gene nodes in the gene tree and rectangular nodes g and g′′ correspond to implied speciation nodes. The two loci are indicated in solid red and dashed blue. There is a loss ...

Definition 3

(Reconciliation Cost) Given gene tree G, species tree S, leaf map Le:L(G) → L(S), and non-negative real number costs Cd and C for duplication and loss events, respectively, the cost of a LCT for (GSLe) with d duplications events and loss events is dCdC.

Definition 4

(DCL Optimization Problem (DCLOP)) Given gene tree G, species tree S, leaf map Le:L(G) → L(S), and non-negative costs Cd and C for duplication and loss events, find a LCT for (GSLe) of minimum cost.

Definition 5

(DCL Decision Problem (DCLDP)) Given gene tree G, species tree S, leaf map Le:L(G) → L(S), non-negative costs Cd and C for duplication and loss events, and non-negative decision parameter k, does there exist a LCT for (GSLe) of cost at most k?

Duplication placement

Duplication events are determined entirely by the locus map whereas loss events depend on both the species map and the locus map. For convenience in our subsequent analyses, we give an alternate characterization of the locus map and prove its equivalence with the original definition.

Definition 6

(Duplication Placement) Given gene tree G, species tree S, and leaf map Le:L(G) → L(S), a duplication placement is a subset D of the edges of G such that for every pair of leaves gg ∈ L(G) where g ≠ g, if Le(g) = Le(g) then D contains an edge that separates g and g.

Theorem 1

Given gene tree G, species tree S, and leaf map Le:L(G) → L(S), for every locus map in a LCT inducing d duplication events, there exists a duplication placement D such that |D| = d. Conversely, for every duplication placement D such that |D| = d, there exists a locus map that induces exactly d duplications.

Proof

Let be a locus map for (GSLe) and define D to be the set of all edges e(g) = (p(g), g), g ∈ V(G), such that there is a duplication on edge e(g). By definition, |D| is the number of duplication events induced by . To show that D is a duplication placement, consider any pair of leaves gg ∈ L(G) where g ≠ g and Le(g) = Le(g). By Definition 1 (3), ℒ(g) ≠ ℒ(g). Let P denote the path from lca(gg) to g and let P denote the path from lca(gg) to g. There must exist some edge (p(u), u) in P ∪ P such that ℒ(u) ≠ ℒ(p(u)) since otherwise every node in P and P is mapped to the same locus, contradicting the assumption that ℒ(g) ≠ ℒ(g). Therefore, there is necessarily a duplication event on an edge in P ∪ P; this edges separates g and g and thus D is a duplication placement.

Conversely, let D be a duplication placement and consider the set S(D) = {G1, …, G|D|+1} comprising the |D| + 1 subgraphs of G induced by the removal of the edges of D from G. Note that S(D) partitions the nodes V(G). Let 𝕃 = {1, …, |D| + 1} and let map all nodes in Gi to i ∈ 𝕃. It follows directly that this satisfies the requirements of a locus map in Definition 1 (3), (4), (5).

Henceforth, we use locus maps and duplication placements interchangeably. When defining a duplication placement D, we say that a duplication is placed on an edge (uv) to mean that edge (uv) is included in the set D. We say that a duplication is placed between two leaves g and g to mean that there is a duplication placed on some edge that separates g and g.

3SAT

Our reductions will be from 3SAT [8]: Given m Boolean variables x1, …, xm and n clauses C1, …, Cn where each clause is the disjunction of exactly three literals over the given set of variables, we wish to determine whether there exists a valuation of the variables such that all clauses are satisfied. Without loss of generality, each literal occurs at most once per clause. In addition, the literals in the clauses are assumed to be ordered so that we may uniquely refer to the hth literal of each clause, 1 ≤ h ≤ 3. Since the clauses are ordered, we may also uniquely refer to the qth occurrence of a literal xi (or x¯i) in the 3SAT instance. Finally, without loss of generality, we assume that no clause contains both a literal and its negation (since such clauses are trivially satisfied by every valuation and can thus be removed).

NP-hardness

We show that DLCDP is NP-hard, even when loss events have cost zero, by a reduction from 3SAT. To provide intuition, we begin with a small example of the reduction and sketch the proof of correctness. Afterwards, we formalize the reduction and prove its correctness.

Figure 3 shows the construction for the 3SAT instance comprising a single clause, (x1x¯2x3). We construct a gene tree with a single clause gadget on the left and one variable gadget for each of x1x2 and x3 on the right. The variable gadget for variable xi is a subtree rooted at node xi. That node has a true branch and a false branch, corresponding to setting that variable true or false, respectively. The nodes at the end of the true and false branches each have two children, resulting in four leaves for each variable gadget. (In general, variable gadgets can be larger than this, with size dependent on the number of clauses in which xi appears). One leaf on the true side and one leaf on the false side of the variable gadget get mapped to the same species tree leaf, as represented by the dashed rectangles at the bottom right of Fig. 3 and labeled 1, 2, and 3 for x1, x2, and x3, respectively. Since each of these pairs of leaves are paralogs mapped to the same species leaf, there must be a duplication placed between them. As we shall see, our construction will force there to be a duplication on exactly one of the true or false branches incident on each xi, corresponding to setting each variable to true or false, respectively.

Fig. 3
A small example of the reduction for a single clause (x1x¯2x3)

Next, the gadget for clause 1 has five internal nodes (this is true in general, not just in this small example). The three important internal nodes are λ1,1, λ2,1, λ3,1 corresponding to the first, second, and third literals in clause 1. Each of these internal nodes has one leaf child that is mapped to a shared species leaf, as indicated in the dashed rectangle at the bottom left labeled A. Since the first literal in clause 1 is x1, clause node λ1,1 and the true node in the variable gadget for x1 each have a leaf child that is mapped to the same species node labeled B in the figure. Similarly, since the second literal of clause 1 is x¯2, clause node λ2,1 and the false node in the variable gadget for x2 each have a leaf child that is mapped to the same species node labeled C in the figure. Finally, λ3,1 and the true node in the x3 gadget have leaves on a shared species node D. All remaining leaves in the variable gadgets are mapped to their own individual unshared species leaves, placing no constraints on their locus mappings.

We set the cost of duplication events, Cd, to 1 and the cost of loss events, C, to 0. We set the decision parameter in this example to 5 which will force two duplications to be used in the clause gadget and one to be used in each of the three variable gadgets in a way that corresponds to choosing a valuation for the three variables (in general, the decision parameter for the number of duplications will be equal to the number of variables plus twice the number of clauses).

As noted earlier, the variable gadget leaves mapped to species 1, 2, and 3 require that there be at least one duplication placed within each variable gadget. Similarly, the three clause gadget leaves mapped to species A are paralogs and imply that there must be two duplications placed in the clause gadget rooted at δ1. Thus, in order to use no more than the five given duplications, there must be exactly one duplication placed in each variable gadget and exactly two duplications placed in the clause gadget. Moreover, without loss of generality, we can assume that duplications do not occur on edges terminating at leaves, since such duplications can be pushed up one level in the tree without violating any of the species map constraints.

We now sketch how the proof of correctness will proceed. First, assume that there is a satisfying assignment for the 3SAT instance (for example, x1 true, x2 true, x3 false). We place duplications on the corresponding edges in the variable gadgets. This satisfies the requirement that there exists a duplication placed between each pair of leaves associated with species 1, 2, and 3. Since, in our valuation, x1 true satisfies the clause, we choose not to place a duplication on the edge terminating at λ1,1 in the clause gadget, instead placing duplications on the two edges terminating at λ2,1 and λ3,1. This satisfies the requirement that a duplication is placed between each pair of the three clause leaves associated with species A. Moreover, the two leaves associated with species B have a duplication between them due to the duplication on x1’s true edge and the leaves associated with groups C and D have duplications between them due to the duplications placed on the edges terminating at λ2,1 and λ3,1.

To prove the converse direction, we assume a solution to the constructed DLCDP instance; as noted above, this implies that there exists one duplication placed in each variable gadget and two in the clause gadget. At least one duplication must be placed in the subtree rooted at δ1, as it is the lca of two leaves in group A. Therefore, only one of the three remaining internal edges in the subtree rooted at δ1 can contain a duplication. Thus, at least one of the pairs of leaves mapped to species B, C, or D cannot be separated by a duplication placed inside the clause gadget and thus must be separated by a duplication placed inside a variable gadget. Consider, for example, the case that the pair of leaves in group B is separated by an edge in a variable gadget. By construction, that duplication must then occur on the true side of the x1 gadget, which corresponds to setting x1 to be true in the valuation which, in turn, satisfies this 3SAT instance.

Formal reduction

Given a 3SAT instance with m variables x1x2, …, xm and n clauses C1C2, …, Cn, we construct an instance of DLCDP comprising m variable gadgets and n clause gadgets.

Variable gadgets

A variable gadget for variable xi, shown in Fig. 4, is a binary tree with root node αi which, in turn, has two children βi and β¯i which are roots of two subtrees. Node βi has two children: a leaf yi and an internal node βi,1. Each node βi,k has two children: a leaf yi,k and an internal node βi,k+1, 1 ≤ k < n - 1. Node βi,n-1 has two children: leaves yi,n-1 and yi,n. Similarly, node β¯i has a child labeled y¯i and another child β¯i,1. Each node β¯i,k has a child y¯i,k and a child β¯i,k+1, 1 ≤ k < n - 1. Node β¯i,n-1 has children y¯i,n-1 and y¯i,n.

Fig. 4
A variable gadget corresponding to variable xi

Clause gadgets

A clause gadget for clause Cj, shown in Fig. 5, is a binary tree rooted at node δj which in turn has children δj and λ3,j. Node δj has children λ1,j and λ2,j. Finally, each node λh,j has two leaf children, kh,j and kh,j, 1 ≤ h ≤ 3.

Fig. 5
A clause gadget corresponding to clause Cj

Gene tree

The gene tree is constructed by assembling m variable gadgets and n clause gadgets into a single binary tree. Specifically, the gene tree is constructed from an arbitrary binary tree with mn leaves. The first m leaves become the roots of m variable gadgets corresponding to variables x1, …, xm while the remaining n leaves become the roots of n clause gadgets corresponding to clauses C1, …, Cn.

Species tree

The species tree is an arbitrary binary tree with 2mnmn leaves labeled 1, …, 2mnmn.

Leaf map

We define Le:L(G) → L(S) as follows:

  1. Le(yi)=Le(y¯i)=i, 1 ≤ i ≤ m.
  2. Le(k1,j) = Le(k2,j) = Le(k3,j) = mj, 1 ≤ j ≤ n,
  3. For each xi appearing as the h-th literal in clause Cj, Le(kh,j)=Le(yi,j)=m+n+3(j-1)+h,
  4. For each x¯i appearing as the h-th literal in clause Cj, Le(kh,j)=Le(y¯i,j)=m+n+3(j-1)+h,
  5. Every leaf g ∈ L(G) whose mapping is not specified above is mapped to a unique species leaf s ∈ L(S) such no other gene leaf is mapped to s.

Note that steps 1 through 4 of this leaf map define the mapping of gene tree leaves onto species leaves 1, …, m + 4n. By construction, after these first four steps in the leaf map, there remain 2mn - 3n gene tree leaves that are not yet mapped and (2mnmn) - (m + 4n) = 2mn - 3n species tree leaves that are not yet mapped onto. Thus, in step 5 of the leaf map, every gene tree leaf whose mapping was not established in parts 1 through 4 can be mapped to a unique species tree leaf.

Event costs and decision parameter

We set the cost of a duplication event to be 1 and all other event costs to be 0. The decision parameter is 2nm, meaning in this case that we seek a reconciliation with at most 2nm duplications. It is easily seen that this reduction can be performed in time polynomial in the size of the given 3SAT instance.

Proof of correctness

3SAT  →  DLCDP

We first show that the existence of a satisfying valuation to a given 3SAT instance implies that the corresponding DLCDP instance is true. We prove this by constructing a duplication placement D of size 2nm as follows: For each literal xi, place a duplication on edge e(βi) = (αiβi) if xi is true in the valuation and place a duplication on edge e(β¯i)=(αi,β¯i) if xi is false. This ensures that all pairs of leaves yi and y¯i, 1 ≤ i ≤ m, are separated by an edge in D as required by part 1 of the leaf map above.

Next, consider an arbitrary clause Cj and one of the literals xi whose true valuation satisfies Cj (the case that the literal is x¯i is analogous). Without loss of generality, assume that xi is the first literal in clause Cj (the case that the literal is the second or third literal in the clause is analogous). The placement of a duplication on edge e(βi) ensures that leaves k1,j and yi,j are separated by an edge in D as required by part 3 (analogously, part 4) of the leaf map. Next, we place duplications on the edges e(λ2,j) and e(λ3,j) in the clause gadget for Cj. This separates all leaves in part 2 of the leaf map and separates the remaining leaves in parts 3 and 4. Part 5 of the leaf map has no leaves requiring separation by D.

Since all of the duplication requirements implied by the leaf map are satisfied by this duplication placement and it uses exactly k = 2nm duplications, this is a solution to the constructed DLCDP instance.

DLCDP  →  3SAT

Given a solution to the DLCDP instance, we construct a satisfying valuation for the corresponding 3SAT instance. Because part 1 of the leaf map associates each pair yi and y¯i, 1 ≤ i ≤ m, with the same species node, each such pair must be separated by an edge in D. By construction, each such pair must be separated by a distinct edge in the variable gadget for xi which is either an edge on the path from αi to yi or on the path from αi to y¯i. Separating all such pairs therefore requires m edges in D.

For each clause Cj, 1 ≤ j ≤ n, the leaves k1,jk2,j, and k3,j are mapped to the same species leaf by part 2 of the leaf map. Therefore, each pair of those leaves must be separated by an edge in D and, by the construction of the clause gadget, this requires two edges in each clause gadget and thus a total of 2n additional edges in D.

Thus, all k = 2nm are required to satisfy parts 1 and 2 of the leaf map, with exactly m edges selected from the variable gadgets and exactly 2n edges from the clause gadgets.

We construct a valuation of the boolean variables in the 3SAT instance as follows: for 1 ≤ i ≤ m, set xi to true if there is a duplication placed on some edge on the path from αi to yi, and set xi to false if there is a duplication along the path from αi to y¯i.

Consider an arbitrary clause Cj and its corresponding gadget in the gene tree. Part 2 of the leaf map requires that there be an edge in D separating each pair of of k1,j, k2,j, and k3,j, but, as noted above, only two edges of D are placed within that clause gadget. Since δj is the lca of k1,j and k2,j, at least one duplication must be placed in the subtree rooted at δj. Therefore, at least one of the three paths from δj to k1,j, k2,j, and k3,j does not contain an edge in D. Without loss of generality, assume that the path from δj to k1,j does not contain an edge in D and let xi be the first literal in clause Cj (the argument is analogous if xi is the second or third literal of the clause). Then, by part 3 (analogously, part 4) of the leaf map, k1,j and yi,j must be separated by an edge in D. Since this edge occurs in the variable gadget for xi, by the observations above it must occur on the path from αi to yi, resulting in setting xi true and thereby satisfying clause Cj.

Thus, all clauses are satisfied and the 3SAT instance is satisfiable.

APX-hardness of the DLC parsimony problem

When only the duplication cost is considered, the DLC optimization problem, DLCOP, can be approximated arbitrarily well using the polynomial-time approximation scheme (PTAS) for Multicut in binary trees [4] since duplications correspond exactly to removed edges in the Multicut problem. However, we now show that DLCOP has no PTAS in general, unless P = NP. Specifically, we show that DLCOP is APX-hard when duplications and losses are considered. We establish this result by a polynomial-time reduction from max3sat(b) which comprises a Boolean formula in 3-CNF form in which each variable appears at most B times in the clauses. Arora [9] showed that, for some ϵ, 0 < ϵ < 1, there exists a constant value of B (B = 13) and a polynomial-time reduction from any NP-complete problem Π to max3sat(b) that maps yes instances of Π to satisfiable instances of max3sat(b) and no instances of Π to instances of max3sat(b) in which less than 1 - ϵ of the total number of clauses are satisfiable.

Our reduction maps an instance of max3sat(b) with n clauses (for sufficiently large values of n) to an instance of DLCOP and a parameter b such that the optimal solution to the DLCOP instance is less than b if the max3sat(b) instance is satisfiable and more than (1 + α)b if at most (1 - ϵ)n clauses can be satisfied, for some constant α > 0. If a polynomial-time (1 + α)-approximation algorithm exists for DLCOP, we can apply our gap-preserving reduction to generate a DLCOP instance from the max3sat(b) instance and then run the putative approximation algorithm to distinguish between satisfiable and (1 - ϵ)-satisfiable instances of max3sat(b). Thus, the existence of a (1 + α)-approximation algorithm for DLC implies that PNP, and the approximation-hardness of DLCOP follows.

Reduction

Given an instance of max3sat(b) comprising m variables and n clauses, we construct an instance of DLCOP comprising a gene tree, a species tree, a leaf map, and event costs. The reduction is based on the NP-hardness reduction in the previous section but introduces more complex gadgetry and uses nonzero cost for loss events.

Thorn gadget

An -thorn gadget, depicted in Fig. 6, is a binary tree with leaves constructed as follows: let the root node be u1. Each node ui has two children: internal node ui+1 and leaf ti, 1 ≤ i ≤  - 2. Node u-1 has two leaf children t-1 and t. Leaf t is denoted the end tip of the thorn gadget.

Fig. 6
An -thorn gadget

Variable gadgets

Let B(i) and B¯(i) denote the number of occurrences of literals xi and x¯i, respectively. The variable gadget for variable xi, illustrated in Fig. 7, consists of a root node, αi, and two subtrees, one for each of the two literals of this variable. The left subtree has root βi, with two children: Internal node βi and leaf yi. In turn, βi has two children: Internal node βi,1 and leaf yi. Each node βi,q, 1 ≤ q ≤ B(i) - 2, has a child βi,q+1 and a second child which is the root of a (n2 - 1)-thorn gadget with end tip yi,q. Node βi,B(i)-1 has two children, each of which is the root of a (n2 - 1)-thorn gadget. The end tips of these thorn gadgets are labeled yi,B(i)-1 and yi,B(i). This construction introduces a distinct (n2 - 1)-thorn gadget for each occurrence of xi in the 3SAT instance. We refer to the thorn gadget terminating at end tip yi,q as the thorn gadget for the qth occurrence of xi. The right subtree of αi, representing literal x¯i, is symmetric to the left subtree, but with βi and βi replaced with β¯i and β¯i, respectively, each βi,j replaced by β¯i,j, and each yi,j replaced by y¯i,j. This construction introduces a distinct (n2 - 1)-thorn gadget for each clause containing x¯i. We refer to the thorn gadget terminating at end tip y¯i,q as the thorn gadget for the qth occurrence of x¯i.

Fig. 7
A gene tree variable gadget corresponding to variable xi

Clause gadgets

A clause gadget corresponding to clause Cj, shown in Fig. 8, consists of root node δj with children δj and λ3,j. Node δj has two children λ1,j and λ2,j. Each node λh,j, 1 ≤ h ≤ 3, is the root of a tree with two children, a leaf kh,j and a node λh,j, which in turn has two leaf children kh,j and kh,j.

Fig. 8
A gene tree clause gadget corresponding to clause Cj

Gene tree

The gene tree G is constructed as follows: the root of the gene tree is a node g0 with children g1 and g2. Node g1 is the root of a (3nm + 1)-thorn gadget. Node g2 is the root of an arbitrary binary subtree with nm leaves. Each of the first n of those leaves becomes the root of a clause gadget for clauses C1, …, Cn and the remaining m leaves become the roots of m variable gadgets for variables x1, …, xm.

Species tree

The species tree, shown in Fig. 9, is rooted at node ρ0 and is constructed from a path ρ0, …, ρ2m followed by σ1,σ1,,σn,σn, and finally τ1,1τ2,1τ3,1, …, τ1,nτ2,nτ3,n. This path is henceforth referred to as the trunk of the tree. Each node ρi has a leaf child ri, 1 ≤ i ≤ 2m, and each node σj and σj has a leaf child sj and sj, respectively, 1 ≤ j ≤ n. Finally, each node τh,j, which corresponds the hth literal in clause Cj, has a child that is the root of a n2-thorn with end tip th,j (henceforth referred to as the n2 -thorn for τh,j), 1 ≤ h ≤ 3, 1 ≤ j ≤ n. Node τ3,n has an additional leaf child so that the tree is binary.

Fig. 9
The species tree

Leaf map and event costs

The leaf map Le is defined as follows:

  1. Le(yi)=Le(y¯i)=r2i-1 and Le(yi)=Le(y¯i)=r2i, 1 ≤ i ≤ m;
  2. Le(k1,j) = Le(k2,j) = Le(k3,j) = sj and Le(k1,j)=Le(k2,j)=Le(k3,j)=sj, 1 ≤ j ≤ n;
  3. Each leaf in the (3nm + 1)-thorn gadget rooted at node g1 is mapped to r0;
  4. If the hth literal of Cj is xi and this is the qth occurrence of xi in the 3SAT instance, then each leaf of the (n2 - 1)-thorn gadget for the qth occurrence of xi is mapped to the leaf with the same index in the n2-thorn gadget for τh,j and kh,j is mapped to the end tip, th,j, of that n2-thorn gadget.
  5. If the hth literal of Cj is x¯i and this is the qth occurrence of x¯i in the 3SAT instance, then each leaf of the (n2 - 1)-thorn gadget for the qth occurrence of x¯i is mapped to the leaf with the same index in the n2-thorn gadget for τh,j and kh,j is mapped to the end tip, th,j, of that n2-thorn gadget.

Let the event costs be as follows: D = 2Bn2L = 1, C = 0. Finally, note that this reduction can be performed in polynomial time.

Proof of correctness

To prove the correctness of our reduction, we show that:

  • If the max3sat(b) instance is satisfiable, the optimal cost of the constructed DLC instance is less than
    b = (10B + 2)n3 + 121n2
  • For sufficiently large n, if at most (1 - ϵ)n clauses of the max3sat(b) instance can be satisfied, the optimal cost is more than (1 + α)b, where
    α=ϵ20B+4

Satisfiable MAX3SAT(B) instances

We first consider a satisfiable instance of max3sat(b). We show how a satisfying valuation can be used to construct a solution to the DLC instance whose cost is less than b.

The species map maps all internal nodes of G to ρ0 except for g1 and its descendant (3nm + 1)-thorn gadget which are mapped to r0; each leaf g ∈ L(G) is mapped to Le(g).

For each variable xi, we place one duplication in the corresponding variable gadget, on the edge e(β¯i) if xi is assigned true and on the edge e(βi) if xi is assigned false.3 This ensures that yi and y¯i are separated and that yi and y¯i are separated, as required by part 1 of the leaf map. For each clause Cj, identify any one literal that satisfies that clause. If the first literal in Cj satisfies the clause, place duplications on edges e(λ2,j) and e(λ3,j). Alternatively, if the second literal in Cj satisfies the clause, place duplications on edges e(λ1,j) and e(λ3,j); alternatively, if the third literal in Cj satisfies the clause, place duplications on edges e(λ1,j) and e(λ2,j). This placement of two duplications per clause gadget satisfies the constraints implied by part 2 of the leaf map, which requires that each pair of k1,jk2,jk3,j be separated and that each pair of k1,j,k2,j,k3,j be separated. Thus far, m + 2n duplications have been placed. Finally, we place 3nm duplications on the terminal edges of the (3nm + 1)-thorn gadget, since all 3nm + 1 of its leaves are mapped to r0 by part 3 of the leaf map and thus each pair of leaves must be separated. Note that parts 4 and 5 of the leaf mapping do not map multiple species leaves to the same trees leaves and thus require no additional duplication placements. The total number of duplications is thus m + 2n + (3nm) = 5n.

Next, we count the number of losses. We do this by first counting losses on the n2-thorns of the species tree and then on the trunk of the species tree.

Each clause Cj has three n2-thorns in the species tree, one branching from each of τ1,j, τ2,j, and τ3,j. Without loss of generality, assume that clause Cj is satisfied by its first literal and thus duplications were placed on e(λ2,j) and e(λ3,j). Also, without loss of generality, assume that the first literal in Cj is xi (the case for x¯i is analogous) and that this is the qth occurrence of xi in the 3SAT instance. The duplication on e(λ2,j) implies that leaf k2,j is mapped to a different locus than all of the leaves of the (n2 - 1)-thorn for the qth occurrence of xi in the variable gadget for xi. Since Le(k2,j)=t2,j by part 4 of the leaf map, there is a loss event on each of the n2 edges terminating at the leaves of the n2-thorn gadget for τ2,j. Similarly, the duplication on edge e(λ3,j) incurs n2 losses in the n2-thorn gadget for τ3,j for a total of 2n2 losses for clause Cj. Since Cj is satisfied by xi, we know that xi true and thus a duplication was placed on edge e(β¯i) in the variable gadget for xi. Therefore, there is no duplication placed between k1,j and the leaves of the (n2 - 1)-thorn for the qth occurrence of xi and thus there are no losses incurred on the n2-thorn for τ1,j. Since there are n clauses and each contributes 2n2 losses in the corresponding n2-thorns, 2n3 losses are incurred thus far.

We next consider the number of losses incurred on the trunk of the species tree. Since ℳ(g1) = r0, none of the loci created by the 3nm duplications in the 3nm + 1-thorn required by part 3 of the leaf map induce loss events. There are 1 + 2m + 2n + 3n nodes on the trunk and at most m + 2n loci can be lost on each of the two edges emanating from each such node since there only m + 2n other duplications.

Observing that m ≤ 3n, the total number of losses can thus be bounded from above by

2(m+2n)(1+2m+2n+3n)2·5n·12n<121n2.

Therefore, the total cost of this solution is bounded by

5n · 2Bn2 + (2n3 + 121n2) · 1 = (10B + 2)n3 + 121n2b.

At most (1-ϵ)-satisfiable MAX3SAT(B) instances

To complete the proof, we show that given an instance of max3sat(b) in which the fraction of satisfiable clauses is at most (1-ϵ), the optimal cost of the corresponding DLC instance, for sufficiently large n, is greater than:

(1+α)b=1+ϵ20B+4(10B+2)n3+121n2=(10B+2)n3+ϵ20B+4(10B+2)n3+1+ϵ20B+4121n2=(10B+2)n3+ϵ2n3+1+ϵ20B+4121n2=10B+2+ϵ2n3+1+ϵ20B+4121n2.

Part 1 of the leaf map requires at least one duplication placement per variable gadget, part 2 of the leaf map requires at least two duplications per clause gadget, and part 3 of the leaf map requires 3nm duplications to be placed in the (3nm + 1)-thorn gadget. Therefore, all valid duplication placements for this instance use at least m + 2n + (3nm) = 5n duplications. We call a solution that uses exactly 5n duplications well-behaved.

A well-behaved solution must use exactly one duplication in each variable gadget. For each variable gadget for variable xi, this duplication must be placed on either the edge e(βi) or the edge e(β¯i) in order to separate both yi and y¯i and yi and y¯i. We interpret a duplication on edge e(βi) as setting variable xi to false and a duplication on edge e(β¯i) as setting xi to true. Thus, a well-behaved solution to the DLC Optimization Problem has a corresponding valuation of the variables in the 3SAT instance.

We now show that all optimal solutions to the DLC Optimization Problem are necessarily well-behaved. Consider a solution for our constructed DLC instance that is not well-behaved and thus comprises more than 5n duplications. A duplication placed outside of a variable, clause, or (3nm + 1)-thorn gadget cannot satisfy any of the duplication requirements imposed by the leaf map and thus can be removed, reducing the number of duplications and not increasing the number of losses.

If a variable gadget for xi contains more than one duplication, we may replace all duplications in that variable gadget with a single duplication on edge e(βi) = (αiβi), which satisfies the duplication requirements of the leaf map and reduces the number of duplications by at least one. Introducing a new duplication may increase the number of losses. However, since each variable xi appears in at most B clauses in the max3sat(b) instance, the number of new losses introduced can be at most Bn2 due to the B n2-thorn gadgets where losses are introduced and the O(n) internal vertices in the trunk of the species tree, which is dominated by Bn2 for sufficiently large n. Thus, the total number of new losses incurred is less than 2Bn2 for sufficiently large n and thus less than the cost of the saved duplication.

Similarly, if a clause gadget for Cj contains more than two duplications, we can replace it with two duplications on the edges e(λ1,j) and e(λ2,j). The saving of one duplication is larger than the cost of the additional losses.

We have established that an optimal solution to the constructed DLC instance is necessarily well-behaved. Next, observe that any species map must map λh,j, 1 ≤ h ≤ 3, 1 ≤ j ≤ n, to a node v on the trunk of the species tree such that vTτh,j since λh,j has children kh,j and kh,j and Le(kh,j)=sj while Le(kh,j)=th,j.

Consider an optimal solution for the DLC instance. Since this solution is well-behaved, it induces a valuation of the Boolean variables as described above. As noted earlier, if clause Cj is satisfied by this valuation then a total of 2n2 losses are incurred in two of the three n2-thorns τ1,j, τ2,j, and τ3,j. Conversely, if clause Cj is not satisfied by this valuation then a total of 3n2 losses are incurred in all three of those n2-thorns. To see this, let the hth literal, 1 ≤ h ≤ 3, of Cj be xi (analogously, x¯i) and let this be the qth occurrence of this literal in the 3SAT instance. Since Cj is not satisfied xi false [analogously, x¯i= false and, therefore, there is a duplication placed on edge e(βi) (analogously, e(β¯i)]. It follows that the loci of the leaves of the (n2 - 1)-thorn for the qth occurrence of xi are different from the locus of kh,j, causing n2 losses in the n2-thorn for τh,j since, as noted above, the path from M(λh,j) to M(kh,j)=th,j passes through every internal node of this thorn gadget. Thus, if Cj is unsatisfied, its three n2-thorns in the species tree contribute 3n2 losses.

We have shown that every satisfied clause contributes 2n2 losses and every unsatisfied clause contributes 3n2 losses. Therefore, if there are fewer than 2n3ϵn3 losses then there must be fewer than ϵn unsatisfied clauses. Since there are more than ϵn unsatisfied clauses by assumption, for sufficiently large n, the cost of a well-behaved solution, and thus of an optimal solution, is at least:

5n(2Bn2)+2n3+ϵn3=(10B+2+ϵ)n3>10B+2+ϵ2n3+1+ϵ20B+4121n2=(1+α)b

Conclusion

We have shown that the DLC parsimony problem is NP-hard even when only duplications are considered and APX-hard when duplications and losses are considered. These results may help guide the direction of future research on algorithms and heuristics for the DLC parsimony problem. In particular, although the existence of a polynomial-time approximation scheme for the DLC parsimony problem would imply that P = NP, approximation algorithms may exist and would be of significant potential value.

Authors' contributions

All authors contributed to the development of the results and writing of this paper. All authors read and approved the final manuscript.

Acknowlegements

The authors wish to thank Yi-Chieh Wu and Mukul Bansal for valuable advice and feedback.

Competing interests

The authors declare that they have no competing interests.

Funding

This work was funded by the U.S. National Science Foundation under Grant Number IIS-1419739. Any opinions, findings, and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the National Science Foundation.

Footnotes

1Wu et al. include one other relation in the LCT, a partial ordering relation 𝒪 on V(G). This relation is used solely to define and count the number of so-called coalescence events. In this paper, we show that the reconciliation problem is intractable even when the cost of coalescence events is ignored. Therefore, while coalescence events are induced by the LCT, there is no need to explicitly identify these events here and we thus omit the partial ordering relation 𝒪 from the above definition.

2Wu et. al use the names leaves and roots where we use bottoms and tops, respectively.

3Note that this is opposite of what was done in the preceeding NP-hardness proof. This switch is necessary as becomes evident in the subsequent proof of correctness.

Contributor Information

Daniel Bork, ude.cmh.g@krobd.

Ricson Cheng, ude.umc.werdna@cnoscir.

Jincheng Wang, ude.cmh.g@gnawij.

Jean Sung, ude.cmh.g@gnusj.

Ran Libeskind-Hadas, ude.cmh.sc@sadah.

References

1. Kingman JFC. The coalescent. Stoch Process Appl. 1982;13(3):235–248. doi: 10.1016/0304-4149(82)90011-4. [Cross Ref]
2. Rasmussen M, Kellis M. Unified modeling of gene duplication, loss, and coalescence using a locus tree. Genome Res. 2011;22:755–765. doi: 10.1101/gr.123901.111. [PubMed] [Cross Ref]
3. Wu Y-C, Rasmussen MD, Bansal MS, Kellis M. Most parsimonious reconciliation in the presence of gene duplication, loss, and deep coalescence using labeled coalescent trees. Genome Res. 2014;24(3):475–486. doi: 10.1101/gr.161968.113. [PubMed] [Cross Ref]
4. C-ălinescu G, Fernandes CG, Reed B. Multicuts in unweighted graphs and digraphs with bounded degree and bounded tree-width. J Algorithm. 2003;48(2):333–359. doi: 10.1016/S0196-6774(03)00073-7. [Cross Ref]
5. Bansal MS, Alm EJ, Kellis M. Efficient algorithms for the reconciliation problem with gene duplication, horizontal transfer and loss. Bioinformatics. 2012;28(12):283–291. doi: 10.1093/bioinformatics/bts225. [PMC free article] [PubMed] [Cross Ref]
6. Ovadia Y, Fielder D, Conow C, Libeskind-Hadas R. The cophylogeny reconstruction problem is NP-complete. J Comput Biol. 2011;18(1):59–65. doi: 10.1089/cmb.2009.0240. [PubMed] [Cross Ref]
7. Tofigh A, Hallett MT, Lagergren J. Simultaneous identification of duplications and lateral gene transfers. IEEE/ACM Trans Comput Biol Bioinform. 2011;8(2):517–535. doi: 10.1109/TCBB.2010.14. [PubMed] [Cross Ref]
8. Garey MR, Johnson DS. Computers and intractability: a guide to the theory of NP-completeness. New York: W. H. Freeman & Co.; 1979.
9. Arora S. Probabilistic checking of proofs and hardness of approximation problems. Ph.D. Thesis, Princeton: Princeton University, Department of Computer Science; 1994

Articles from Algorithms for Molecular Biology : AMB are provided here courtesy of BioMed Central