An illustrative example for the reduction from the MWIS problem to the

metabolic pathway alignment problem. (

**a**) A vertex-weighted graph

*G* that is an input to the MWIS problem. Four vertices labeled from “1” to “4” have weights from w(1) to w(4) respectively. The edges are labeled from “a” to “e” and are unweighted and undirected. (

**b**) Two

pathways and

constructed from

*G*. We create one vertex for each vertex of

*G* in both pathway

and

. Then, for

we add a vertex labeled with a letter for each edge of

*G* and add edges from it to the vertices on its both ends in

*G*. In order to simplify the figure, we match the label of each vertex in

with that of its corresponding vertex or edge in

*G*. Similarly, we match the label of each vertex in

with that of its corresponding vertex in

*G*. (

**c**) The assignment of similarity scores for

subnetwork pairs one from

and the other from

. Each vertex here shows a

subnetwork from

or

. The label of each vertex lists the vertices contained in that

subnetwork. For instance, label “1ab” indicates the

subnetwork of

that consists of the three vertices labeled as “1,” “a,” and “b.” The edge weights show the similarity of the two subnetworks corresponding to the two vertices at its end points.

## PubMed Commons