BACKGROUND
complex diseases are likely to be associated with the effects of multiple genes, proteins and biological pathways  <cit> .
pathway analysis methods that combine multiple types of high-throughput data, such as genomics and proteomics, have become the first choice to gain insights into the pathogenesis of complex diseases.
a biological pathway that reduces data involving thousands of altered genes and proteins into a smaller and more interpretable set of altered processes and combines multiple types of high-throughput data plays an important role in understanding the mechanisms of complex diseases, improving clinical treatment, and discovering drug targets and biomarkers  <cit> .
the most commonly employed traditional pathway analysis methods use classical pathway databases  to analyse gene expression profile data.
these analyses use statistical methods to identify significant pathways in a particular biological process, such as gsea  <cit> , page  <cit> , gage  <cit>  and meanabs  <cit> .
a limitation of this class of algorithms is their ignorance of interactions between genes and proteins because neither network topology nor dynamics is taken into account  <cit> .
these limitations are addressed by network-based pathway analyses.
accordingly, several pathway analysis models that reflect the laws of life activities and employ network topology information have been proposed  <cit> , such as spia  <cit> , paradigm  <cit> , pathologist  <cit> , active modules  <cit> , ambient  <cit> , giga  <cit>  and ganpa  <cit> .
although the above methods utilize network topology information, they only consider the topological structure of the pathway itself and do not take into account the information of pathway external genes in biological networks; thus, they do not fully mine pathway information.
for example, only the pathway internal topology is utilized by the spia method, whereas the pathologist model only computes the probability of an interaction of pathway internal genes being active when it is consistent with the known regulatory logic of the pathway.
hence, how to take the interactions between internal and external genes of the pathway and between pathways into account in the pathway analysis method is the main problem addressed in this paper.
to that end, we proposed a novel network-based pathway analysis method.
first, we integrated protein-protein interaction  information, gene expression profile data and pathway databases into the pathway analysis and constructed two whole-genome level gene-gene interaction networks.
then, we expanded pathways based on the k-walks algorithm  <cit>  to two small networks in two weighted networks .
finally, we scored the pathways corresponding to the gene expression profile data based on the correlations of these two small networks to identify significant pathways .
fig.
<dig> workflow of the proposed method
methods
construction of a weighted gene-gene interaction network
ppi network provides a valuable framework to elucidate the functional organization of the proteome.
however, existing ppi networks cannot accurately describe the interactions between proteins in specific conditions and have different degrees of false positive and false negative results because most large-scale ppi networks are obtained in different experimental conditions, predicted/extracted using different algorithms  <cit> .
additionally, the interaction or the intensity between proteins varies in different cells or tissues.
the gene co-expression network  is an undirected graph where each node corresponds to a gene and a pair of nodes is connected with an edge if there is a significant co-expression relationship between them  <cit> .
using gene expression profiles obtained from a number of genes for several samples or experimental conditions, a gene co-expression network can be constructed by looking for pairs of genes that show a similar expression pattern across samples.
in this study, the weight of each pair of genes is calculated by the pearson’s correlation coefficient.
pearson’s correlation coefficient was selected as the co-expression measurement because it was the most popular co-expression measurement used in the construction of gene co-expression networks.
the absolute values correspond to an interaction mechanism where the intensity of one gene is related to its co-expressed gene.
however, a gene co-expression network does not guarantee the existence of a real interaction between the corresponding proteins; instead, it only suggests that there may be an interaction between the proteins.
to accurately describe the change in gene interactions for several samples or experimental conditions, here we constructed two weighted gene-gene interaction networks  with ppi and gcn .
fig.
<dig> construction of the weighted gene-gene interaction network .
the ppi network comes from i2d, the co-expression weighted network is from gene expression profiling, and the weight of each pair of genes is calculated by pearson’s correlation coefficient.
finally, the ppi network and the co-expression weighted network are merged into the weighted gene-gene interaction network.
we obtain two weighted gene-gene interaction networks under two phenotype datasets
pathway-based extension of the sub-network
the gene-gene interaction of pathway is different in different tissues or samples.
these differences may be caused by changes in the interactions between internal genes of the pathway or between pathway and neighbor genes.
to assess the significance of the pathway in different phenotypic data, we expanded the pathway based on the k-walk algorithm  <cit>  by considering all of the above factors in two weighted gene-gene interaction networks separately.
the pathway-based extension of the sub-network was constructed as follows:
let g= comprise a set v of genes and a set e of edges denote the weighted gene-gene interaction network with e⊆v×v.
let n=∣v∣reflect the number of genes.
symmetric matrix a represents the weighted n×n adjacency matrix of g, where a
ijdenotes the weight of the edge connecting gene i to gene j. let d
i represent the weighted degree of each gene node i where di=∑j=1naij.
then, a
ij is calculated by pearson’s correlation coefficient as:
<dig> aij=|cor|βxi,xjisexpressiondataofgenevi,vj0otherwise
where β= <dig>
given a gene set s  of a pathway belonging to a subset of g, we formally define an edge relevance function er:e→ℝ+ that maps any edge to its relevance.
the extended process of a gene set of a pathway simulates random walks on a graph by the markov chain model.
the possibility of transiting from gene i to gene j is calculated as:
<dig> pij=aijdi
here, a gene set s is a set of absorbing states of the markov chain.
if the random walk starts from gene x, the modified transition will be:
<dig> xpij=1i∈s∖{x}andi=j0i∈s∖{x}andi≠jpijotherwise
then, the transition matrix is described as follow:
<dig> xp=xqxr0i
where x
q is a matrix that denotes transient states, x
r is a matrix that denotes the transition probability from transient states to absorbing states, and i is the identity matrix.
after k steps, the transition matrix becomes k.
given that the walk started in state x, the joint probability of visiting the edge e between step k and k+ <dig> is calculated as follow:
<dig> pxk=i,xk+1=j,l|x0=x=fjisatransientstatel−1xiijjisanabsorbingstate
where l is a total walk length, f=∑r∈s∖{x}xiijjr, xi is the probability of transiting from x to i in k steps.
the probability of a walk of length l starting in x is calculated as follow:
<dig> p=∑r∈s∖{x}xr
the e is defined as the number of times a random walk starts in x using the transition from i to j. given that the walk length is l, the conditional expectations of e is given by:
<dig> e=∑k=0l−1pp
let l
max denote a maximal walk length.
then:
<dig> e=∑l=1lmaxe
finally, the edge relevance er is given by:
er=
<dig> ∑r∈slx|ee|l≤lmax−ee|l≤lmax|∀∈e
where the vector l
x represents an initial probability distribution.
here, the maximal relevance score that can lead to a connected subgraph is chose as the threshold θ. finally, a subnetwork is obtained by keeping only edges with relevance scores er above a threshold value θ .
in the paper, we set l
max to  <dig> by default.
fig.
<dig> an example of a pathway-based extension.
blue nodes denote a gene set of a pathway and red nodes denote the expanded genes that are most associated with the corresponding pathway
identification of significant pathways
for a given pathway i, the pathway was expanded in two weighted gene-gene interaction networks for two phenotypic datasets separately.
the union genes of two expanded pathway play a role in performing a similar function in normal or tumor tissues.
moreover, genes in expanded pathway from tumor and normal tissues are almost different.
the union genes construct sub-networks in two weighted networks.
these sub-networks weights’ differences can describe the change of pathways between different phenotypes.
accordingly, we calculate the difference between the two pathway-based sub-networks reflects the change of the given pathway for the two phenotypic datasets through the union of the two sub-networks.
let union_pathway  denote the union of two sub-networks  that are the expansion of pathway i in two weighted gene-gene interaction networks .
then, we mapped union_pathway  into the two weighted gene-gene interaction networks  and obtained two edge weight vectors t_w  and n_w .
pearson’s correlation coefficient was calculated as:
corri=
<dig> ∑k=1n∑k=1n2∑k=1n <dig>
where n is the dimension of the vector and t_w¯=1n∑k=1nt_wk, n_w¯=1n∑k=1nn_wk.
finally, we calculated score , which depicts the difference in pathway i for two phenotypic datasets as follow:
<dig> score=1−|corri|
here, score  is a measure depicting the relevance degree between pathway i and the corresponding disease .
RESULTS
data
the breast invasive carcinoma  dataset was downloaded from the tcga  website .
the brca dataset consists of  <dig> samples obtained from comparing  <dig> breast cancer samples with  <dig> normal samples using the agilent platform.
the second dataset was available via the gene expression omnibus .
this dataset compared  <dig> pathologic complete response  samples and  <dig> residual disease  samples  <cit>  .
ppi network  was obtained from the interologous interaction database  website  <cit>  .
ppi was mapped into the gene-gene interaction  data through the uniprot website .
finally,  <dig>  unique gene pairs were selected for brca, and  <dig>  unique gene pairs were selected for gse <dig> by data pretreatment.
the kegg pathways were downloaded from the consensuspathdb website .
we selected  <dig> pathways related to humans by screening; only genes of pathways belonging to the brca gene set were used in the downstream analysis.
the breast cancer gene set was downloaded from website.
to identify the significance of the given pathway, first, we dealt with the ppi data.
the ppi network was mapped into the gene-gene interaction  network in which the weight of each pair of genes was calculated using high-throughput gene expression profiling data.
finally, we obtained two weighted gene-gene interaction networks for the two phenotypic datasets.
the weighted gene-gene interaction network has  <dig>  vertices and  <dig>  edges for brca.
based on the above algorithm, we expanded a gene set of the given pathway based on the k-walks algorithm into two sub-networks in two weighted networks .
then, we compared the number of the genes in the original pathway and the expanded pathway .
finally, the union of the two sub-networks served as the ultimate expansion of the given pathway.
fig.
<dig> the number of the genes in the original pathway and the expanded pathway.
through the diagram, we found that every pathway was validly expanded except pathway hsa <dig> because it only contained one gene from the original pathway
next, we ran the proposed approach using the brca dataset.
to provide a more comprehensive understanding of the proposed method, we discuss the method from the following aspects separately.
the pathway score
based on the background mentioned above, each pathway score depicts the degree of relevance between the given pathway and the corresponding disease.
all scores were calculated using algorithm  <dig> .
the top  <dig> pathways were tabulated based on their scores .
note: yes if the pathway was also ranked in the spia or gsea top 15; no if otherwise
top pathways identified by the proposed method should be significantly associated with the breast cancer risk.
to test the idea, we compared the intersections of the breast cancer gene set and pathway gene sets before and after expansion .
the breast cancer gene set comes from sidd which integrates  <dig> disease gene knowledge sources.
we found that more genes associated with breast cancer were expanded to the original pathway gene set through pathway expansion.
this result demonstrates that the proposed method can expand genes associated with the corresponding disease.
fig.
<dig> comparison between the gene number of intersections of the breast gene set and pathway gene sets before and after expansion
analysis of the top  <dig> brca pathways
in order to prove that the pathways identified by the proposed method are associated with the breast cancer risk, we need to look for the supports of biological knowledge and other methods.
table  <dig> shows that top  <dig> pathways identified from brca by the proposed method are significantly associated with the breast cancer risk through reference.
here we give the supports of biological knowledge and other methods for the top  <dig> brca pathways.
the number  <dig> ranked significant pathway identified by our method was vitamin b <dig> metabolism .
growing evidence suggests that the lack of several trace elements, such as vitamin b <dig> and folate, can induce dna damage , eventually leading to tumors, cancers and a variety of degenerative diseases  <cit> .
there is a significant negative correlation between the plasma b <dig> level and different types of cancer.
vitamin b <dig> can reduce the homocysteine and pyridoxal phosphate levels, which have potential biological effects on tumors.
vitamin b <dig> deficiency leads to lower serine hydroxymethyltransferase activity, lower generation of  <dig> -methylenetetrahydrofolate and the generation of a dump instead of a dtmp mismatch to dna, which is more likely to lead to a chromosome chain break and /or impair dna excision repair.
the reduced generation of  <dig> -methylenetetrahydrofolate may lead to dna hypomethylation.
abnormal methylation of dna has been found in different tumor types  <cit> .
vitamin b <dig> deficiency can increase the sensitivity of the steroid hormone,which may lead to breast cancer or colon cancer  <cit> .
these findings demonstrate that the proper intake of vitamin b <dig> can reduce the risk of breast cancer; therefore, this pathway is significantly associated with the breast cancer risk.
the number  <dig> ranked significant pathway identified by the proposed method was synthesis and degradation of ketone bodies .
ketone bodies  are sufficient to drive mitochondrial biogenesis in human breast cancer cells  <cit> .
carcinoma-associated fibroblasts  produce “mitochondrial fuels”, including lactic acid, ketones, fatty acids, and glutamine, that provide a "eutrophication" microenvironment for tumor cells and promote tumor cell proliferation when metabolized; these fuels are the major cellular components of the breast cancer stroma  <cit> .
it was reported that caf reduced the apoptosis of human breast cancer mcf <dig> cells induced by tamoxifen and fulvestrant by  <dig> -fold and  <dig> -fold, respectively  <cit> .
lactic acid and ketones are sufficient to induce tamoxifen resistance in breast cancer mcf <dig> cells.
metformin and arsenic trioxide can overcome caf-induced drug resistance in mcf <dig> cells.
these findings indicate that this pathway is also significantly associated with the breast cancer risk.
the proposed method ranked the sulphur relay system  in 3rd place.
sulphur enables the transport of oxygen across cell membranes.
oxygen is necessary for healthy cellular regeneration in mammals.
therefore, sulphur deficiencies may promote sickness and disease.
sulphur is commonly used as an herbal medicine to treat inflammation and cancer and organic sulphur has been studied in several types of cancers and found to have remarkable anti-cancer benefits.
methylsulfonylmethane  is an organic sulphur-containing natural compound without any toxicity.
it was found that msm substantially decreased the viability of human breast cancer cells in a dose-dependent manner and recommended the use of msm as a trial drug for the treatment of all types of breast cancers  <cit> .
leimkühler et al.
pointed out that sulphur not only prevented but also helped reverse cancer  <cit> .
hence, the sulphur relay system is significantly associated with the breast cancer risk to some extent.
phenylalanine, tyrosine and tryptophan biosynthesis  was ranked 4th in the list of proposed methods.
eno <dig> in phenylalanine tyrosine and tryptophan biosynthesis was significantly overexpressed in her-2/neu positive breast tumors  <cit> .
this finding indicates that this pathway is associated with breast cancer to some extent; however, the clear relationship between this pathway and breast cancer re-quires further verification.
the 5th ranked pathway was glycosaminoglycan biosynthesis .
abnormal glycosaminoglycan  concentrations have been reported for various types of tumors, suggesting that they may play a role in neoplasia.
recently, cell biology studies revealed that glycosaminoglycans were among the key macromolecules that affected cell properties and functions by acting directly on cell receptors or via interactions with growth factors.
the interactions of gags with growth factors, cytokines and growth factor receptors have been implicated in cancer growth and progression.
gags are involved in signalling cascades that regulate the angiogenesis, invasion and metastasis of malignant cells.
investigations of the fine structures and specific biological roles of gags has led to novel therapeutic approaches .
the above references denote that glycosaminoglycan biosynthesis and breast cancer have a certain degree of correlation.
the top 6– <dig> pathways are also associated with human breast cancer .
based on the table  <dig>  one can argue that the proposed method is very efficient in identifying significant pathways of the corresponding complex disease.
classification performance using the original genes and expanded genes of the pathway
to estimate the classification performance of the top  <dig> expanded pathways, we firstly prepared our data set consisted of  <dig> normal and  <dig> tumor samples randomly derived from the brca dataset.
the original genes and expanded genes of the pathway were selected classification features and svm is employed to classify the selected samples.
next, a 10-fold cross validation was used to train and test svm.
the above experiment was repeated  <dig> times and the average accuracy of svm is shown in fig.
<dig>
fig.
<dig> cross validation accuracy using 10-fold cross validation
in results, the lowest accuracy was  <dig>  and the highest accuracy was  <dig> .
the experimental results suggested that the union of the original genes and expanded genes of the pathway had a good classification ability and that the top  <dig> pathways were significantly different between the two phenotypic data sets.
analysis using alternative methods
to assess the validity of the proposed approach, we analysed the same data using gsea and spia.
the gsea approach searches for gene sets that are enriched at the top or bottom of the ranked list of all genes.
this method is a typical representative of the gene set enrichment analysis methods.
the spia method scores a gene product as highly impactful if it points to other impactful gene products in the network diagram.
this method is a representative of the network-based pathway analysis approaches.
therefore, we compared our method with gsea and spia.
it was interesting to examine pathways ranked at the top by our method but not by gsea and spia, which reflected the validity of our method.
in gsea, the analysis performed  <dig> permutations with an fdr cutoff of 25%.
then,  <dig> pathways were identified  of which  <dig> were found among the top  <dig> pathways identified using the proposed method .
in spia, a significant threshold of 5% was used on the fdr corrected p-values to infer pathway significance.
then,  <dig> pathways were identified  of which one was identified by the proposed method .
the spia did not identify any of the top  <dig> pathways identified using the proposed method.
validation of the alternative data set
to test the effectiveness of the proposed method, we ran the proposed approach on gse <dig>  the data were obtained from response and survival following taxane-anthracycline chemotherapy for newly diagnosed invasive breast cancer.
anthracyclines and taxanes are the two most active classes of cytotoxic agents for early and advanced stage breast cancer and thus are commonly used as a component of either adjuvant or neoadjuvant therapy and/or in patients with metastatic breast cancer   <cit> .
finally, we also obtained two weighted gene-gene interaction networks for the two phenotypic datasets.
the weighted gene-gene interaction network has  <dig>  vertices and  <dig>  edges for gse <dig>  our intention was to identify significant pathways for breast cancer patients before and after taxane-anthracycline use and to evaluate the pharmacological mechanism of taxane-anthracycline.
among the top  <dig> pathways identified using the proposed method, which were significant pathways for taxane-anthracycline except for collecting duct acid secretion pathway , the gsea and spia did not identify any.
the relationship between collecting duct acid secretion pathway and taxane-anthracycline and/or breast cancer requires further verification.
the results  showed that our approach discovered significant pathways for taxane-anthracycline.
the top  <dig> pathways are shown in table  <dig>
note: yes if the pathway was also ranked in spia or gsea top 15; no if otherwise
the significantly impacted pathways identified by the proposed method in the corresponding conditions were mostly consistent with the known biological processes.
accordingly, the novel proposed method is of methodological and biological significance for future research.
CONCLUSIONS
pathway analysis not only reduces data involving thousands of altered genes and proteins to a smaller and more interpretable set of altered processes but can also combine multiple types of high-throughput data.
the analysis results play an important role in elucidating the mechanisms of complex diseases, improving clinical treatment, and discovering drug targets and biomarkers.
therefore, pathway-based analysis of complex diseases has become a research hotspot.
to date, these methods have entered the third stage  <cit> : 1) pathway-based gene set enrichment analysis; 2) pathway-based functional class clustering and scoring approaches; and 3) network-based pathway approaches.
unlike existing pathway analysis approaches that do not take into account the interaction between internal and external genes of the pathway and between pathways, we propose a novel approach that addresses the above-mentioned limitations by expanding a pathway based on the k-walk algorithm to two small networks in two weighted networks .
finally, our approach effectively identified significant pathways that corresponded to a complex disease through a series of verification steps.
it is undeniable that the pathways identified by gsea and spia but not by our method are mostly significantly associated with the breast cancer risk.
based on the above analysis, our method combined with gsea may produce better results.
hence, we will combine our method with gsea in future studies.
this study provides a new research direction for the pathway-based analysis of complex diseases.
we will employ more datasets to assess the validity of our approach in future research.
additional files
additional file  <dig> table s <dig>  the scores of pathways from brca.
additional file  <dig> table s <dig>  the results of gsea from brca.
additional file  <dig> table s <dig>  the results of spia from brca .
additional file  <dig> table s <dig>  the scores of pathways from gse <dig>

 complex diseases are likely to be associated with the effects of multiple genes, proteins and biological pathways. pathway analysis methods that combine multiple types of high-throughput data, such as genomics and proteomics, have become the first choice to gain insights into the pathogenesis of complex diseases. a biological pathway that reduces data involving thousands of altered genes and proteins into a smaller and more interpretable set of altered processes and combines multiple types of high-throughput data plays an important role in understanding the mechanisms of complex diseases, improving clinical treatment, and discovering drug targets and biomarkers. the most commonly employed traditional pathway analysis methods use classical pathway databases to analyse gene expression profile data. these analyses use statistical methods to identify significant pathways in a particular biological process, such as gsea, page, gage and meanabs. a limitation of this class of algorithms is their ignorance of interactions between genes and proteins because neither network topology nor dynamics is taken into account. these limitations are addressed by network-based pathway analyses. accordingly, several pathway analysis models that reflect the laws of life activities and employ network topology information have been proposed, such as spia, paradigm, pathologist, active modules, ambient, giga and ganpa. although the above methods utilize network topology information, they only consider the topological structure of the pathway itself and do not take into account the information of pathway external genes in biological networks; thus, they do not fully mine pathway information. for example, only the pathway internal topology is utilized by the spia method, whereas the pathologist model only computes the probability of an interaction of pathway internal genes being active when it is consistent with the known regulatory logic of the pathway. hence, how to take the interactions between internal and external genes of the pathway and between pathways into account in the pathway analysis method is the main problem addressed in this paper. to that end, we proposed a novel network-based pathway analysis method. first, we integrated protein-protein interaction information, gene expression profile data and pathway databases into the pathway analysis and constructed two whole-genome level gene-gene interaction networks. then, we expanded pathways based on the k-walks algorithm to two small networks in two weighted networks. finally, we scored the pathways corresponding to the gene expression profile data based on the correlations of these two small networks to identify significant pathways. fig. workflow of the proposed method methods construction of a weighted gene-gene interaction network ppi network provides a valuable framework to elucidate the functional organization of the proteome. however, existing ppi networks cannot accurately describe the interactions between proteins in specific conditions and have different degrees of false positive and false negative results because most large-scale ppi networks are obtained in different experimental conditions, predicted/extracted using different algorithms. additionally, the interaction or the intensity between proteins varies in different cells or tissues. the gene co-expression network is an undirected graph where each node corresponds to a gene and a pair of nodes is connected with an edge if there is a significant co-expression relationship between them. using gene expression profiles obtained from a number of genes for several samples or experimental conditions, a gene co-expression network can be constructed by looking for pairs of genes that show a similar expression pattern across samples. in this study, the weight of each pair of genes is calculated by the pearson’s correlation coefficient. pearson’s correlation coefficient was selected as the co-expression measurement because it was the most popular co-expression measurement used in the construction of gene co-expression networks. the absolute values correspond to an interaction mechanism where the intensity of one gene is related to its co-expressed gene. however, a gene co-expression network does not guarantee the existence of a real interaction between the corresponding proteins; instead, it only suggests that there may be an interaction between the proteins. to accurately describe the change in gene interactions for several samples or experimental conditions, here we constructed two weighted gene-gene interaction networks with ppi and gcn. fig. construction of the weighted gene-gene interaction network. the ppi network comes from i2d, the co-expression weighted network is from gene expression profiling, and the weight of each pair of genes is calculated by pearson’s correlation coefficient. finally, the ppi network and the co-expression weighted network are merged into the weighted gene-gene interaction network. we obtain two weighted gene-gene interaction networks under two phenotype datasets pathway-based extension of the sub-network the gene-gene interaction of pathway is different in different tissues or samples. these differences may be caused by changes in the interactions between internal genes of the pathway or between pathway and neighbor genes. to assess the significance of the pathway in different phenotypic data, we expanded the pathway based on the k-walk algorithm by considering all of the above factors in two weighted gene-gene interaction networks separately. the pathway-based extension of the sub-network was constructed as follows: let g= comprise a set v of genes and a set e of edges denote the weighted gene-gene interaction network with e⊆v×v. let n=∣v∣reflect the number of genes. symmetric matrix a represents the weighted n×n adjacency matrix of g, where a ijdenotes the weight of the edge connecting gene i to gene j. let d i represent the weighted degree of each gene node i where di=∑j=1naij. then, a ij is calculated by pearson’s correlation coefficient as: aij=|cor|βxi,xjisexpressiondataofgenevi,vj0otherwise where β= given a gene set s of a pathway belonging to a subset of g, we formally define an edge relevance function er:e→ℝ+ that maps any edge to its relevance. the extended process of a gene set of a pathway simulates random walks on a graph by the markov chain model. the possibility of transiting from gene i to gene j is calculated as: pij=aijdi here, a gene set s is a set of absorbing states of the markov chain. if the random walk starts from gene x, the modified transition will be: xpij=1i∈s∖{x}andi=j0i∈s∖{x}andi≠jpijotherwise then, the transition matrix is described as follow: xp=xqxr0i where x q is a matrix that denotes transient states, x r is a matrix that denotes the transition probability from transient states to absorbing states, and i is the identity matrix. after k steps, the transition matrix becomes k. given that the walk started in state x, the joint probability of visiting the edge e between step k and k+ is calculated as follow: pxk=i,xk+1=j,l|x0=x=fjisatransientstatel−1xiijjisanabsorbingstate where l is a total walk length, f=∑r∈s∖{x}xiijjr, xi is the probability of transiting from x to i in k steps. the probability of a walk of length l starting in x is calculated as follow: p=∑r∈s∖{x}xr the e is defined as the number of times a random walk starts in x using the transition from i to j. given that the walk length is l, the conditional expectations of e is given by: e=∑k=0l−1pp let l max denote a maximal walk length. then: e=∑l=1lmaxe finally, the edge relevance er is given by: er= ∑r∈slx|ee|l≤lmax−ee|l≤lmax|∀∈e where the vector l x represents an initial probability distribution. here, the maximal relevance score that can lead to a connected subgraph is chose as the threshold θ. finally, a subnetwork is obtained by keeping only edges with relevance scores er above a threshold value θ. in the paper, we set l max to by default. fig. an example of a pathway-based extension. blue nodes denote a gene set of a pathway and red nodes denote the expanded genes that are most associated with the corresponding pathway identification of significant pathways for a given pathway i, the pathway was expanded in two weighted gene-gene interaction networks for two phenotypic datasets separately. the union genes of two expanded pathway play a role in performing a similar function in normal or tumor tissues. moreover, genes in expanded pathway from tumor and normal tissues are almost different. the union genes construct sub-networks in two weighted networks. these sub-networks weights’ differences can describe the change of pathways between different phenotypes. accordingly, we calculate the difference between the two pathway-based sub-networks reflects the change of the given pathway for the two phenotypic datasets through the union of the two sub-networks. let union_pathway denote the union of two sub-networks that are the expansion of pathway i in two weighted gene-gene interaction networks. then, we mapped union_pathway into the two weighted gene-gene interaction networks and obtained two edge weight vectors t_w and n_w. pearson’s correlation coefficient was calculated as: corri= ∑k=1n∑k=1n2∑k=1n where n is the dimension of the vector and t_w¯=1n∑k=1nt_wk, n_w¯=1n∑k=1nn_wk. finally, we calculated score, which depicts the difference in pathway i for two phenotypic datasets as follow: score=1−|corri| here, score is a measure depicting the relevance degree between pathway i and the corresponding disease.  data the breast invasive carcinoma dataset was downloaded from the tcga website. the brca dataset consists of samples obtained from comparing breast cancer samples with normal samples using the agilent platform. the second dataset was available via the gene expression omnibus. this dataset compared pathologic complete response samples and residual disease samples. ppi network was obtained from the interologous interaction database website. ppi was mapped into the gene-gene interaction data through the uniprot website. finally, unique gene pairs were selected for brca, and unique gene pairs were selected for gse by data pretreatment. the kegg pathways were downloaded from the consensuspathdb website. we selected pathways related to humans by screening; only genes of pathways belonging to the brca gene set were used in the downstream analysis. the breast cancer gene set was downloaded from website. to identify the significance of the given pathway, first, we dealt with the ppi data. the ppi network was mapped into the gene-gene interaction network in which the weight of each pair of genes was calculated using high-throughput gene expression profiling data. finally, we obtained two weighted gene-gene interaction networks for the two phenotypic datasets. the weighted gene-gene interaction network has vertices and edges for brca. based on the above algorithm, we expanded a gene set of the given pathway based on the k-walks algorithm into two sub-networks in two weighted networks. then, we compared the number of the genes in the original pathway and the expanded pathway. finally, the union of the two sub-networks served as the ultimate expansion of the given pathway. fig. the number of the genes in the original pathway and the expanded pathway. through the diagram, we found that every pathway was validly expanded except pathway hsa because it only contained one gene from the original pathway next, we ran the proposed approach using the brca dataset. to provide a more comprehensive understanding of the proposed method, we discuss the method from the following aspects separately. the pathway score based on the background mentioned above, each pathway score depicts the degree of relevance between the given pathway and the corresponding disease. all scores were calculated using algorithm. the top pathways were tabulated based on their scores. note: yes if the pathway was also ranked in the spia or gsea top 15; no if otherwise top pathways identified by the proposed method should be significantly associated with the breast cancer risk. to test the idea, we compared the intersections of the breast cancer gene set and pathway gene sets before and after expansion. the breast cancer gene set comes from sidd which integrates disease gene knowledge sources. we found that more genes associated with breast cancer were expanded to the original pathway gene set through pathway expansion. this result demonstrates that the proposed method can expand genes associated with the corresponding disease. fig. comparison between the gene number of intersections of the breast gene set and pathway gene sets before and after expansion analysis of the top brca pathways in order to prove that the pathways identified by the proposed method are associated with the breast cancer risk, we need to look for the supports of biological knowledge and other methods. table shows that top pathways identified from brca by the proposed method are significantly associated with the breast cancer risk through reference. here we give the supports of biological knowledge and other methods for the top brca pathways. the number ranked significant pathway identified by our method was vitamin b metabolism. growing evidence suggests that the lack of several trace elements, such as vitamin b and folate, can induce dna damage, eventually leading to tumors, cancers and a variety of degenerative diseases. there is a significant negative correlation between the plasma b level and different types of cancer. vitamin b can reduce the homocysteine and pyridoxal phosphate levels, which have potential biological effects on tumors. vitamin b deficiency leads to lower serine hydroxymethyltransferase activity, lower generation of -methylenetetrahydrofolate and the generation of a dump instead of a dtmp mismatch to dna, which is more likely to lead to a chromosome chain break and /or impair dna excision repair. the reduced generation of -methylenetetrahydrofolate may lead to dna hypomethylation. abnormal methylation of dna has been found in different tumor types. vitamin b deficiency can increase the sensitivity of the steroid hormone,which may lead to breast cancer or colon cancer. these findings demonstrate that the proper intake of vitamin b can reduce the risk of breast cancer; therefore, this pathway is significantly associated with the breast cancer risk. the number ranked significant pathway identified by the proposed method was synthesis and degradation of ketone bodies. ketone bodies are sufficient to drive mitochondrial biogenesis in human breast cancer cells. carcinoma-associated fibroblasts produce “mitochondrial fuels”, including lactic acid, ketones, fatty acids, and glutamine, that provide a "eutrophication" microenvironment for tumor cells and promote tumor cell proliferation when metabolized; these fuels are the major cellular components of the breast cancer stroma. it was reported that caf reduced the apoptosis of human breast cancer mcf cells induced by tamoxifen and fulvestrant by -fold and -fold, respectively. lactic acid and ketones are sufficient to induce tamoxifen resistance in breast cancer mcf cells. metformin and arsenic trioxide can overcome caf-induced drug resistance in mcf cells. these findings indicate that this pathway is also significantly associated with the breast cancer risk. the proposed method ranked the sulphur relay system in 3rd place. sulphur enables the transport of oxygen across cell membranes. oxygen is necessary for healthy cellular regeneration in mammals. therefore, sulphur deficiencies may promote sickness and disease. sulphur is commonly used as an herbal medicine to treat inflammation and cancer and organic sulphur has been studied in several types of cancers and found to have remarkable anti-cancer benefits. methylsulfonylmethane is an organic sulphur-containing natural compound without any toxicity. it was found that msm substantially decreased the viability of human breast cancer cells in a dose-dependent manner and recommended the use of msm as a trial drug for the treatment of all types of breast cancers. leimkühler et al. pointed out that sulphur not only prevented but also helped reverse cancer. hence, the sulphur relay system is significantly associated with the breast cancer risk to some extent. phenylalanine, tyrosine and tryptophan biosynthesis was ranked 4th in the list of proposed methods. eno in phenylalanine tyrosine and tryptophan biosynthesis was significantly overexpressed in her-2/neu positive breast tumors. this finding indicates that this pathway is associated with breast cancer to some extent; however, the clear relationship between this pathway and breast cancer re-quires further verification. the 5th ranked pathway was glycosaminoglycan biosynthesis. abnormal glycosaminoglycan concentrations have been reported for various types of tumors, suggesting that they may play a role in neoplasia. recently, cell biology studies revealed that glycosaminoglycans were among the key macromolecules that affected cell properties and functions by acting directly on cell receptors or via interactions with growth factors. the interactions of gags with growth factors, cytokines and growth factor receptors have been implicated in cancer growth and progression. gags are involved in signalling cascades that regulate the angiogenesis, invasion and metastasis of malignant cells. investigations of the fine structures and specific biological roles of gags has led to novel therapeutic approaches. the above references denote that glycosaminoglycan biosynthesis and breast cancer have a certain degree of correlation. the top 6– pathways are also associated with human breast cancer. based on the table one can argue that the proposed method is very efficient in identifying significant pathways of the corresponding complex disease. classification performance using the original genes and expanded genes of the pathway to estimate the classification performance of the top expanded pathways, we firstly prepared our data set consisted of normal and tumor samples randomly derived from the brca dataset. the original genes and expanded genes of the pathway were selected classification features and svm is employed to classify the selected samples. next, a 10-fold cross validation was used to train and test svm. the above experiment was repeated times and the average accuracy of svm is shown in fig. fig. cross validation accuracy using 10-fold cross validation in results, the lowest accuracy was and the highest accuracy was. the experimental results suggested that the union of the original genes and expanded genes of the pathway had a good classification ability and that the top pathways were significantly different between the two phenotypic data sets. analysis using alternative methods to assess the validity of the proposed approach, we analysed the same data using gsea and spia. the gsea approach searches for gene sets that are enriched at the top or bottom of the ranked list of all genes. this method is a typical representative of the gene set enrichment analysis methods. the spia method scores a gene product as highly impactful if it points to other impactful gene products in the network diagram. this method is a representative of the network-based pathway analysis approaches. therefore, we compared our method with gsea and spia. it was interesting to examine pathways ranked at the top by our method but not by gsea and spia, which reflected the validity of our method. in gsea, the analysis performed permutations with an fdr cutoff of 25%. then, pathways were identified of which were found among the top pathways identified using the proposed method. in spia, a significant threshold of 5% was used on the fdr corrected p-values to infer pathway significance. then, pathways were identified of which one was identified by the proposed method. the spia did not identify any of the top pathways identified using the proposed method. validation of the alternative data set to test the effectiveness of the proposed method, we ran the proposed approach on gse the data were obtained from response and survival following taxane-anthracycline chemotherapy for newly diagnosed invasive breast cancer. anthracyclines and taxanes are the two most active classes of cytotoxic agents for early and advanced stage breast cancer and thus are commonly used as a component of either adjuvant or neoadjuvant therapy and/or in patients with metastatic breast cancer. finally, we also obtained two weighted gene-gene interaction networks for the two phenotypic datasets. the weighted gene-gene interaction network has vertices and edges for gse our intention was to identify significant pathways for breast cancer patients before and after taxane-anthracycline use and to evaluate the pharmacological mechanism of taxane-anthracycline. among the top pathways identified using the proposed method, which were significant pathways for taxane-anthracycline except for collecting duct acid secretion pathway, the gsea and spia did not identify any. the relationship between collecting duct acid secretion pathway and taxane-anthracycline and/or breast cancer requires further verification. the results showed that our approach discovered significant pathways for taxane-anthracycline. the top pathways are shown in table note: yes if the pathway was also ranked in spia or gsea top 15; no if otherwise the significantly impacted pathways identified by the proposed method in the corresponding conditions were mostly consistent with the known biological processes. accordingly, the novel proposed method is of methodological and biological significance for future research.  pathway analysis not only reduces data involving thousands of altered genes and proteins to a smaller and more interpretable set of altered processes but can also combine multiple types of high-throughput data. the analysis results play an important role in elucidating the mechanisms of complex diseases, improving clinical treatment, and discovering drug targets and biomarkers. therefore, pathway-based analysis of complex diseases has become a research hotspot. to date, these methods have entered the third stage: 1) pathway-based gene set enrichment analysis; 2) pathway-based functional class clustering and scoring approaches; and 3) network-based pathway approaches. unlike existing pathway analysis approaches that do not take into account the interaction between internal and external genes of the pathway and between pathways, we propose a novel approach that addresses the above-mentioned limitations by expanding a pathway based on the k-walk algorithm to two small networks in two weighted networks. finally, our approach effectively identified significant pathways that corresponded to a complex disease through a series of verification steps. it is undeniable that the pathways identified by gsea and spia but not by our method are mostly significantly associated with the breast cancer risk. based on the above analysis, our method combined with gsea may produce better results. hence, we will combine our method with gsea in future studies. this study provides a new research direction for the pathway-based analysis of complex diseases. we will employ more datasets to assess the validity of our approach in future research. additional files additional file table s the scores of pathways from brca. additional file table s the results of gsea from brca. additional file table s the results of spia from brca. additional file table s the scores of pathways from gse 
here, we propose a network-based pathway-expanding approach that takes the topological structures of biological networks into account. first, two weighted gene-gene interaction networks are constructed integrating protein-protein interaction information, gene expression data and pathway databases. pathway analysis combining multiple types of high-throughput data, such as genomics and proteomics, has become the first choice to gain insights into the pathogenesis of complex diseases. currently, several pathway analysis methods have been developed to study complex diseases. a novel network-based pathway-expanding approach is proposed to avoid the limitations of existing pathway analysis approaches. pathway analysisnetwork-basedsignificant pathwayprotein-protein interactionthe 27th international conference on genome informatics shanghai, china 3- october http://admis.fudan.edu.cn/giw2016/issue-copyright-statement© the author 2016 then, they are used to identify significant pathways through testing the difference of topological structures of expanded pathways in the two weighted networks. experimental results indicate that the proposed method can accurately and reliably identify significant pathways which are related to the corresponding disease. however, these methods did not take into account the interaction between internal and external genes of the pathway and between pathways. in addition, the proposed method is also compared with other methods, such as gsea and spia, and estimated using the classification performance of the top expanded pathways. as a result, the top pathways identified using the proposed method are supported by biological knowledge from the published literatures and other methods.
 pathway analysis combining multiple types of high-throughput data, such as genomics and proteomics, has become the first choice to gain insights into the pathogenesis of complex diseases. currently, several pathway analysis methods have been developed to study complex diseases. however, these methods did not take into account the interaction between internal and external genes of the pathway and between pathways. hence, these approaches still face some challenges. here, we propose a network-based pathway-expanding approach that takes the topological structures of biological networks into account.  first, two weighted gene-gene interaction networks are constructed integrating protein-protein interaction information, gene expression data and pathway databases. then, they are used to identify significant pathways through testing the difference of topological structures of expanded pathways in the two weighted networks. the proposed method is employed to analyze two breast cancer data. as a result, the top pathways identified using the proposed method are supported by biological knowledge from the published literatures and other methods. in addition, the proposed method is also compared with other methods, such as gsea and spia, and estimated using the classification performance of the top expanded pathways.  a novel network-based pathway-expanding approach is proposed to avoid the limitations of existing pathway analysis approaches. experimental results indicate that the proposed method can accurately and reliably identify significant pathways which are related to the corresponding disease. electronic supplementary material the online version of this article contains supplementary material, which is available to authorized users. keywords pathway analysisnetwork-basedsignificant pathwayprotein-protein interactionthe 27th international conference on genome informatics shanghai, china 3- october http://admis.fudan.edu.cn/giw2016/issue-copyright-statement© the author 2016 