The maximum quasi-biclique problem has been proposed for finding interacting protein group pairs from large protein-protein interaction (PPI) networks. The problem is defined as follows: THE MAXIMUM QUASI-BICLIQUE PROBLEM: Given a bipartite graph G = (X U Y, E) and a number 0 < δ ≤ 0.5, find a subset X_(opt) of X and a subset Y_(opt) of Y such that any vertex x ∈ X_(opt) is incident to at least (1 - δ)|Y_(opt)| vertices in Y_(opt), any vertex y ∈ Y_(opt) is incident to at least (1 - δ)|X_(opt)| vertices in X_(opt) and |X_(opt)| + |Y_(opt)| is maximized. The problem was proved to be NP-hard [2]. We design a polynomial time approximation scheme to give a quasi-biclique (X_a, Y_a) for X_a (is contained in) X and Y_a (is contained in) Y with |X_a| ≥ (1 - ∈)|X_(opt)| and |Y_a| ≥ (1 - ∈)|Y_(opt)| such that any vertex x ∈ X_a is incident to at least (1 - δ - ∈)|Y_a| vertices in Y_a and any vertex y ∈ Y_a is incident to at least (1 - δ - ∈)|X_A| vertices in X_a for any ∈ > 0, where X_(opt) and Y_(opt) form the optimal solution.
展开▼
