The problem of aligning multiple metabolic pathways is one of very challenging problems in computational biology. A metabolic pathway consists of three types of entities: reactions, compounds, and enzymes. Based on similarities between enzymes, Tohsato et al. gave an algorithm for aligning multiple metabolic pathways. However, the algorithm given by Tohsato et al. neglects the similarities among reactions, compounds, enzymes, and pathway topology. How to design algorithms for the alignment problem of multiple metabolic pathways based on the similarity of reactions, compounds, and enzymes? It is a difficult computational problem. In this article, we propose an algorithm for the problem of aligning multiple metabolic pathways based on the similarities among reactions, compounds, enzymes, and pathway topology. First, we compute a weight between each pair of like entities in different input pathways based on the entities' similarity score and topological structure using Ay et al.'s methods. We then construct a weighted k-partite graph for the reactions, compounds, and enzymes. We extract a mapping between these entities by solving the maximum-weighted k-partite matching problem by applying a novel heuristic algorithm. By analyzing the alignment results of multiple pathways in different organisms, we show that the alignments found by our algorithm correctly identify common subnetworks among multiple pathways.
1. Introduction
With the development of science and technology, several different types of biological data are produced, including genomic, proteomic, and pathway data. Metabolic pathway data are one of the important types of data in biology and provide interaction information on three types of entities important to organisms (Ay et al., 2008). By analyzing these data, people can get useful information. For example, the analysis of metabolic pathway data can provide important information for drug designing (Sridhar et al., 2007) and comparing genomes (Bono et al., 1998; Dandekar et al., 1999).
The comparative analysis of pathways is one of the most important types of pathway analysis, and the comparative analysis of different metabolic pathways can provide insight in several biological applications. Network alignment is a comparative method of analysis that seeks to identify subnetworks that are conserved across two or more species, which implies that they represent true functional modules (Sharan and Ideker, 2006). Network alignment methods can be used to compare many different types of networks, including protein interaction networks (Kelley et al., 2003), regulatory networks (Yu et al., 2004), and metabolic networks (Ogata et al., 2000). One of the widely used types of networks for network alignment is the metabolic network. Aligning metabolic networks requires a method of determining similarity between parts of different networks, which has been done in many different ways. Similarity has been determined using the similarity of the enzymes that catalyze the metabolic reactions in the network (Kelley et al., 2003) and the EC (Enzyme Commission) numbers (Tohsato et al., 2000; Koyutürk et al., 2004; Wernicke and Rasche, 2007). Similarity between the topological structures of the networks has also been used (Pinter et al., 2005; Li et al., 2008). Recently, similarity measures that combine many different measures of similarity have been developed (Li et al., 2008; Tian and Samatova, 2009). Metabolic network alignment algorithms use these similarity measures to identify conserved subnetworks, which likely correspond to conserved metabolic pathways.
As stated in Ay et al. (2008), the pairwise pathway alignment problem is close to finding a maximum common isomorphism subgraph from two graphs. The maximum common subgraph problem is related to the well-known graph isomorphism and subgraph isomorphism problems. The graph isomorphism problem is the problem of deciding if two graphs have the same topological structure, and the subgraph isomorphism problem is the problem of deciding if one graph is isomorphic to a subgraph of another. In computer science, the complexity of graph isomorphism is unknown, although the subgraph isomorphism problem is known to be NP (nondeterministic polynomial time)-complete (Garey and Johnson, 1979). At present, there are no polynomial time exact algorithms for the graph isomorphism and subgraph isomorphism problems, and as the pairwise alignment can be reduced to these problems, existing algorithms for the pairwise pathway alignment problem rely on heuristic methods (Pinter et al., 2005; Tohsato and Nishimura, 2007; Ay et al., 2008).
In Tohsato and Nishimura (2007), Tohsato et al. (2000) propose a pairwise alignment algorithm based solely on the similarities between compounds in the pathways. Pinter et al. (2005) propose a pairwise alignment algorithm to align metabolic pathway by aligning tree based only on the similarities between enzymes. These two algorithms only consider the similarities among one type of entity and neglect the other entities, as well as the topological structure of the pathways. This neglect can result in information loss, as explained by Ay et al. (2008), which can reduce accuracy in the results and limits the utility of these algorithms in the pairwise alignment problem. To overcome these restrictions, Ay et al. (2008) propose an algorithm for the pairwise alignment of metabolic pathways based on the similarity of enzymes, compounds, reactions, and topological structure. This technique improves accuracy and is not limited to pathways with topological restrictions. However, the algorithm by Ferhat Ay et al. can only be applied to two pathways. In many cases, we need to compute the similarity between multiple pathways.
Tohsato et al. (2000) proposed an algorithm to align multiple metabolic pathways based on the similarity of enzymes. This algorithm, however, does not consider similarities in topology or other entities, such as compounds and reactions. Thus, their algorithm is less accurate. To overcome this shortcoming, we propose an algorithm for the problem of aligning multiple metabolic pathways based on the similarities between enzymes, compounds, reactions, and topological structure.
A k-partite matching in a k-partite graph is a vertex partition that partitions the vertices into different equivalence classes. Given a weighted k-partite graph, the maximum-weighted k-partite matching problem is the problem of finding the k-partite matching with the maximum weight. In Singh et al. (2008), the maximum-weighted k-partite matching problem has been used to compute an alignment across multiple protein–protein interaction (PPI) networks. Our reduction from the problem of aligning multiple metabolic pathways to the maximum-weighted k-partite matching problem is a modification of the reduction from the multiple alignment of PPI network to the maximum-weighted k-partite matching problem presented in Singh et al. (2008).
1.1. Our contributions
In this article, we propose an algorithm for aligning multiple metabolic pathways based on the similarity of enzymes, compounds, reactions, and topological structure. We use Ferhat Ay's graph model to represent each metabolic pathway (Ay et al., 2008). To compute the alignment of multiple pathways, we create a weighted k-partite graph for each type of entity and reduce the problem of aligning multiple metabolic pathways to the maximum-weighted k-partite matching problem.
Before we describe our algorithms, we introduce the maximum-weighted (1, r)-matching problem in a bipartite graph, where one vertex in one part can be matched at most r vertices in the other part, and give a polynomial time algorithm for this problem. Based on the algorithm for the maximum-weighted (1, r)-matching problem, we will give an approximation algorithm and a heuristic algorithm for the maximum-weighted k-partite matching problem.
Singh et al. have proposed a greedy algorithm for the maximum-weighted k-partite matching problem in Singh et al. (2008). We compare the accuracy of Singh et al.'s greedy algorithm with our approximation heuristic algorithms, and our experimental results show that our heuristic algorithm is the most accurate based on the matching weights.
We apply our heuristic algorithm to compute an alignment of multiple metabolic pathways. Our experiments show that our algorithm can correctly identify common subnetworks among multiple pathways, which can be used to find conserved entities. To enforce the consistent mapping [the consistent alignment concept is introduced by Ay et al. (2008)], we first get the mapping of reactions. Then, we remove those nonconsistent enzymes and compounds based on the mapping of reactions and reachability concept.
2. Definitions
In Ay et al. (2008), Ferhat Ay describes a graph representation of metabolic pathways for computing the pairwise alignment of pathways. The advantage of Ferhat Ay et al.'s graph representation is that it exhibits no information loss and includes the topological structure of the pathways. If the graph representation exhibited information loss, the alignment results would be less accurate (Ay et al., 2008). Thus, to compute the alignment of multiple pathways without topological restrictions, we use Ferhat Ay et al.'s graph model to represent metabolic pathways.
For clarity, we reproduce some of the notations from Ay et al. (2008).
Notations in Ay et al. (2008): “Let\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \cal P} , \mathcal{R} , { \cal C} , \mathcal{E}$$
\end{document}denote the sets of all pathways, all reactions, all compounds, and all enzymes, respectively. Let\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$R \subseteq \mathcal{R}$$
\end{document}such that\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$R = \{ {R_1} , {R_2} , \ldots , {R_{ \vert R \vert }} \} $$
\end{document}denote the reactions. Let\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$C \subseteq { \cal C}$$
\end{document}such that\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$C = \{ {C_1} , {C_2} , \ldots , {C_{ \vert C \vert }} \} $$
\end{document}denote the compounds. Let\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$E \subseteq \mathcal{E}$$
\end{document}such that\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$E = \{ {E_1} , {E_2} , \ldots , {E_{ \vert E \vert }} \} $$
\end{document}denote the enzymes.”
We also reproduce the definition of the graph representation for a metabolic pathway from Ay et al. (2008).
Definition 1.A directed graph,\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G ( V , I )$$
\end{document}for representing the metabolic pathway\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$P \in { \cal P}$$
\end{document}, is constructed as follows (Ay et al., 2008): The node set,\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$V = [ R , C , E ]$$
\end{document}, is the union of reactions, compounds, and enzymes of P. The edge set, I, is the set of interactions between the nodes. An interaction is represented by a directed edge that is drawn from a node x to another node y if and only if one of the following three conditions holds:
1. x is an enzyme that catalyzes reaction y.
2. x is an input compound of reaction y.
3. x is a reaction that produces compound y.
Below, we give the definition of an alignment of multiple pathways, which is a generalization of the pairwise alignment of pathways described in Ay et al. (2008).
Definition 2.An alignment of k metabolic pathways\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${P_1} = G ( [ {R_1} , {C_1} , {E_1} ] , {I_1} ) , \ldots ,$$
\end{document}\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${P_k} = G ( [ {R_k} , {C_k} , {E_k} ] , {I_k} )$$
\end{document}is a partition over the node set\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$V = {V_1} \cup \ldots \cup {V_k}$$
\end{document}that divides V into disjoint equivalence classes. The nodes in each equivalence classes are mapped to each other and are of the same type of entity (i.e., compounds are mapped to compounds, enzymes to enzymes, and reactions to reactions).
To evaluate the degree of similarity between two alignments across multiple pathways, we define an alignment score based on compounds and enzymes, a generalization of the similarity score of pairwise pathways defined in Ay et al. (2008). Since the similarity score of two reactions is computed from the similarity scores of compounds and enzymes (Ay et al., 2008), the similarity scores of reactions are not included in the alignment score.
where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$0 \le \beta \le 1$$
\end{document} is a parameter that measures the relative importance of compounds and enzymes, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\vert { \varphi _C} \vert$$
\end{document} is the number of compound mappings, and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\vert { \varphi _E} \vert$$
\end{document} is the number of enzyme mappings. \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$SimC ( {C_i} , {C_j} )$$
\end{document} denotes the similarity score of Ci and Cj, and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$SimE ( {E_i} , {E_j} )$$
\end{document} denotes the similarity score of Ei and Ej. Different methods for calculating the similarity scores of two compounds and two enzymes are discussed in Section 4.1 of Ay et al. (2008). Two enzyme similarity scoring methods are hierarchical enzyme similarity score (Tohsato et al., 2000) and information content enzyme similarity score (Pinter et al., 2005), and two compound similarity scoring methods are trivial compound similarity score and SIMCOMP compound similarity score (Hattori et al., 2003).
The alignment problem of multiple pathways is defined as follows:
Definition 4.The problem of aligning the k pathways\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${P_1} , \ldots , {P_k}$$
\end{document}is the problem of finding an alignment\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\varphi$$
\end{document}of\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${P_1} , \ldots , {P_k}$$
\end{document}with the maximum alignment score.
3. The Algorithm for The Alignment Problem of Multiple Pathways
The maximum-weighted k-partite matching problem is introduced in Singh et al. (2008), and a greedy algorithm is used to compute the global alignment of multiple PPI networks. Similarly, we will use the solution produced by our heuristic algorithm to compute the mappings between the compounds, enzymes, and reactions of multiple pathways. In Singh et al. (2008), there is an informal description for the maximum-weighted k-partite matching problem. We give a formal definition for the maximum-weighted k-partite matching problem.
Definition 5.Suppose\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G = ( V , E , w )$$
\end{document}is a weighted k-partite graph whose k parts are\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${U_1} , \ldots , {U_k}$$
\end{document}. A k-partite matching M of G is a vertex partition that divides V into\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${V_1} , \ldots , {V_h}$$
\end{document}such that\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$V = {V_1} \cup \ldots \cup {V_h}$$
\end{document}and Vi contains at most r vertices from Uj for any\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$i , j$$
\end{document}, where h and r are two positive integers. The weight\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w ( M )$$
\end{document}of M is\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\mathop \sum \limits_{i = 1}^h w ( G ( {V_i} ) )$$
\end{document}, where\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w ( G ( {V_i} ) ) = \mathop \sum \limits_{e \in E ( G ( {V_i} ) ) } w ( e )$$
\end{document}is the weight of the subgraph\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G ( {V _i} )$$
\end{document}induced by Vi,\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$E ( G ( {V _i} ) )$$
\end{document}is the set of edges in\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G ( {V_i} )$$
\end{document}, and\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w ( e )$$
\end{document}is the weight of edge e. When\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$k = 2$$
\end{document}, this matching is called an\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( r , r )$$
\end{document}-matching.
Definition 6.Given a weighted k-partite graph, the maximum-weighted k-partite matching problem is the problem of finding a k-partite matching with the maximum weight.
In the following, we give an algorithm for the alignment of multiple pathways without topological restrictions (Algorithm 1).
This algorithm is a modification of Singh et al.'s algorithm for aligning multiple PPI networks in Singh et al. (2008). Our novelty is as follows: we create three k-partite graphs, and we propose an approximation algorithm and a heuristic algorithm for the maximum-weighted k-partite matching problem in the following sections since the maximum weight k-partite matching is NP-hard (Singh et al., 2008). To enforce the consistent mapping, we first get the mapping of reactions. Then, we remove those nonconsistent enzymes and compounds based on the mapping of reactions and reachability concept. [The consistent alignment concept is introduced in Ay et al. (2008).]
Algorithm 1: The Multiple Pathway Alignment Algorithm
Output: A global alignment of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${P_1} , \ldots , {P_k}$$
\end{document}.
1: For each pair of pathways Pi and Pj (\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$i \ne j$$
\end{document}), we compute a weight for each pair of compounds, each pair of reactions, and each pair of enzymes in Pi and Pj by the method in Ay et al. (2008). This method considers the similarity of the entities as well as the topology.
2: Based on these weights, we construct weighted k-partite graphs \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${H_R} , {H_E} ,$$
\end{document} and HC for the reactions, enzymes, and compounds, respectively. HR consists of k partite sets of reaction nodes: each partite set of reaction nodes comes from one pathway. Weighted edges are constructed as follows. If ri comes from Pi and rj comes from Pj, and the weight between ri and rj is \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${w_{ij}}$$
\end{document}, then there is an edge \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$E ( {r_i} , {r_j} )$$
\end{document} between ri and rj iff \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${w_{ij}} > 0$$
\end{document}. The weight of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$E ( {r_i} , {r_j} )$$
\end{document} is \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${w_{ij}}$$
\end{document}. HE and HC are constructed similarly.
3: We compute approximation solutions \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${M_R} , {M_E} ,$$
\end{document} and MC for the maximum-weighted k-partite matching of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${H_R} , {H_E} ,$$
\end{document} and HC, respectively, by a heuristic algorithm from the following sections.
4: Based on MR and reachability concept, we can determine if two enzymes (or compounds) are consistent. From ME and MC, by pruning those nonconsistent enzymes and compounds, we get \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${M ^\prime _E}$$
\end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${M ^\prime _C}$$
\end{document}.
5: These \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${M_R} , {M ^\prime _E} ,$$
\end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${M ^\prime _C}$$
\end{document} give the consistent mapping of reactions, enzymes, and compounds, respectively, and define a consistent alignment of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${P_1} , \ldots , {P_k}$$
\end{document}.
4. A Polynomial Time Algorithm for The Maximum-Weighted (1, r)-Matching Problem in a Bipartite Graph
In a weighted bipartite graph, a maximum-weighted matching is a matching with maximum weight. The maximum-weighted bipartite matching problem is the problem of finding the maximum-weighted matching in a weighted bipartite graph, which is a well-known combinatorial optimization problem in computer science. To give the new algorithms for the maximum-weighted k-partite matching problem, we generalize the maximum-weighted matching problem in bipartite graphs to the maximum-weighted (1, r)-matching problem in bipartite graphs.
In the following, we introduce the definition of the maximum-weighted (1, r)-matching in a bipartite graph.
Definition 7.Let\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G = ( [ L , R ] , E )$$
\end{document}be a weighted bipartite graph, where L and R are the vertices set of two parts. For a positive integer\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$r \ge 1$$
\end{document}, a (1, r)-matching is a vertex partition of V that partitions V into\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${V_1} , \ldots , {V_h}$$
\end{document}such that\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\vert {V_i} \cap L \vert \le 1$$
\end{document}and\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\vert {V_i} \cap R \vert \le r$$
\end{document}for every Vi. In the maximum (1, r)-matching problem, we want to find the (1, r)-matching with the maximum weight.
In the following, we give a polynomial-time algorithm to compute the maximum-weighted (1, r)-matching in a bipartite graph.
In the following, we show that the above algorithm can find a maximum-weighted (1, r)-matching in polynomial time.
Algorithm 2: A Polynomial Algorithm A1 for the Maximum-Weighted (1, r)-Matching in a Bipartite Graph
Input: A weighted bipartite graph \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G = ( L , R )$$
\end{document}, where \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\vert L \vert = m$$
\end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\vert R \vert = n$$
\end{document}.
Output: A (1, r)-matching of maximum weight.
1: Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${v_1} , \ldots , {v_{{n_1}}}$$
\end{document} be the vertices in L. Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$d ( {v_i} )$$
\end{document} denote the degree of vi for all i.
2: Construct \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G ^\prime = ( L ^\prime , R ^\prime )$$
\end{document} from G as follows. For any \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${v_i} \in L$$
\end{document}, if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$d ( {v_i} ) \ge r$$
\end{document}, then we place r copies \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${v_{i1}} , \ldots , {v_{ir}}$$
\end{document} of vi into \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G ^\prime$$
\end{document}. If \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$d ( {v_i} ) \le r$$
\end{document}, then we put \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$d ( {v_i} )$$
\end{document} copies \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${v_{i1}} , \ldots , {v_{id ( {v_i} ) }}$$
\end{document} of vi in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G ^\prime$$
\end{document}, where vertex u being a copy of vertex v means that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( u , u ^\prime ) \in E ( G )$$
\end{document} iff \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( v , u ^\prime ) \in E ( G )$$
\end{document} for any vertex \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$u ^\prime$$
\end{document}. Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$R ^\prime = R$$
\end{document}.
3: Find the maximum-weighted matching \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$M ^\prime$$
\end{document} in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G ^\prime$$
\end{document} by using the known algorithms, such as the algorithm in Fredman and Tarjan (1984). [More references can be found in Fredman and Tarjan (1984).]
4: Compute the (1, r)-matching M from \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$M ^\prime$$
\end{document}: for any vi, if \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( {v_{i{j_1}}} , {w_{i1}} ) \in M ^\prime , \ldots , ( {v_{i{j_h}}} , {w_{ih}} ) \in$$
\end{document}\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$M \prime$$
\end{document}, then vi is matched to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\{ {w_{i1}} \ldots , {w_{ih}} \} $$
\end{document}.
Theorem 1.Algorithm 2 can find a maximum-weighted (1, r)-matching in\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$O ( mn + {n^2} \log n )$$
\end{document}-time.
Proof. Steps 1 and 2 can be finished in time \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$O ( m )$$
\end{document}. Step 3 can be finished in time \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$O ( mn + {n^2} \log n )$$
\end{document} (Fredman and Tarjan, 1984). Thus, the Algorithm 2 can be finished in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$O ( mn + {n^2} \log n )$$
\end{document}-time.
First, we show that M in algorithm A1 is a (1, r)-matching. Suppose that vi is matched to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\{ {w_{i1}} , \ldots , {w_{ih}} \} $$
\end{document} and that vj is matched to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\{ {w_{j1}} , \ldots , {w_{j \ell }} \} $$
\end{document}. Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$M ^\prime$$
\end{document} be the maximum matching found in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G ^\prime$$
\end{document} at step 3. From step 4, there are some copy \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${v_i}p$$
\end{document} of vi and some copy \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${v_j}q$$
\end{document} of vj such that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( {v_i} , {w_{ip}} ) \in M ^\prime$$
\end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( {v_j} , {w_{jq}} ) \in M ^\prime$$
\end{document} for every \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$p \in \{ 1 , \ldots , h \} $$
\end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$q \in \{ 1 , \ldots , \ell \} $$
\end{document}. Since \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$M ^\prime$$
\end{document} is a matching in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G ^\prime$$
\end{document}, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${w_{ip}} \ne {w_{jq}}$$
\end{document} for any \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$p \in \{ 1 , \ldots , h \} $$
\end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$q \in \{ 1 , \ldots , \ell \} $$
\end{document}. So \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\{ {w_{i1}} , \ldots , {w_{ih}} \} \cap \{ {w_{j1}} , \ldots , {w_{j \ell }} \} = \emptyset$$
\end{document}. Since there are at most r copies of any vertex vi, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$h \le r$$
\end{document}. Thus, M is a (1, r)-matching.
Second, we show that the weight \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w ( M )$$
\end{document} of M is the maximum. Let M2 be any (1, r)-matching in G. We can construct a matching \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${M ^\prime _2}$$
\end{document} in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G ^\prime$$
\end{document} as follows: if vi is matched to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\{ {w_{i1}} \ldots , {w_{ih}} \} $$
\end{document} in M2, then \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( {v_{i{j_1}}} , {w_{i1}} ) \in {M_{2 \prime }} , \ldots , ( {v_{i{j_h}}} , {w_{ih}} ) \in {M_{2 \prime }}$$
\end{document}. Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$M \prime$$
\end{document} be the maximum matching found in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G ^\prime$$
\end{document} at step 3. Since \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$M ^\prime$$
\end{document} is a maximum matching in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G ^\prime$$
\end{document}, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w ( M ^\prime ) \ge w ( {M ^\prime _2} )$$
\end{document}. Since \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w ( M ) = w ( M ^\prime )$$
\end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w ( {M_2} ) = w ( {M ^\prime _2} )$$
\end{document}, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w ( M ) \ge w ( {M_2} )$$
\end{document}, so the weight \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w ( M )$$
\end{document} of M is the maximum out of all (1, r)-matchings. ■
5. An Approximation Algorithm for The Maximum-Weighted K-Partite Matching Problem
The maximum-weighted k-partite matching problem is introduced in Singh et al. (2008) and is used to compute the alignment of multiple PPI networks. Each of these PPI networks is modeled as a weighted graph, and the problem of aligning the PPI networks is reduced to the maximum-weighted k-partite matching problem. Singh et al. (2008) give a greedy heuristic algorithm for the maximum-weighted k-partite matching problem. In this section, we describe the first approximation algorithm for the maximum-weighted k-partite matching problem. Our approximation algorithm is a generalization of the approximation algorithm for the maximum disjoint k-clique problem in He et al. (2000), which is a special case of maximum-weighted k-partite matching problem. The approximation algorithm given in He et al. (2000) is based on the maximum-weighted matching in a bipartite graph and the idea of merging matched vertices. Our approximation algorithm for the maximum-weighted k-partite matching problem is based on the maximum-weighted (1, r)-matching in a bipartite graph and the idea of merging matched vertices.
First, we extend the definition of the merging operation in He et al. (2000) to merge (1, r)-matching operation. For clarity, we reproduce some notations from He et al. (2000) in the following definition. In our definition, the matched vertices are merged into a single node, whereas in He et al. (2000), an edge is merged into a node.
Definition 8.Suppose\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G = ( V , E , w )$$
\end{document}is a weighted k-partite graph with k parts:\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${U_1} , \ldots , {U_k}$$
\end{document}. Let\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${G_{i , j}} = G [ {U_i} \cup {U_j} ]$$
\end{document}be the subgraph induced by\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${U_i} \cup {U_j}$$
\end{document}, and let\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${M_{i , j}}$$
\end{document}be a (1, r)-matching of\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${G_{i , j}}$$
\end{document}. For our definition, if v is matched to\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\{ {u_1} , \ldots , {u_r} \} $$
\end{document}in\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${M_{i , j}}$$
\end{document}, then we merge\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$v , {u_1} , \ldots , {u_r}$$
\end{document}into is a new vertex u. Let\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${U_i} ( j )$$
\end{document}denote the new vertex set of G. For each\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$v ^\prime \in V$$
\end{document}, we define edge weights to the merged vertex using\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w ( u , v \prime ) = w ( v , v ^\prime ) + \mathop \sum \limits_{i = 1}^r w ( {u_i} , v ^\prime )$$
\end{document}, and the loops and edges between vertices\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$v , {u_1} , \ldots , {u_r}$$
\end{document}are removed. Let\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( {G_{i ( j ) }} , w ^\prime )$$
\end{document}denote the new weighted graph after merging\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${M_{i , j}}$$
\end{document}. Note that\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( {G_{i ( j ) }} , w ^\prime )$$
\end{document}is an edge-weighted\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( k - 1 )$$
\end{document}-partite graph.
We now propose an approximation algorithm for the maximum-weighted k-partite matching problem (Algorithm 3) that is the generalization of the approximation algorithm for the maximum disjoint k-clique problem in He et al. (2000). To explain our algorithm clearly, we present our algorithm in a modified format from the description of the approximation algorithm in He et al. (2000).
The idea behind Algorithm 3 is as follows. First, we find the maximum-weighted (1, r)-matching between U1 and Uk and merge U1 and Uk into one graph, turning the k-partite graph into a (k−1)-partite graph. This process is repeated until the original k-partite graph becomes the bipartite graph \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G ^\prime$$
\end{document}. Finally, we find the maximum-weighted (1, r)-matching in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G ^\prime$$
\end{document} and return the associated k-partite matching.
Algorithm 3: The Approximation Algorithm A2 for the Maximum-Weighted k-Partite Matching Problem
4: Find a maximum-weighted (1, r)-matching Mi of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G_{1 , i}^i$$
\end{document} by Algorithm 2. Suppose that Mi matches v1 to the vertex set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$S_1^i$$
\end{document}, v2 to the vertex set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$S_2^i$$
\end{document}, and so on.
5: Merge Mi in Gi to produce the \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( i - 1 )$$
\end{document}-partite graph \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G_{1 ( i ) }^i$$
\end{document}.
6: Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$i = i - 1$$
\end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${G^i} = G_{1 ( i ) }^i$$
\end{document}.
7: end while
8: Find a maximum-weighted (1, r)-matching M2 of G2 by Algorithm 2.
Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$c = \max \{ \vert {U_1} \vert , \vert {U_2} \vert , \ldots , \vert {U_k} \vert \} $$
\end{document}. Step 4 in Algorithm 3 can be finished in time \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$O ( {c^3} )$$
\end{document} by Theorem 1, and since the while loop at step 2 can iterate at most k times, the total time for Algorithm 3 is at most \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$O ( k{c^3} )$$
\end{document}.
In the following, we prove an approximation ratio for our algorithm.
Theorem 2.Suppose G is a weighted complete bipartite graph where each part has c vertices. Let M be the solution output by Algorithm 3. It must be the case that\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$ { \frac { w ( G ) } { w ( M ) } } \le c$$
\end{document}, where\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w ( G )$$
\end{document}and\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w ( M )$$
\end{document}are the sum of edges weight of G and M, respectively.
Proof. In Algorithm 3, the matching M is a maximum-weighted (1, r)-matching in G output when \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$k = 2$$
\end{document}. Thus, M corresponds to the maximum-weight matching \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$M ^\prime$$
\end{document} that appears in algorithm A1 by the proof of Theorem 3.2. From the graph \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G ^\prime$$
\end{document}, we construct a cr complete bipartite graph \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G \prime\prime = ( L \prime\prime , R \prime\prime )$$
\end{document} as follows: let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$L \prime\prime = L ^\prime$$
\end{document}, and add \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( c - 1 ) r$$
\end{document} new vertices to the set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$R ^\prime$$
\end{document} to form \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$R \prime\prime$$
\end{document}. We add an edge of weight 0 from every new vertex to every vertex in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$L \prime\prime$$
\end{document}, and keep all of the edges in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G ^\prime$$
\end{document}. Thus, for every matching \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$M \prime\prime$$
\end{document} in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G \prime\prime$$
\end{document}, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$M \prime\prime \cap G ^\prime$$
\end{document} is a matching in \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G \prime$$
\end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w ( M \prime\prime ) = w ( M \prime\prime \cap G ^\prime )$$
\end{document}. Since \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G \prime\prime$$
\end{document} is complete bipartite graph with cr vertices in each part, it can be easily decomposed into the cr edge-disjoint perfect matching \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${M \prime\prime _1} , \ldots , {M \prime\prime _{cr}}$$
\end{document}. (It is simple to prove that every k-regular bipartite graph can be decomposed into k edge-disjoint perfect matchings by induction on k. Please see exercise 3.3.4 in the book West (2004). Thus, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w ( {M \prime\prime _1} ) + \cdots + w ( {M \prime\prime _{cr}} ) = w ( G \prime\prime )$$
\end{document}, so \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w ( {M \prime\prime _1} \cap G ^\prime ) + \cdots + w ( {M \prime\prime _{cr}} \cap G ^\prime ) = w ( G \prime\prime \prime )$$
\end{document}. Since \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w ( {M \prime\prime _i} \cap G ^\prime ) \le w ( M ^\prime )$$
\end{document} for any i, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$cr \cdot w ( M \prime ) \ge w ( G \prime\prime )$$
\end{document}. As \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w ( G \prime\prime ) = w ( G ^\prime ) = r \cdot w ( G )$$
\end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w ( M ^\prime ) = w ( M )$$
\end{document}, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$cr \cdot w ( M ) \ge r \cdot w ( G )$$
\end{document}, proving that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$ { \frac { w ( G ) } { w ( M ) } } \le c$$
\end{document}. ■
Based on the proof of Theorem 2, we show that the conclusion of Theorem 2 in He et al. (2000) holds for our algorithm A2 by induction.
Theorem 3.Suppose G is a weighted complete k-partite graph where each part has c vertices. Let M be the solution output by algorithm A2. It must be the case that\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$ { \frac { w ( G ) } { w ( M ) } } \le c$$
\end{document}.
Proof. We use induction on k to prove the claim. First, the conclusion holds for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$k = 2$$
\end{document} by Theorem 2. So, suppose that the claim holds for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$k - 1$$
\end{document}. (We will establish that the claim also holds for k.)
In step 3 in the first while loop in algorithm A2, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${G_{1 , k}} = G [ {U_1} , {U_k} ]$$
\end{document} is generated, and in step 4, a maximum-weighted (1, r)-matching Mk of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${G_{1 , k}}$$
\end{document} is found. By Theorem 2, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w ( {G_{1 , k}} ) \le c \cdot w ( {M_k} )$$
\end{document}. After merging Mk in Gk, we get a \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( k - 1 )$$
\end{document}-partite graph \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G_{1 ( k ) }^k$$
\end{document}. Suppose that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$M \prime$$
\end{document} is the approximate solution obtained by applying algorithm A2 to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G_{1 ( k ) }^k$$
\end{document}. By the induction hypothesis, we know that \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w ( G_{1 ( k ) }^k ) \le c \cdot w ( M \prime ) ,$$
\end{document} so \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w ( G ) = w ( {G_{1 , k}} ) + w ( G_{1 ( k ) }^k ) \le c \cdot ( w ( {M_k} ) + w ( M \prime ) ) = c \cdot w ( M )$$
\end{document} by step 9 in Algorithm 3). ■
Corollary 1.Suppose G is a weighted complete k-partite graph where each part has c vertices. Algorithm\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$A2$$
\end{document}has an approximation ratio of c.
Proof. Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${M^*}$$
\end{document} be the maximum-weighted k-partite matching in G. So, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$ { \frac { w ( { M^* } } { w ( M ) } } ) \le { \frac { w ( G ) } { w ( M ) } } \le c$$
\end{document}. ■
Corollary 2.Suppose G is a weighted complete k-partite graph whose k parts are\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${U_1} , \ldots , {U_k}$$
\end{document}, and let\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$c = \max \{ \vert {U_1} \vert , \vert {U_2} \vert , \ldots , \vert {U_k} \vert \} $$
\end{document}. The algorithm A2 has an approximation ratio of c.
Proof. From G, we construct a complete k-partite graph \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G ^\prime$$
\end{document} with c vertices in each part by adding new vertices in each part and new edges of weight 0. Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$M ^\prime$$
\end{document} be the matching produced by applying algorithm A2 to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G ^\prime$$
\end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$M = M ^\prime \cap G$$
\end{document}. Since the new edges weights are 0, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$w ( M ^\prime ) = w ( M )$$
\end{document}, so \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$ { \frac { w ( G ) } { w ( M ) } } \le { \frac { w ( G ^\prime ) } { w ( M ^\prime ) } } \le c$$
\end{document}. Thus, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$ { \frac { w ( { M^* } ) } { w ( M ) } } \le { \frac { w ( G ) } { w ( M ) } } \le c$$
\end{document}. ■
6. A Heuristic Algorithm for The Maximum-Weighted K-Partite Matching Problem
In this section, we propose a heuristic algorithm for the maximum-weighted k-partite matching problem. Note that each matched node set in the solution M produced by Algorithm 3 contains at most one node from the first part U1 and at most r nodes from other parts, but each matched node set of a k-partite matching can contain up to r nodes from each part. To allow each matched node set of the approximation to also contain up to r nodes from U1, we propose a novel heuristic algorithm.
Our heuristic algorithm idea is as follows. We first find an \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( r , r )$$
\end{document}-matching M for the subgraph of two parts by the greedy algorithm in Singh et al. (2008) and then perform a merge based on M to get a \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( k - 1 )$$
\end{document}-partite graph \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G ^\prime$$
\end{document}. (Since the definition of merging a \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( r , r )$$
\end{document} matching is very similar to the definition of merging a \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( 1 , r )$$
\end{document} matching, we omit it here.) Next, we find a matching \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$M \prime$$
\end{document} for the \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( k - 1 )$$
\end{document}-partite graph \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G \prime$$
\end{document} using our approximation algorithm, and the matchings M and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$M \prime$$
\end{document} are combined into an approximate solution.
The heuristic algorithm for the maximum-weighted k-partite matching problem appears in Algorithm 4. To explain our algorithm clearly, we reproduce some formatting of the approximation algorithm for the maximum disjoint k-clique problem given in He et al. (2000).
Algorithm 4: The Heuristic Algorithm A3 for the Maximum k-Partite Matching Problem
3: Find an approximate solution Mk of the maximum-weighted (r, r)-matching of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G_{1 , k}^k$$
\end{document} by the greedy algorithm in Singh et al. (2008). Suppose that in Mk, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$S_1^1$$
\end{document} is matched to a vertex set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$S_1^k$$
\end{document}, \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$S_2^1$$
\end{document} is matched to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$S_2^k$$
\end{document}, and so on.
4: Merge Mk in Gk to get the \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( k - 1 )$$
\end{document}-partite graph \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G_{1 ( k ) }^k$$
\end{document}.
5: Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$i = k - 1$$
\end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${G^i} = G_{1 ( k ) }^k$$
\end{document}.
8: Find a maximum-weighted (1, r)-matching Mi of \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G_{1 , i}^i$$
\end{document}. Suppose that in Mi, v1 is matched to the vertex set \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$S_1^i$$
\end{document}, v2 is matched to \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$S_2^i$$
\end{document}, and so on.
9: Merge Mi in Gi to get the \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$( i - 1 )$$
\end{document}-partite graph \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$G_{1 ( i ) }^i$$
\end{document}.
10: Let \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$i = i - 1$$
\end{document} and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${G^i} = G_{1 ( i ) }^i$$
\end{document}.
11: end while
12: Find a maximum-weighted (l, r)-matching M2 of G2.
In this section, we compare our approximation algorithm A2, our heuristic algorithm A3, and the greedy algorithm in Singh et al. (2008) on the basis of the sum of the weights of the edges in the resulting matchings. In our experiments, we build a k-partite graph by generating random edge weights \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$0 \le w \le 1$$
\end{document}. We ran each algorithm on 100 random k-partite graphs with 20 vertices in each part. In the following Tables 1–6, we give the mean value and the standard deviation for the sum of the edge weights for the 100 matchings produced by the three algorithms, for k between 3 and 9. We choose \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$r = 5$$
\end{document} for our algorithms as well as the greedy algorithm in Singh et al. (2008). We have considered other values for r, but due to space limitations, we only list the results for \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$r = 5$$
\end{document}.
The Mean Value and Standard Deviation for the Sum of the Edge Weights in the Matchings for 3-Partite Graphs
From these Tables 1–6, we conclude that algorithm A3 produces better matchings than algorithm A2, which finds better matchings than the greedy algorithm. We believe that this is because algorithm A3 considers the possibility that each matched node set of a k-partite matching can contain up to r nodes from the first part (in step 3). Elsewhere in algorithm A3, an (1, r)-matching is computed exactly, and each matched node set of a k-partite matching is allowed to contain up to r nodes from other parts.
8. Alignment Results of Metabolic Pathways
From the above sections, we concluded algorithm A3 is the best. So we apply Algorithm 1, using algorithm A3 in step 3, to metabolic data from the KEGG (Kyoto Encyclopedia of Genes and Genomes) database to compute the alignment of multiple metabolic pathways. We used the hierarchical enzyme similarity score (Tohsato et al., 2000) to calculate the similarity between enzymes and trivial compound similarity score (Hattori et al., 2003) for compounds. Other algorithmic parameters are as follows: \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\alpha = 0.7 , \beta = 0.5 , { \gamma _{{C_{in}}}} = 0.3 ,$$
\end{document}\documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \gamma _{{C_{out}}}} = 0.3$$
\end{document}, and \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$${ \gamma _E} = 0.4$$
\end{document}.
8.1. Biological significance
Aligning metabolic pathways of multiple phenotype-related microorganisms enables identification of conserved metabolic components, such as compounds, enzymes, or reactions. By analyzing these conserved metabolic components, scientists may gain new insights into metabolic processes, structural information, and evolutionary relationships (for instance, by identifying homologous proteins) (Koyutürk et al., 2004; Pevsner, 2009), or subpathways related to phenotypes involved in production of specific microbial products, such as biological hydrogen. In particular, biological engineers are interested in using these data to identify conserved metabolic pathways related to the production of specific microbial products, such as biological hydrogen.
To evaluate the performance of our algorithm, we aligned the well-characterized tricarboxylic acid (TCA) cycle across five aerobic microorganisms and compared the results with known microbial physiological data. We also aligned the TCA pathway in KEGG across five facultative anaerobes.
8.1.1. TCA-related enzymes
We aligned the TCA cycle pathway (KEGG pathway 00020) across the five aerobic organisms Bordetella bronchiseptica RB50 (bbr), Staphylococcus saprophyticus subsp. saprophyticus ATCC 15305 (ssp), Myxococcus xanthus DK 1622 (mxa), Leptospira interrogans serovar Lai str. 56601 (lil), and Helicobacter pylori HPAG1 (hpa). The resulting alignments for the TCA enzymes appear in Table 7. The parts of resulting alignment for the TCA reactions and compounds are depicted in Table 8.
Results for Aligning the Metabolic Components of KEGG Pathway 00020 (the Tricarboxylic Acid Cycle) Across Five Aerobic Organisms
Only the alignments for enzymes are presented in this table. Each row in the table below represents an alignment of a single enzyme across the organisms Bordetella bronchiseptica RB50 (bbr), Staphylococcus saprophyticus subsp. saprophyticus ATCC 15305 (ssp), Myxococcus xanthus DK 1622 (mxa), Leptospira interrogans serovar Lai str. 56601 (lil), and Helicobacter pylori HPAG1 (hpa). The + entries in the table indicate which enzyme was identified as being aligned for that organism, whereas \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\diamondsuit$$
\end{document} indicates that no aligned enzyme was identified for that organism. Enzymes marked with ★ are part of the TCA cycle.
TCA, tricarboxylic acid.
Results for Aligning the Metabolic Components of KEGG Pathway 00020 (the Tricarboxylic Acid Cycle) Across Five Aerobic Organisms
The parts of alignments for reactions and compounds are presented in this table. Enzyme marked with * is part of the TCA cycle.
The alignment results generated for the TCA cycle pathway demonstrate the ability of our algorithm to identify key enzymes associated with phenotype-related metabolic pathways. In our validation experiment, all TCA enzymes were correctly aligned in the four aligned microorganisms that have complete TCA cycles (bbr, ssp, mxa, and lil). While the presence of the TCA cycle is considered an indicator of aerobic respiration, it is not complete in all aerobic species (White, 2007). The TCA enzymes succinate thiokinase and malate dehydrogenase (MDH) were not aligned in H. pylori, as these two enzymes are missing from hpa in the KEGG data. This absence may be due incomplete data in KEGG or the lack of a complete TCA cycle in hpa. In this case, studies have indicated that only parts of the TCA cycle are active in H. pylori, and that the active components are responsible for providing necessary biosynthetic components (Chalk et al., 1994).
8.1.2. Facultative respiration
To further understand the subpathways involved in central metabolism, we used the KEGG TCA metabolic pathway to align the five facultative organisms Escherichia coli (eco), Shewanella oneidensis MR-1 (son), Zymomonas mobilis (zmo), Listeria innocua (lin), and Streptococcus pneumonia (spn). These five organisms were selected for their potential use in industrial environmental technologies. The enzyme alignment results appear in Table 9. In this study, we omit the reaction and compound alignment results.
Results for Aligning the Metabolic Components of KEGG Pathway 00020 (the Tricarboxylic Acid Cycle) Across Five Facultative Anaerobic Organisms
Only the alignments for enzymes are presented in this table. Each row in the table below represents an alignment of a single enzyme across the organisms Escherichia coli (eco), Shewanella oneidensis MR-1 (son), Zymomonas mobilis (zmo), Listeria innocua (lin), and Streptococcus pneumonia (spn). The \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$+$$
\end{document} entries in the table indicate which enzyme was identified as being aligned for that organism, whereas \documentclass{aastex}\usepackage{amsbsy}\usepackage{amsfonts}\usepackage{amssymb}\usepackage{bm}\usepackage{mathrsfs}\usepackage{pifont}\usepackage{stmaryrd}\usepackage{textcomp}\usepackage{portland, xspace}\usepackage{amsmath, amsxtra}\usepackage{upgreek}\pagestyle{empty}\DeclareMathSizes{10}{9}{7}{6}\begin{document}
$$\diamondsuit$$
\end{document} indicates that no aligned enzyme was identified for that organism. Enzymes marked with ★ are part of the TCA cycle.
Alignment results for these species reveal that only two bacterial species, E. coli and S. oneidensis, contain complete TCA cycles, consistent with the ability of these organisms to thrive in a number of aerobic habitats, such as aquatic systems. As such, one would expect these organisms to use an oxidative pathway such as the TCA cycle to break down simple organic matter (e.g., glucose) and generate the adenosine triphosphate metabolites necessary for growth (White, 2007).
Results for the alignment also indicated that the TCA cycle was incomplete in Z. mobilis and L. innocua due to the absence of two important TCA enzymes, MDH and α-ketoglutarate dehydrogenase (KGDH). Unlike E. coli and S. oneidensis, these bacterial species tend to thrive in low-oxygen environments, so complete TCA cycles are not necessarily optimal for them. While these organisms can utilize some TCA reactions to produce biosynthetic precursors, the absence of MDH and KGDH may play an important role in regulating overall cell growth and energy requirements.
In the case of Z. mobilis, a recent genomic study by Seo et al. found that Z. mobilis ZM4 does not contain genes that encode these two enzymes, and the lack of these enzymes is likely responsible for low cell biomass yields compared to other organisms with complete TCA cycles. In addition, Seo et al. noted that Z. mobilis relied on the Entner–Doudoroff pathway to metabolize simple sugars such as glucose and fructose. As such, it incorporates high quantities of glucose for the production of end-products such as ethanol, and without a complete TCA cycle, most of this energy is directed to ethanol production rather than cellular growth (Seo et al., 2005).
Similar to Z. mobilis, we found that L. innocua did not contain the two TCA enzymes KGDH and MDH. L. innocua is a nonpathogenic bacterium commonly found in aquatic and terrestrial environments (Karlin et al., 2004). Our findings are consistent with comparative genomic studies by Karlin et al. (2004) that found L. innocua and other Listeria species to contain incomplete TCA cycles. The advantages of having an incomplete cycle are not well understood at this time, but further alignments of metabolic pathways involved in glycolysis, pentose phosphate metabolism, and the reductive TCA cycle may shed light onto these advantages, or even lead to alternative routes for the production of biosynthetic precursors such as succinyl-CoA.
8.1.3. Another five aerobic and anaerobic microorganisms
In addition, we still align the metabolic pathway (00020) for five aerobic and anaerobic microorganisms. Aerobic microorganisms are Aquifex aeolicus, Acidothermus cellulolyticus, Bdellovibrio bacteriovorus, B. bronchiseptica, and E. coli K-12 MG1655. Anaerobic species used in this study are Geobacter sulfurreducens, Herminiimonas arsenicoxydans, Mannheimia succiniciproducens, Pelobacter carbinolicus, and Geobacter metallireducens.
Results for multiple alignments of pathway in aerobic and anaerobic microorganisms demonstrate the ability of the algorithm to identify enzymes and compounds specific to our target pathway and individual phenotypes.
We give the details of experimental results. We align the following metabolic pathways: aae00020, ace00020, bba00020, bbr00020, eco00020, which have a common subpath as follows (Fig. 1).
A common subpath of aae00020, ace00020, bba00020, bbr00020, and eco00020.
The following Tables 10 and 11 are part of our experimental results. Our experimental results show that our algorithm correctly aligns the common subpath.
We align the following metabolic pathways: gsu00020, har00020, msu00020, pca00020, gme00020, which have a common subgraph as follows (Fig. 2).
. A common subgraph of gme00020, gsu00020, har00020, msu00020, and pca00020.
The following Tables 12 and 13 are part of our experimental results. Our experimental results show that our algorithm correctly aligns the common subgraph.
Where C00158 denotes citrate; C00024 denotes acetyl-CoA; C16255 denotes S-acetyl-dihydrolipoamide-E; C05125 denotes 2-hydroxyethyl-ThPP; C15973 denotes dihydrolipoamide-E; and C15972 denotes lipoamide-E.
In addition, we choose organisms from the same anaerobic phenotype. We align the reductive acetyl-CoA pathway (00630) for four anaerobic microorganisms, which are chy (Carboxydothermus hydrogenoformans Z-2901), cdf (Clostridium difficile 630), mta (Moorella thermoacetica ATCC 39073), and dat (Desulfobacterium autotrophicum HRM2). We align the toluene degradation pathway (00632) for five anaerobic microorganisms, which are tmz (Thauera sp. MZ1T), dar (Dechloromonas aromatica), gme (Geobacter metallireducens), eba (Aromatoleum aromaticum EbN1), and bvi (Burkholderia vietnamiensis G4). We align the reductive TCA pathway (00720) for five anaerobic microorganisms, which are hdu (Haemophilus ducreyi 35000HP), cli (Chlorobium limicola DSM 245), nam (Nautilia profundicola AmH), msu (Mannheimia succiniciproducens MBEL55E), and tdn (Thiomicrospira denitrificans ATCC 33889). Experimental results (the following Tables 14 and 15) show our algorithm can correctly identify common subnetworks.
The Identified Subnetworks for Specific Pathways in Organisms of Anaerobic Phenotype
Furthermore, we choose three organisms from the same aerobic phenotype: Aquifex aeolicus (aae), Acidothermus cellulolyticus (ace), and Bordetella bronchiseptica RB50 (bbr). From these organisms, we align 10 pathways with common subnetworks. Experimental results (the following Tables 16 and 17) show our algorithm can correctly identify nine common subnetworks.
The Identified Subnetworks for Pathways in aae, ace, and bbr
However, since the algorithm by Tohsato et al. (2000) only considered the similarity of enzymes in multiple pathways and did not consider the similarities of topography, compounds, and reactions, their algorithm cannot align common subnetworks.
8.2. Statistical significance
The z-score is a common measure of statistical significance. In Ay et al. (2008), Ferhat Ay uses the z-score of the pairwise alignment to measure the statistical significance of pairwise alignment. In this study, we also use the z-score of multiple alignment to measure the statistical significance of multiple alignment.
We compare the z-score of alignments of the same pathways in multiple organisms with the z-score of alignment of different pathways in multiple organisms. The results are in the following table.
In this article, we have considered the multiple alignment problem for metabolic pathways. We have developed two algorithms for aligning multiple pathways based on similarities between compounds, reactions, enzymes, and topological structure. We have also reduced the problem of aligning multiple metabolic pathways to the maximum-weighted k-partite matching problem.
For the maximum-weighted k-partite matching problem, we presented an approximation and a heuristic algorithm. To design our algorithms, we introduced the maximum-weighted (1, r)-matching problem and gave a polynomial-time algorithm for solving this problem, and we designed our k-partite matching algorithms based on an algorithm for solving the maximum-weighted (1, r)-matching problem. Singh et al. (2008) proposed a greedy algorithm for the maximum-weighted k-partite matching problem, and we compare this algorithm with the ones proposed in this article. Experimental results show that our heuristic algorithm is the most accurate.
Finally, we applied our heuristic algorithm to compute the alignment of multiple metabolic pathways, and our experimental results verify that our algorithm correctly identifies the common subnetworks of multiple pathways.
Footnotes
Acknowledgments
This research has been partly supported by “faculties' starting funding of Guangzhou University,” by the “Algorithms Research for Analysis of Large-Scale Biological Networks” project (IIPL-2011-001) from Shanghai Key Laboratory of Intelligent Information Processing, and has also been supported by the “Exploratory Data Intensive Computing for Complex Biological Systems” project from U.S. Department of Energy (Office of Advanced Scientific Computing Research, Office of Science). The work of N.F.S. was also sponsored by the Laboratory Directed Research and Development Program of Oak Ridge National Laboratory. Oak Ridge National Laboratory is managed by UT-Battelle for the LLC U.S. D.O.E. under contract no. DEAC05-00OR22725. In addition, Wenbin Chen's research has been also partly supported by the National Natural Science Foundation of China (NSFC) under Grant No.11271097, the research project of Guangzhou education bureau under Grant No. 2012A074, the project IIPL-2011-001 from Shanghai Key Laboratory of Intelligent Information Processing, and the project KFKT2012B01 from State Key Laboratory for Novel Software Technology, Nanjing University.
Author Disclosure Statement
No competing financial interests exist.
References
1.
AyF., KahveciT., and Crecy-LagardV.2008. Consistent alignment of metabolic pathways without any abstraction. Comput. Syst. Bioinformatics Conf., 7, 237–248.
2.
BonoH., OgataH., GotoS., et al.1998. Reconstruction of amino acid biosynthesis pathways from the complete genome sequence. Genome Res. 8, 203–210.
3.
ChalkP.A., RobertsA.D., and BlowsW.M.1994. Metabolism of pyruvate and glucose by intact cells of Helicobacter pylori studied by 13C NMR spectroscopy. Microbiology. 140, 2085–2092.
4.
ChenW.B., RochaA., HendrixW., et al.2010. The multiple alignment algorithm for metabolic pathways without abstraction, 669–678. The 10th IEEE International Conference on Data Mining Workshops, Sydney, Australia.
5.
DandekarT., SchusterS., SnelB., et al.1999. Pathway alignment: Application to the comparative analysis of glycolytic enzymes. Biochem. J., 343, 115–124.
6.
FredmanM.L., and TarjanR.E.1984. Fibonacci heaps and their uses in improved network optimization algorithms, 338–346. The 25th IEEE Symposium on Foundations of Computer Science, Singer Island, Florida.
7.
GareyM.R., and JohnsonD.S.1979. Computers and Intractability. Freeman, New York.
8.
HattoriM, OkunoY., GotoS., et al.2003. Development of a chemical structure comparison method for integrated analysis of chemical and genomic information in the metabolic pathways. J. Am. Chem. Soc., 125, 11853–11865.
9.
HeG., LiuJ., and ZhaoC.2000. Approximation algorithms for some graph partitioning problems. J. Graph Algorithms Appl., 4, 1–11.
10.
KarlinS., TheriotJ., and MrázekJ.2004. Comparative analysis of gene expression among low G+C gram-positive genomes. Proc. Natl. Acad. Sci. U S A., 101, 6182–6187.
11.
KelleyB.P., SharanR., KarpR.M., et al.2003. Conserved pathways within bacteria and yeast as revealed by global protein network alignment. Proc. Natl. Acad. Sci. U S A., 100, 11394–11399.
12.
KoyutürkM., GramaA., and SzpankowskiW.2004. An efficient algorithm for detecting frequent subgraphs in biological networks. Bioinformatics. 20, 200–207.
13.
LiY., de RidderD., de GrootM., et al.2008. Metabolic pathway alignment between species using a comprehensive and flexible similarity measure. BMC Syst. Biol. 2, 111.
14.
OgataH., FujibuchiW., GotoS., et al.2000. A heuristic graph comparison algorithm and its application to detect functionally related enzyme clusters. Nucl. Acids Res., 28, 4021–4028.
15.
PevsnerJ., ed. 2009. Bioinformatics and Functional Genomics, 2nd ed. Wiley-Blackwell.
16.
PinterR.Y., RokhlenkoO., Yeger-LotemE., et al.2005. Alignment of metabolic pathways. Bioinformatics. 21, 3401–3408.
17.
SeoJ.-S., ChongH., ParkH.S., et al.2005. The genome sequence of the ethanologenic bacterium Zymomonas mobilis ZM4. Nat. Biotechnol., 23, 63–68.
18.
SharanR., and IdekerT.2006. Modeling cellular machinery through biological network comparison. Nat. Biotechnol., 24, 427–433.
19.
SinghR., XuJ.B., and BergerB.2008. Global alignment of multiple protein interaction networks. Pac. Symp. Biocomput. 13, 303–314.
20.
SridharP., KahveciT., and RankaS.2007. An iterative algorithm for metabolic network-based drug target identification. Pac. Symp. Biocomput., 12, 88–99.
21.
TianW., and SamatovaN.F.2009. Pairwise alignment of interaction networks by fast identification of maximal conserved patterns. Pac. Symp. Biocomput., 2009, 99–110.
22.
TohsatoY., MatsudaH., and HashimotoA.2000. A multiple alignment algorithm for metabolic pathway analysis using enzyme hierarchy. Proc. Int. Conf. Intell. Syst. Mol. Biol. 8, 376–383.
23.
TohsatoY., and NishimuraY.2007. Metabolic pathway alignment based on similarity between chemical structures. IPSJ Digital Courier. 3, 736–745.
24.
WernickeS., and RascheF.2007. Simple and fast alignment of metabolic pathways by exploiting local diversity. Bioinformatics. 23, 1978–1985.
25.
WestD.B.2004. Introduction to Graph Theory, 2nd ed. China Machine Press, China.
26.
WhiteD.2007. The Physiology and Biochemistry of Prokaryotes. Oxford University Press, New York.
27.
YuH., LuscombeN.M., LuH.X., et al.2004. Annotation transfer between genomes: Protein-protein interologs and protein-DNA regulogs. Genome Res. 14, 1107–1118.
