Gaëlle Brevier

Romeo Rizzi
email: romeo.rizzi@dimi.uniud.it

Stéphane Vialette
email: vialette@univ-mlv.fr

Pattern Matching in Protein-Protein Interaction Graphs

In the context of comparative analysis of protein-protein interaction graphs, we use a graph-based formalism to detect the preservation of a given protein complex (pattern graph) in the protein-protein interaction graph (target graph) of another species with respect to (w.r.t.) orthologous proteins. We give an efficient exponential-time randomized algorithm in case the occurrence of the pattern graph in the target graph is required to be exact. For approximate occurrences, we prove a tight inapproximability results and give four approximation algorithms that deal with bounded degree graphs, small ortholog numbers, linear forests and very simple yet hard instances, respectively.

Introduction

High-throughput analysis makes possible the study of protein-protein interactions at a genome-wise scale [GB + 02,HG + 02,UG + 00], and comparative analysis tries to determine the extent to which protein networks are conserved among species. Indeed, mounting evidence suggests that proteins that function together in a pathway or a structural complex are likely to evolve in a correlated fashion, and, during evolution, all such functionally linked proteins tend to be either preserved or eliminated in a new species [PMT + 99].

Protein interactions identified on a genome-wide scale are commonly visualized as protein interaction graphs, where proteins are vertices and interactions are edges [START_REF] Titz | What do we learn from highthroughput protein interaction data?[END_REF]. Experimentally derived interaction networks can be extremely complex, so that it is a challenging problem to extract biological functions or pathways from them. However, biological systems are hierarchically organized into functional modules. Several methods have been proposed for identifying functional modules in protein-protein interaction graphs. As observed in [START_REF] Pereira-Leal | Detection of functional modules from protein interaction networks[END_REF], cluster analysis is an obvious choice of methodology for the extraction of functional modules from protein interaction networks. Comparative analysis of protein-protein interaction graphs aims at finding complexes that are common to different species. Kelley et al. [KSK + 03] developed the program PathBlast, which aligns two protein-protein interaction graphs combining topology and sequence similarity. Sharan et al. [SIK + 04] studied the conservation of complexes (they focused on dense, clique-like interaction patterns) that are conserved in Saccharomyces cerevisae and Helicobacter pylori, and found 11 significantly conserved complexes (several of these complexes match very well with prior experimental knowledge on complexes in yeast only). They actually recasted the problem of searching for conserved complexes as a problem of searching for heavy subgraphs in an edge-and node-weighted graph, whose vertices are orthologous protein pairs. A promising computational framework for alignment and comparison of more than one protein network together with a three-way alignment of the protein-protein interaction networks of Caenorhabditis elegans, Drosophila melanogaster and Saccharomyces cerevisae is presented in [SSK + 04].

In [START_REF] Fagnot | Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs[END_REF], this pattern matching problem was stated as the problem of finding an occurrence of a pattern graph G in a target graphs H w.r.t lists constraints (referred hereafter as the Exact-(ρ, σ)-Matching problem): to each vertex u of G is associated a lists L(u) of vertices in H and the occurrence of G in H is required to be an injective graph homomorphism φ from G to H such that φ(u) ∈ L(u) for each vertex u in G. The two parameters ρ and σ denote the maximum size of a list of G and the maximum number of occurrences of a vertex of H among the lists of G, respectively ; Roughly speaking, the rationale of this approach is as follows. First, graph homomorphism only preserves adjacency, and hence can deal with interaction datasets that are missing many true protein interactions. Second, injectivity is required in order to establish a bijective relationship between proteins in the complex and proteins in the occurrence. Finally, graph homomorphism with respect to orthologous links can be easily recasted as list homomorphism: a list of putative orthologs is associated to each protein (vertex) of the complex, and each such protein can only be mapped by the homomorphism to a protein occurring in its list. In the context of comparative analysis of protein-protein interaction graphs, drastic restrictions were imposed on the size of the lists. Some (classical and parameterized) hardness results together with several heuristics for the Exact-(ρ, σ)- Matching problem were presented in [START_REF] Fagnot | Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs[END_REF]. These results were improved in [START_REF] Fertin | Finding exact and maximum occurrences of protein complexes in protein-protein interaction graphs[END_REF]. Of particular importance in the context of computational biology, we investigated in [START_REF] Fertin | Finding exact and maximum occurrences of protein complexes in protein-protein interaction graphs[END_REF] the problem of finding approximate occurrences (the Max-(ρ, σ)-Matching problem), i.e., the injective mapping of G to H were no longer required to be a graph homomorphism but to match as many edges as possible.

Aiming at presenting accurate computational models, we combine here stateof-the art approaches to identifying orthologs (genes in different species that originate from a single gene in the last common ancestor of these species) for transferring functional information between genes in different organisms with a high degree of reliability [TKL97,RSS01] and the above mentioned line of research by considering additional structural constraints on the lists: for each distinct vertices u and v of G, either L(u) = L(v) or L(u) ∩ L(v) = ∅. The obtained problem is modeled by replacing lists by colors: to all vertices of G and H is associated a color and a vertex of G can only be mapped to a vertex of H with the same color. This paper is organized as follows. We briefly discuss in Section 2 basic notations and definitions that we will use throughout the paper. In Section 3 we give a randomized algorithm for finding an injective mapping w.r.t to the colorings that matches all the edges of the pattern graph. We prove in Section 4 that the problem of finding an injective mapping w.r.t to the colorings that matches as many edges of the pattern graph as possible is hard to approximate even if both the pattern graph and the target graph are linear forests or trees. Section 5 is devoted to approximation with a focus on three restricted but still hard cases: (i) the pattern graph or the target graph has bounded degree, (ii) the number of occurrences of each color in the target graph is considered to be small, (iii) both the pattern graph and the target graphs are linear forests and (iv) each color occurs two times in both G and H. Section 6 concludes our word and propose future directions of research.

Preliminaries

We assume readers have basic knowledge about graph theory [START_REF] Diestel | Graph theory[END_REF] and we shall thus use most conventional terms of graph theory without defining them (we only recall basic notations). Let G be a graph. We write V(G) for the set of vertices and E(G) for the set of edges. Also, we write n(G) for |V(G)| and m(G) for |E(G)|. The maximum degree ∆(G) of a graph G is the largest degree over all vertices. A graph is called a linear forest if every component is a path. Let G be a graph together with a coloring λ : V(G) → C of its vertices. For any color c i ∈ C, we denote by C G (c i ) the set of vertices of G that are colored with color c i , i.e.,

C G (c i ) = {u ∈ V(G) : λ(u) = c i }.
The multiplicity of λ in G, written mult(G, λ), is the maximum number of occurrences of a color in G, i.e., mult(G, λ) = max{|C G (c i )| : c i ∈ C}. Let G and H be two graphs and let θ : V(G) → V(H) be an injective mapping. The set of edges of G that are preserved in H by θ is written match(G, H, θ), i.e., match(G, H, θ) = {{u, v} ∈ E(G) : {θ(u), θ(v)} ∈ E(H)}. If both G and H are equipped with some colorings λ G : V(G) → C and λ H : V(H) → C of their vertices, a mapping θ : V(G) → V(H) is said to be with respect to (w.r.t.) λ G and λ H if λ G (u) = λ H (θ(u)) for every u ∈ V(G), i.e., θ is a color preserving mapping. For simplicity, we shall usually abbreviate such a mapping as θ :

V(G) λ G ,λ H ----→ V(H).
We are now in position to formally define the Max-(ρ, σ)-Matching-Colors problem we are interested in.

Max-(ρ, σ)-Matching-Colors

• Input : Two graphs G and H together with the coloring mappings λ

G : V(G) → C, mult(G, λ G ) = ρ, and λ H : V(H) → C, mult(H, λ H ) = σ. • Solution : An injective mapping θ : V(G) λ G ,λ H ----→ V(H).
• Measure : The number of edges of G matched by the injective mapping θ, i.e., |match(G, H, θ)|.

We designate by Exact-(ρ, σ)-Matching-Colors the extremal problem of finding an injective mapping θ :

V(G) λ G ,λ H ----→ V(H) that
matches all the edges of G, i.e., θ is required to be an injective graph homomorphism [START_REF] Fertin | Finding exact and maximum occurrences of protein complexes in protein-protein interaction graphs[END_REF]. Also, we call an instance of both the Max-(ρ, σ)-Matching-Colors and Exact-(ρ, σ)-Matching-Colors problems colorful if ρ = 1.

Let G, H, λ G , λ H be an instance of the Max-(ρ, σ)-Matching-Colors. First, a necessary and sufficient condition for an injective mapping to exist is

|C G (c i )| ≤ |C H (c i )| for each color c i ∈ C. Second, an edge {u, v} ∈ E(G), λ G (u) = c u and λ G (v) = c v , is called a bad edge if there does not exist distinct u ′ ∈ C H (c u ) and v ′ ∈ C H (c v ) such that {u ′ , v ′ } ∈ E(H).
Clearly, if we remove from G its bad edges, this does not affect the optimal solutions for the Max-(ρ, σ)- Matching-Colors problem, since bad edges can never be matched. Notice that we can tell bad edges apart in O(σ 2 m(G)) = O(m(G)) time, provided σ is a constant. Therefore, throughout the paper, we will consider only trim instances as defined in the following.

Definition 1 (Trim instance) An instance G, H, λ G , λ H of the Max-(ρ, σ)-Matching-Colors or the Exact-(ρ, σ)-Matching-Colors problem is said to be trim if the following conditions hold true: (i) for each color

c i ∈ C, |C G (c i )| ≤ |C H (c i )|, and (ii) for each edge {u i , u j } ∈ E(G), there exists an edge {v i , v j } ∈ E(H) such that λ G (u i ) = λ H (v i ) and λ G (u j ) = λ H (v j ).

Exact colorful instances

This section is devoted to the Exact-(1, σ)-Matching-Colors problem. On the one hand, both the Exact-(1, σ)-Matching-Colors problem for ∆(G) ≤ 2 and the Exact-(ρ, 2)-Matching-Colors problem are polynomial-time solvable for any constant ρ and σ [START_REF] Fagnot | Bounded list injective homomorphism for comparative analysis of protein-protein interaction graphs[END_REF]. On the other hand, the Exact-(1, 3)- Matching-Colors problem for ∆(G) = 3 and ∆(H) = 4 is NP-complete [START_REF] Fertin | Finding exact and maximum occurrences of protein complexes in protein-protein interaction graphs[END_REF]. We first observe that the Exact-(1, σ)-Matching-Colors problem is easily solvable in Õ(σ n(G) ) time: the brute-force algorithm tries all possible injective mappings θ : V(G) λ G ,λ H ----→ V(H) and returns the best one. We give a faster randomized algorithm (referred hereafter as Algorithm Rand-Exact-Matching-Colors) than runs in Õ(f (σ) n(G) ) expected time, where

f (σ) = 4σ(2σ -2) 3 4(2σ -2) 3 + 27(2σ -3)
. Observe that f (σ) < σ, for σ > 2. For the sake of illustration, f (3) < 2.279, f (4) < 3.460 and f (5) < 4.578.

We present here a random walk algorithm which is similar to [START_REF] Mitzenmacher | Probability and computing: Randomized algorithms and probabilistic analysis[END_REF]. For simplicity, we assume the worst case where each color occurs exactly σ times in graph H. The basic idea is to start with a random injective mapping θ, look at an edge e of G that is not matched by θ, select at random one end-vertex u of e and finally change at random the image of u, i.e., θ(u). Observe however that, oppositely to satisfiability-like algorithms where changing the assignment of a boolean variable in an unsatisfied clause result in a satisfied clause, the edge e might be here still not matched by the new injective mapping θ. The complete description of the alorithm is given as Algorithm Rand-Exact-Matching-Colors.

Let G, H, λ G , λ H be an arbitrary instance of the Exact-(1, σ)-Matching-Colors problem, and suppose that there exists an injective homomorphism

Rand-Exact-Matching-Colors( G, H, λ G , λ H ) Input: An instance G, H, λ G , λ H of the Exact-(1, σ)-Matching- Colors problem. Output: An occurrence of G in H, i.e., an injective homomorphism θ : V(G) λ G ,λ H ----→ V(H) (if such a mapping exists).
Repeat, terminating whether an occurrence of G in H w.r.t λ G and λ H is found:

• Let θ : V(G) λ G ,λ H ----→ V(H) be a random injective. • Loop up to 3 n(G) times, terminating whether an occurrence of G in H w.r.t λ G and λ H is found:
Choose at random an edge e ∈ E(G) that is not matched by θ, choose at random one vertex u ∈ e and change at random the value of θ(u) w.r.t λ G and λ H .

θ opt : V(G) λ G ,λ H ----→ V(H), i.e., G, H, λ G , λ H is a YES instance.
Without loss of generality we may assume that, for each color c i ∈ C, exactly σ vertices of H are colored with color c i (and hence H has σ|C| vertices). Fix any injective mapping θ :

V(G) λ G ,λ H ----→ V(H) and let θ i : V(G) λ G ,λ H ----→ V(H)
be the injective mapping after the i-th step of the inner loop of Algorithm Rand-Exact-Matching-Colors. Let X i be the number of vertices u ∈ V(G) such that θ i (u) = θ opt (u). If X i = n(G), Algorithm Rand-Exact-Matching-Colors terminates with an injective homomorphism. Clearly, the algorithm could terminate before X i = n(G) by finding a different injective homomorphism, but for our analysis the worst case is that the algorithm only stops when X i = n(G).

Suppose 1 ≤ X i ≤ n(G) -1. At each step, we choose an edge e = {u, v} ∈ E(G) that is not matched. Since G, H, λ G , λ H is a YES instance, θ i and θ opt disagree on at least one of u and v. Suppose first that θ i and θ opt disagree on exactly one of u and v. Then, the probability of increasing the number of agreements between θ opt and θ i+1 is (2σ -2) -1 , the probability of decreasing the number of agreements between θ opt and θ i+1 is (σ -1)(2σ -2) -1 and the probability of obtaining the same number of agreements between θ opt and θ i+1 is (σ -2)(2σ -2) -1 . Suppose now that θ i and θ opt disagree on both u and v. Then, the probability of increasing the number of agreements between θ opt and θ i+1 is 2(2σ -2) -1 , the probability of decreasing the number of agreements between θ opt and θ i+1 is 0 (θ i and θ opt indeed already both disagree on both vertices) and the probability of obtaining the same number of agreements between θ opt and θ i+1 is (2σ -4)(2σ -2) -1 . In the light of the above probabilities, let us thus consider the pessimistic stochastic process Y = (Y 1 , Y 2 , . . .) defined as follows:

Pr[Y i+1 = j + 1|Y i = j] ≥ 1 2σ -2 , Pr[Y i+1 = j -1|Y i = j] ≤ 2σ -3 2σ -2 .
This stochastic process is best understood by using the same metaphor as in [START_REF] Mitzenmacher | Probability and computing: Randomized algorithms and probabilistic analysis[END_REF]: consider a particle moving on the integer line, with probability (2σ -1) -1 of moving up by one and probability (2σ -3)(2σ -2) -1 of moving down by one. Observe that in the pessimistic stochastic process Y the particle never stays in place whereas the probability of obtaining the same number of agreements is non-zero in Algorithm Rand-Exact-Matching-Colors. Let r j be the probability of exactly k "moves down", and j + k "moves up" in a sequence of 2k + j moves. We have

r j ≥ 2σ -3 2σ -2 k 1 2σ -2 j+k
. Now, let q j be the probability that the algorithm finds an injective homomorphism within j + 2k ≤ 3 n(G) steps, starting from a random injective mapping θ :

V(G) λ G ,λ H ----→ V(H). Lemma 2 q j ≥ √ 3 8 √ πj 27(2σ -3) 4(2σ -2) 3 j .
PROOF. We first observe that r j is a lower bound for q j , and hence

q j ≥ max 0≤k≤j j + 2k k 2σ -3 2σ -2 k 1 2σ -2 j+k .
If we restrict ourselves to k = j, we obtain

q j ≥ 3j j 2σ -3 2σ -2 j 1 2σ -2 2j = 3j j 2σ -3 (2σ -2) 3 j .
Combining this with standard Stirling's approximation yields

q j ≥ √ 3 8 √ πj 27 4 j 2σ -3 (2σ -2) 3 j = √ 3 8 √ πj 27(2σ -3) 4(2σ -2) 3 j
and the lemma is proved. ✷ Let p j be the probability that a random injective mapping θ : V(G)

λ G ,λ H ----→ V(H) has j disagreements with θ opt . We now derive a lower bound for q, the probability that the process finds an occurrence of G in H w.r.t λ G and λ H in 3 n(G) steps starting from a random injective mapping.

Lemma 3 q ≥ √ 3 8 π n(G) 4(2σ -2) 3 + 27(2σ -3) 4σ(2σ -2) 3 n(G)
.

PROOF. By definition, we have q ≥ n(G)

j=0 q j p j ≥ 1 σ n(G) + n(G) j=1 q j p j .
Combining this with Lemma 2, we obtain

q ≥ 1 σ n(G) + n(G) j=1 n j 1 σ n(G) √ 3 8 √ πj 27(2σ -3) 4(2σ -2) 3 j ≥ √ 3 8 π n(G) 1 σ n(G) n(G) j=0 n j 27(2σ -3) 4(2σ -2) 3 j (1) n-j = √ 3 8 π n(G) 1 σ n(G) 1 + 27(2σ -3) 4(2σ -2) 3 n(G) = √ 3 8 π n(G) 4(2σ -2) 3 + 27(2σ -3) 4σ(2σ -2) 3 n(G)
.

✷

Therefore, if we assume that there exists an injective mapping θ :

V(G) λ G ,λ H ----→ V(H)
, the number of random injective mappings the process tries before finding an occurrence of G in H is a geometric random variable with parameter q. Hence, the expected of random injective mappings tried is q -1 , and for each injective mapping the algorithm uses at most 3 n(G) steps. Therefore, the expected number of steps until a solution is found is bounded by O(n(G) 3/2 f (σ) n(G) ). We have thus proved the following.

Proposition 4 Algorithm Rand-Exact-Matching-Colors returns an injective homomorphism θ : V(G) -3) . PROOF. We propose a L-reduction from the Max-2-Sat-3 problem (Given a set X of variables and a boolean formula φ in conjunctive normal form where clause consists in at most 2 literals and each variable appears in at most 3 clauses, find a truth assignment for X that satisfies as many clauses as possible) which is known to be APX-complete [START_REF] Papadimitriou | Optimization, approximation and complexity classes[END_REF]. We assume that each negated literal and each positive literal occurs at most twice, since otherwise a self-reduction would trivially apply. Let φ be an arbitrary input for the Max-2-Sat-3 problem. Let X = {x 1 , . . . , x n } denote the set of variables and C = {c 1 , . . . , c m } denote the set of clauses. For each j = 1, 2, . . . , m and each ℓ = 1, 2, we write c j [ℓ] for the ℓ-th literal of the clause c j . For each variable x i ∈ X, we let nb occ(x i ) stands for the number of occurrences of variable x i in φ (counting together both positive and negative occurrences); we may clearly assume here that 2 ≤ nb occ(x i ) ≤ 3 for each x i ∈ X (a self-reduction would trivially apply in case nb occ(x i ) = 1). We now describe how to construct the corresponding instance of the Max-(2, 2)-Matching-Colors problem.

λ G ,λ H ----→ V(H) (if such a mapping exists) in Õ(f (σ) n(G) ) time, where f (σ) = 4σ(2σ -2) 3 4(2σ -2) 3 + 27(2σ

Hardness results

Recall that the

Let us start by considering the associated graph G. We introduce two vertices

x G i [1] and x G i [2]
for each variable x i ∈ X, and one vertex c G j for each clause c j ∈ C. For each x i ∈ X, we introduce the edge {x G i [1], x G i [2]}. Also, for each clause c j and each ℓ ∈ {1, 2}, we introduce the vertex t

G i [k] (resp. f G i [k]) if the ℓ-th literal of clause c i is the k-th occurrence of positive (resp. negative) literal x i (resp. x i ) together with the edge {c G j , t G i [k]} (resp. {c G j , f G i [k]}).
We now turn to defining the corresponding graph H. For each variable x i ∈ X, we introduce four vertices

t H i [1], t H i [2], f H i [1] and f H i [2]
, and the two edges

{t H i [1], t H i [2]} and {f H i [1], f H i [2]}.
For each clause c j and each ℓ ∈ {1, 2}, we introduce the vertex c H j [ℓ] and the edge {c

H j [ℓ], t H i [k]} (resp. {c H j [ℓ], f H i [k]}
) if the ℓ-th literal of clause c i is the k-th occurrence of positive (resp. negative) literal x i (resp. x i ). Also, for each clause c j we introduce one isolated vertex c H i [3], and for each x i ∈ X we introduce two isolated vertices y H i [1] and

y H i [2]. Let C = {x i [ℓ] : 1 ≤ i ≤ n ∧ 1 ≤ ℓ ≤ 2} ∪ {c j : 1 ≤ j ≤ m} be our set of colors. Define the mapping λ G : V(G) → C by λ G (x G i [1]) = x i [1] for all x G i [1] ∈ V(G), λ G (x G i [2]) = x i [2] for all x G i [2] ∈ V(G), λ G (t G i [ℓ]) = x i [k] for all t G i [k] ∈ V(G), λ G (f G i [ℓ]) = x i [k] for all f G i [k] ∈ V(G), and λ G (c G i ) = c j for all c G j ∈ V(G). Also, define the mapping λ H : V(H) → C by λ H (t H i [k]) = x i [k] for all t H i [k] ∈ V(H), λ H (f H i [k]) = x i [k] for all f H i [k] ∈ V(H), λ H (c H j [k]) = c j for all c H j [k] ∈ V(H), and λ H (y H i [k]) = x i [k] for all y H i [k] ∈ V(H).
It is easily seen that both G and H are linear forests in which each color occurs at most three times. An illustration of this construction is given in Figure 1.

Let f be a truth assignment for X. Write A(φ, f ) the number of clauses of φ that are satisfied by f . Define an injective mapping θ : V(G)

λ G ,λ H ----→ V(H) as follows. For each x i ∈ X, if f (x i ) = true (resp. f (x i ) = false) then θ(x G i [k]) = f H i [k] (resp. θ(x G i [k]) = t H i [k]
). Now, let c j be any clause of φ and let z

G i [k] and z G i ′ [k ′ ],
z ∈ {t, f }, be the two vertices connected to vertex c G j . Suppose first that the clause c j is satisfied by its ℓ-th literal.

If ℓ = 1, then θ(c G j ) = c H j [ℓ], θ(z G i [k]) = z H i [k] and θ(z G i ′ [k ′ ]) = y H i ′ [k ′ ]. Otherwise, if ℓ = 2, then θ(c G j ) = c H j [ℓ], θ(z G i [k]) = y H i [k] and θ(z G i ′ [k ′ ]) = z H i ′ [k ′ ]. Finally, if the clause c j is not satisfied by f , set θ(c G j ) = c H j [3], θ(z G i [k]) = y H i [k] and θ(z G i ′ [k ′ ]) = y H i ′ [k ′ ].
The reader is invited to check that the injective mapping θ preserves n + A(φ, f ) edges.

Conversely, let θ : V(G)

λ G ,λ H ----→ V(H) be an injective mapping. Write A(θ) the number of edges that are preserved by θ. Define Θ to be the set of all injective mappings θ ′ : V(G)

λ G ,λ H ----→ V(H) that preserved at least A(θ) edges. For each θ ′ ∈ Θ, define S(θ ′ ) = {i : {t H i [1], t H i [2]} or {f H i [1], f H i [2]} is matched by θ ′ }. We observe that, by construction, any θ ′ ∈ Θ cannot match both {t H i [1], t H i [2]} and {f H i [1], f H i [2]
}, and hence |S(θ ′ )| ≤ n for all θ ′ ∈ Θ. We claim that there exists θ ′ ∈ Θ such that |S(θ ′ )| = n. Let θ * ∈ Θ be such that |S(θ * )| ≥ S(θ ′ ) for all θ ′ ∈ Θ. Suppose, for the sake of contradiction, that |S(θ * )| < n. Then, there exists one i,

1 ≤ i ≤ n, such that neither {t H i [1], t H i [2]} nor {f H i [1], f H i [2]
} are matched by θ * . We now make the important observation that, by construction, at least one of the four vertices t

H i [1], t H i [2], f H i [1] and f H i [2] is
H i [1], t H i [2]} and {f H i [1], f H i [2]
} of H are matched by θ ′ . As an immediate consequence, A(θ) = n + k for some 0 ≤ k ≤ m. Indeed, at most one of the two edges incident to vertex c G i , Define now a truth assignment f for X as follows: for each

x i ∈ X, f (x i ) = true if and only if the edge {f H i [1], f H i [2]} of H is matched by θ ′ . According to the above, f satisfies k clauses of φ Consequently, we have opt(θ) ≤ n + opt(φ) ≤ m + opt(φ) ≤ 2 opt(φ) + opt(φ) = 3 opt(φ)
, where the second inequality comes from the fact that we can assume that φ contains more clauses than variables and the last inequality is due to the fact that at least half of the clauses of a boolean formula in conjunctive normal form are always satisfiable. Finally, observe that for any

Graph G x 3 [1] c 4 x 2 [2] t G 3 [1] c G 4 t G 2 [2] x 3 [1] c 3 x 1 [2] f G 3 [1] c G 3 t G 1 [2] x 2 [1] c 2 x 1 [1] f G 2 [1] c G 2 f G 1 [1] x 2 [1] c 1 x 1 [1] t G 2 [1] c G 1 t G 1 [1] x 3 [1] x 3 [2] x G 3 [1] x G 3 [2] x 2 [1] x 2 [2] x G 2 [1] x G 2 [2] x 1 [1] x 1 [2] x G 1 [1] x G 1 [2] Graph H x 3 [1] y H 3 [1] x 3 [2] y H 3 [2] x 2 [1] y H 2 [1] x 2 [2] y H 2 [2] x 1 [1] y H 1 [1] x 1 [2] y H 1 [2] c 3 c H 3 [3] c 4 c H 4 [3] c 1 c H 1 [3] c 2 c H 2 [3] c 3 x 3 [1] x 3 [2] c H 3 [2] f H 3 [1] f H 3 [2] c 4 x 3 [1] x 3 [2] c H 4 [2] t H 3 [1] t H 3 [2] c 2 x 2 [1] x 2 [2] c H 2 [2] f H 2 [1] f H 2 [2] c 1 x 2 [1] x 2 [2] c 4 c H 1 [2] t H 2 [1] t H 2 [2] c H 4 [1] c 2 x 1 [1] x 1 [2] c H 2 [2] f H 1 [1] f H 2 [2] c 1 x 1 [1] x 1 [2] c 3 c H 1 [1] t H 1 [1] t H 1 [2] c H 3 [1]
Figure 1. Illustration of the proof of Proposition 5 for the boolean formula

φ = (x 1 ∨ x 2 ) ∧ (x 1 ∨ x 2 ) ∧ (x 1 ∨ x 3 ) ∧ (x 2 ∨ x 3 ).
For the sake of clarity, the color of each vertex is given in shaded circle form.

injective mapping θ : V(G) PROOF. For the sake of clarity, in the reduction described here below, the graph G is actually a forest, but it is very easy to make it into a tree by suitable addition of edges. Furthermore, in the reduction we describe the degree of the graphs G and H is not bounded, but it is easy to modify the reduction so that ∆(G), ∆(H) ≤ 3. These details will be discussed at the end of the proof. The reduction is from the Vertex Cover problem for cubic graphs, which is known to be APX-hard [START_REF] Papadimitriou | Optimization, approximation and complexity classes[END_REF][START_REF] Alimonti | Some apx-completeness results for cubic graphs[END_REF]. Assume thus given a cubic graph W of order n and size m. We now describe the associated instance of the Max- (2, 2)-Matching-Colors problem. For ease of exposition, let us first define P = {(u, e) ∈ V(W ) × E(W ) : u ∈ e} to be the set of pins of the graph W . The set of colors C is now defined by Next, let us specify the forest G. The forest G contains a tree T defined by

λ G ,λ H ----→ V(H), one can find a truth assignment for φ such that A(φ, f ) ≥ A(θ) -n. This implies that opt(φ) -A(φ, f ) = opt(θ) -n -A(φ, f ) = opt(θ) -A(θ).
C = {c 0 , c ′ 0 } ∪ C V ∪ C E ∪ C P , where C V = {c u : u ∈ V(W )}, C E =
V(T ) = {r G 0 } ∪ {T u : u ∈ V(W )} ∪ {T u,e : (u, e) ∈ P } and E(T ) = {{r 0 , T u } : u ∈ V(W )}∪{{T u , T u,e } : (u, e) ∈ P }. The mapping λ G : V(T ) → C is defined by λ G (r G 0 ) = c 0 , λ G (T u ) = c u , u ∈ V(W )
G : V(C e ) → C is defined by λ G (C e e ) = c e , λ G (C e u ) = c u,e and λ G (C e v ) = c v,e .
Finally, let us define the tree

H by V(H) = {r H 0 , s H 0 }∪{H u , H u : u ∈ V(W )}∪ {H u,e , H u,e : (u, e) ∈ P } ∪ {H ′ u,e : (u, e) ∈ P } and E(H) = {{r H 0 , s H 0 }} ∪ {{r H 0 , H u } : u ∈ V(W )} ∪ {{s H 0 , H u } : u ∈ V(W )} ∪ {{H u,e , H u } : (u, e) ∈ P } ∪ {{H u,e , H u } : (u, e) ∈ P } ∪ {{H u,e , H ′
u,e } : (u, e) ∈ P }. The mapping λ H :

V(H) → C is defined by λ H (r H 0 ) = c 0 , λ H (s H 0 ) = c ′ 0 , λ H (H u ) = λ H (H u ) = c u , u ∈ V(W ), λ H (H u,e ) = λ H (H u,e ) = c
u,e , (u, e) ∈ P , and λ H (H ′ u,e ) = c e , (u, e) ∈ P . The description of the reduction is complete. The following two claims are the key of the APX-hardness proof.

Claim 7 Assume W has a vertex cover X ⊆ V(W ), |X| = k. Then the instance G, H, λ G , λ H obtained from the original graph W as outlined above admits a color preserving injective mapping θ : V(G)

λ G ,λ H ----→ V(H) such that |match(G, H, θ)| = 3m + n -k.
PROOF. The solution mapping θ is defined as follows. First, we define θ over the vertices of the tree T as follows:

(i) θ(r R 0 ) = r H 0 , (ii) for each u ∈ V(W ), θ(T u ) = H u if u ∈ X and θ(T u ) = H u
otherwise, and (iii) for each (u, e) ∈ P , θ(T (u,e) ) = H (u,e) if u ∈ X and θ(T (u,e) ) = H (u,e) otherwise. Next, for each edge e = {u, v} ∈ E(W ), we define θ over the three vertices of the connected component C e of G as follows: (iv

) if u ∈ X then θ(C e e ) = H ′ (u,e) , otherwise θ(C e e ) = H ′ (v,e) , (v) if u ∈ X then θ(C e u ) = H (u,e) , otherwise θ(C e u ) = H (u,e) , and (vi) if v ∈ X then θ(C e v ) = H (v,e) , otherwise θ(C e v ) := H (v,e)
. It is easy to check out that θ is a color preserving injective mapping that maps precisely 3 m + nk edges of G into edges of H. ✷ Claim 8 Assume the instance G, H, λ G , λ H obtained from the original graph W as outlined above admits a color preserving injective mapping θ : V(G) Let us now call the mapping θ reasonable if the following two conditions are met: (i) for each edge e = {u, v} ∈ E(W ), precisely one of the two edges of the component C e of G is mapped by θ into an edge of H, and (ii) for each (u, e) ∈ P , θ(T (u,e) ) = H (u,e) if and only if θ(T u ) = H u . It is indeed easy to propose a simple pre-processing algorithm which, starting from θ, constructs a reasonable color preserving injective mapping θ ′ which maps at least as many edges of G as θ does. There is thus no loss of generality in assuming now that θ is reasonable. At this point, we define a subset X of V(W ) as follows. Each vertex u ∈ V(W ) belongs to X if and only if θ(T u ) = H u . Since θ is reasonable, it follows that X is indeed a vertex cover of W . Furthermore, if t is the number of edges of G that θ maps into edges of H, then |X| = 3m + nt. ✷

λ G ,λ H ----→ V(H)
To make G into a tree it suffices to add the following edges: the vertex r G 0 is adjacent to the central vertex C e e of the component C e for each e ∈ E(W ). It is quite clear that this simple modification does not affect the validity of the reduction and of the two claims. It is also very easy yet technical to rely on trees G and H of maximum degree 3 by introducing bifurcation points in the paths from the root T 0 to the vertices T v i as suitable and paralleling the same transformation also into H. To conclude in showing that the proposed reduction is an L-reduction, one has to observe that the Vertex Cover problem is APXhard even when restricted to instances where a minimum vertex cover takes at least half of the vertices (as proven e.g. by the famous Trotter-NemHauser reduction). ✷

Approximation algorithms

We proved in Section 4 that the Max-(3, 3)-Matching-Colors problem for linear forests is APX-hard. In the light of this negative result, we first focus here on approximating the Max-(ρ, σ)-Matching-colors problem for bounded degree graphs and give a polynomial-time approximation algorithm that achieves a performance ratio of 2(∆ min + 1), ∆ min = min{∆(G), ∆(H)}, for the Max-(ρ, σ)-Matching-colors problem. Next, we propose a randomized algorithm with performance ratio 4σ for the Max-(ρ, σ)-Matching- colors problem. and we give an approximation algorithm that achieves a performance ratio of 4 in case both G and H are linear forests. Finally, we prove the Max-(2, 2)-Matching-Colors problem to be approximable within ratio 1.1442.

Bounded degree graphs

We first consider bounded degree graphs. Let C = {c 1 , c 2 , . . . , c m } be a set of colors and G be a graph whose vertices are colored with colors taken from C. Also, let A = [a i,j ] be a symmetric matrix of order m whose entries are natural integers. Consider the problem, referred hereafter as the Max- Matching-with-Color-Constraints (MMwCC) problem, of finding in G a maximum cardinality matching M ⊆ E(G) subject to the constraint that, for 1 ≤ i ≤ j ≤ m, the number of edges in M having one end-vertex colored c i and one end-vertex colored c j is at most a i,j . It is clear that a straightforward greedy algorithm delivers a 2-approximation algorithm for the MMwCC problem.

Lemma 9 The MMwCC problem is approximable within ratio 2.

Recall that an edge coloring of a graph G is proper if no two adjacent edges are assigned the same color. A proper edge coloring with k colors is called a proper k-edge-coloring and is equivalent to the problem of partitioning the edge set into k matchings. The smallest number of colors needed in a proper edge coloring of a graph G is the chromatic index χ ′ (G) [START_REF] Diestel | Graph theory[END_REF]. Vizing's Theorem [START_REF] Vizing | On an estimate of the chromatic class of a p-graph[END_REF] states that χ ′ (G) ≤ ∆(G) + 1 and that such an edge coloring can be found in polynomial-time.

Proposition 10 For any ρ and σ, the Max-(ρ, σ)-Matching-colors problem is approximable within ratio 2(∆ min +1), where ∆ min = min{∆(G), ∆(H)}.

PROOF. Let G, H, λ G , λ H be an arbitrary trim instance of the Max-(ρ, σ)-Matching-colors problem. Assume first ∆ min = ∆(H). According to Vizing's Theorem, H admits a proper edge coloring with at most ∆(H)+1 colors, say {c ′ 1 , c ′ 2 , . . . , c ′ ∆(H)+1 }. For 1 ≤ i ≤ ∆(H) + 1, let H i be the graph obtained from H by deleting all edges but those colored with color c ′ i . Notice that H i is certainly a matching, and hence by resorting to Lemma 9, we can easily obtain a 2-approximation algorithm for the Max-(ρ, σ)-Matching-colors problem for the new instance (G, H i , C, λ G , λ H ). Furthermore, returning the best one these ∆(H)+1 mappings yields an approximation algorithm with performance ratio 2(∆(H) + 1). If ∆ min = ∆(G), we apply the same above arguments to G to obtain an approximation algorithm with performance ratio 2(∆(G) + 1), which completes the proof. ✷

A randomized algorithm

We give here a randomized approximation algorithm which achieves a performance ratio of 4 σ for the Max-(ρ, σ)-Matching-colors problem, for any ρ and σ. Let C be a set of colors and G be a graph whose vertices are colored with colors taken from C. Define a legal (ℓ 1 , ℓ 2 )-labeling of G to be an assignment to labels {ℓ 1 , ℓ 2 } to the vertices of G such that, for each color c i ∈ C, either

|C G (c i )| 2 or |C G (c i )| 2 vertices in C G (c i ) are labeled ℓ 1 .
Of particular importance here is the fact that it is easy to choose at random a legal (ℓ 1 , ℓ 2 )-labeling of G. Define the cut induced by a legal (ℓ 1 , ℓ 2 )-labeling to be the set of edges that have one end-vertex with label ℓ 1 and one end-vertex with label ℓ 2 .

Consider now an arbitrary trim instance G, H, λ G , λ H of the Max-(ρ, σ)-Matching-colors problem and let θ opt : V(G) λ G ,λ H ----→ V(H) be an optimal solution. Now, let L be a random legal (ℓ 1 , ℓ 2 )-labeling of G and C L ⊆ E(G) be the cut induced by L. Finally, let

E ′ = C L ∩ match(G, H, θ opt ). Clearly Exp[|E ′ |] ≥ 1 2 |match(G, H, θ opt )|.
Combining this with a weighted bipartite matching algorithm yields the following result.

we associate to each 2-interval D ∈ D a weight ω(D), the weight of D, denoted ω(D), is defined to be the sum of the weights of all the 2-intervals in D.

Let G, H, λ G , λ H be a trim instance of the Max-(ρ, σ)-Matching-Colors problem where both G and H are linear forests. Let P G 1 , P G 2 , . . . , P G k (resp. P H 1 , P H 2 , . . . , P H ℓ ) be the collection of all paths of G (resp. H). First, we arrange the paths P G 1 , P G 2 , . . . , P G k and next the paths P H 1 , P H 2 , . . . , P H ℓ along an horizontal line, arbitrarily. According to this arrangement, we define the label (resp. reversal label ) of any subpath of a path to be string obtained by concatenating the colors (view as letters) of the vertices of the path reading from left to right (resp. right to left). Second, we construct a corresponding set of weighted 2-intervals D[G, H] as follows. For each pair (Q G i , Q H j ), where and Q H j having the same length, if the label of Q G i is identical to the label of Q H j or to the reversal label of Q H j , we add to D[G, H] a 2-interval whose left interval covers all the vertices (and only those vertices) of the subpath Q G i and whose right interval covers all the vertices (and only those vertices) of the subpath Q H j . The weight of this 2-interval is merely defined to be the length of the subpath Q G i (which also the length of the subpath Q H j ). Without loss of generality, we may assume that each 2-interval in D[G, H] is balanced and that two 2-intervals that correspond to two vertex-disjoint pairs of subpaths are disjoint. See Figure 2 for an illustration of this construction. According to Lemma 12 it is thus enough to focus on finding a maximum weighted subset of D[G, H] of disjoint 2-intervals, which is exactly the 2- Interval-Pattern problem. In [CHL + 06], an algorithm with performance ratio 4 is proposed for finding a subset of disjoint 2-intervals in a balanced 2-intervals set. We have thus proved the following.

Q G i is
Corollary 13 For any ρ and σ, the Max-(ρ, σ)-Matching-Colors problem is approximable within ratio 4 in case both G and H are linear forests.

Approximating the Max-(2, 2)-Matching-Colors problem

This last part is devoted to the NP-hard Max-(2, 2)-Matching-Colors problem. We prove this special case to be approximable within ratio 1.1442. The basic idea is to transform any instance of the Max-(2, 2)-Matching-Colors problem into an instance of the the Max-2-CSP problem. An instance of ble to improve the approximation ratio for bounded degree graphs presented in Proposition 10? Second, due to biological constraints, improving Proposition 11 is of particular interest. In particular, does a deterministic or randomized approximation algorithm with performance ratio σ exist for the Max- (ρ, σ)-Matching-Colors problem?

  It follows that the proposed reduction is, indeed, a L-reduction -with parameters α = 3 and β = 1 -from the Max-2-Sat-3 problem to the Max-(3, 3)-Matching-Colors problem where both G and H are linear forests. ✷ It remains open, however, whether the Max-(ρ, σ)-Matching-Colors problem for linear forests G and H is polynomial-time solvable in case ρ < 3. The rationale of this question stems from the following proposition. Proposition 6 The Max-(2, 2)-Matching-Colors problem is APX-hard even if both G and H are trees.

  {c e : e ∈ E(W )} and C P = {c u,e : (u, e) ∈ P }.

  and λ G (T u,e ) = c u,e , (u, e) ∈ P . Besides the tree T , the forest G contains other m connected components. More precisely, for each edge e = {u, v} ∈ E(W ), the forest G contains a connected component C e defined by V(C e ) = {C e e , C e u , C e v } and E(C e ) = {{C e e , C e u }, {C e e , C e v }}, i.e., the connected component C e is nothing but a length two path in which the vertex C e e is adjacent both to C e u and to C e v . The mapping λ

  that maps t edges of G into edges of H. Then, starting from the knowledge of θ, we can find out in polynomial-time a vertex cover X ⊆ V(W ) of the original graph W with |X| ≥ 3 m + nt.PROOF. Notice first that for each edge e = {u, v} ∈ E(W ), at most one of the two edges of the component C e of G is mapped by θ into an edge of H. Indeed, the central vertex of the length two path C e has color c e and the (two) vertices of H having color c e are leaves of H.

Lemma 12

 12 There exists a pairwise disjoint subset D ′ ⊆ D[G, H] of weight ω(D ′ ) if and only if there exists an injective mapping θ : V(G) λ G ,λ H ----→ V(H) such that |match(G, H, θ)| ≥ ω(D ′ ).

  NP[START_REF] Fertin | Finding exact and maximum occurrences of protein complexes in protein-protein interaction graphs[END_REF]. Therefore, there is a natural interest to investigate the complexity issues of the Max-(ρ, σ)-Matching-Colors problem for restricted graph classes. Unfortunately, as we shall prove here, the Max-(3, 3)- Matching-Colors (resp. Max-(2, 2)-Matching-Colors) problem is APXhard even if both G and H are linear forests (resp. trees with maximum degree 3). The Max-(3, 3)-Matching-Colors problem is APX-hard even if both G and H are linear forests.

	Max-(1, 2)-Matching-Colors problem for bipartite graphs G and H with ∆(G) = 3 and ∆(H) = 2 (resp. with ∆(G) = 6 and ∆(H) = 5) is APX-hard and is not approximable within ratio 1.0005 (resp. 1.0014), un-less P = Proposition 5

  a subpath of length at least one of a path in {P G 1 , P G 2 , . . . , P G k } and Q H j is a subpath of length at least one of a path in {P H 1 , P H 2 , . . . , P H ℓ }, Q i G

Proposition 11 There exists a randomized algorithm for the Max-(ρ, σ)-Matching-Colors problem with expected performance ratio 4 σ.

PROOF. Let θ opt : V(G)

λ G ,λ H ----→ V(H) be an optimal solution. Fix any random legal (ℓ 1 , ℓ 2 )-labeling L of G and let V 1 ⊆ V(G) (resp. V 2 ⊆ V(G)) the set of vertices having label ℓ 1 (resp. ℓ 2 ). Assign at random the vertices in V 1 to vertices in V(H), with respect to λ G and λ H . We denote by θ this partial assignment. We claim that the three following conditions hold true for at least (4 σ) -1 of the edges e = {u, v} in match(G, H, θ opt ): (i) one of the end-vertex of e, say u, has label ℓ 1 and is correctly assigned, i.e., θ opt (u) = θ(u), (ii) one of the end-vertex of e, say v, has label ℓ 2 (and hence is not yet assigned), and (iii) θ opt (v) is still free, i.e., no vertex of G with label ℓ 1 has been assigned to it in the first step. Indeed, for any

of the vertices in C G (c i ) have been randomly assigned to the at least |C H (c i )| vertices of H, then it follows that the probability that a vertex of H is the image of a wrong vertex (according to θ opt ) is at most 1 2 . To complete the proof, we notice that the problem of assigning the vertices of V 2 to the remaining vertices in H in such a way to maximize the number of edges in the cut induced by the labeling L that are matched in H according to θ can be solved to optimality in polynomial-time by a natural reduction to weighted bipartite matching. ✷

Linear forests

We proved in Section 4 that the Max-(3, 3)-Matching-Colors problem is APX-hard even if both G and H are linear forests. Furthermore, according to Proposition 10, the Max-(ρ, σ)-Matching-Colors problem for linear forests is approximable within ratio 2(∆ min + 1) = 6. We strengthen this result here by giving an algorithm that achieves a performance ratio of 4 for the Max- (ρ, σ)-Matching-Colors problem for linear forests. Interestingly enough, the proof make use of weighted 2-intervals sets. More precisely, our approach is based on the 2-Interval-Pattern problem [Via04,CHL + 06]. This problem, initially motivated by RNA secondary structure prediction, asks to find a maximum cardinality subset of a 2-interval set with respect to some prespecified geometric constraints.

We need some additional definitions. A 2-interval [TH79,BYHN + 02,Via04]. is the union of two disjoint intervals and is denoted by D = (I, J) where I and J are two (closed) intervals such that I is completely to the left of J. Two 2-intervals D 1 = (I 1 , J 1 ) and D 2 = (I 2 , J 2 ) are disjoint, if both 2-intervals share no common point. A 2-interval D = (I, J) is said to be balanced if |I| = |J|, i.e., both intervals have the same length. By abuse of notation, a set of balanced 2-interval is also said to be balanced. Let D be a set 2-intervals. If the (boolean) MAX-CSP problem consists of a set of boolean variables and a collection of constraints which are applied to certain specified subsets of these variables; the goal is to find values for the variables which maximize the number of simultaneously satisfied constraints. For analyzing purposes it is useful to consider restricted subclasses of the MAX-CSP problem. Most importantly, MAX-k-CSP is the maximum constraint satisfaction problem where each constraint depends on at most k variables.

Let G, H, λ G , λ H be an arbitrary instance of the the Max-(2, 2)-Matching-Colors problem. For the sake of simplification, by adding dummy isolated vertices if needed, we assume that each color occurs exactly twice in both G and H. Let X be a set of boolean variables defined by X = {x c : c ∈ C}, and write X ∪ X the set of literals over X. Furthermore, define a partial function f : V(G) × V(H) → X ∪ X as follows. For each color c ∈ C, write u and u ′ the two vertices of G with color c, and v and v ′ the two vertices of H with color c, and define f (u, v) = x c and f (u ′ , v ′ ) = x c , the choice is arbitrary. We now turn to defining the corresponding set of constraints F(G, H). Let e = {u, v} ∈ E(G), and write λ G (u) = c i and λ G (v) = c j . We only need to consider the case where c i = c j (the case c i = c j is indeed trivial if ρ = 2 and σ = 2). Thus, let u ′ and u ′′ be the two vertices of H with color c i , and v ′ and v ′′ be the two vertices of H with color c j . Without loss of generality, assume in addition constraint f e defined accordingly to Figure 3. Clearly, there exists an injective mapping θ :

that matches k edges of G if and only if k constraints of the constraint set F(G, H) are simultaneously satisfied. But, each constraint f e ∈ F(G, H) is involved in at most 2 variables, and hence F(G, H) is an instance of the Max-2-CSP problem. Combining this with the fact that the Max-2-CSP problem is approximable with ratio 1.1442 [START_REF] Lewin | Improved rounding techniques for the max 2-sat and max di-cut problems[END_REF], we obtain the following proposition.

Proposition 14 The Max-(2, 2)-Matching-Colors problem is approximable within ratio 1.1442.

Conclusion

In the context of comparative analysis of protein-protein interaction graphs, we considered the problem of finding an occurrence of a given complex in the protein-protein interaction graph of another species. We gave an efficient randomized algorithm in case the mapping is required to be an injective homomorphism. Also, we proved the Max-(3, 3)-Matching-Colors problem for linear forests to be APX-hard and we gave an approximation algorithm that achieves a performance ratio of 2(∆ min + 1), a randomized algorithm with approximation ratio 4 σ and a simple approximation algorithm with performance ratio 4 in case both G and H are linear forests.

We mention here some possible directions for future works. First, is it possi-