BACKGROUND: Recent advances in next-generation sequencing technologies have helped investigators generate massive amounts of cancer genomic data. A critical challenge in cancer genomics is identification of a few cancer driver genes whose mutations cause tumor growth. However, the majority of existing computational approaches underuse the co-occurrence mutation information of the individuals, which are deemed to be important in tumorigenesis and tumor progression, resulting in high rate of false positive. RESULTS: To make full use of co-mutation information, we present a random walk algorithm referred to as DriverRWH on a weighted gene mutation hypergraph model, using somatic mutation data and molecular interaction network data to prioritize candidate driver genes. Applied to tumor samples of different cancer types from The Cancer Genome Atlas, DriverRWH shows significantly better performance than state-of-art prioritization methods in terms of the area under the curve scores and the cumulative number of known driver genes recovered in top-ranked candidate genes. Besides, DriverRWH discovers several potential drivers, which are enriched in cancer-related pathways. DriverRWH recovers approximately 50% known driver genes in the top 30 ranked candidate genes for more than half of the cancer types. In addition, DriverRWH is also highly robust to perturbations in the mutation data and gene functional network data. CONCLUSION: DriverRWH is effective among various cancer types in prioritizes cancer driver genes and provides considerable improvement over other tools with a better balance of precision and sensitivity. It can be a useful tool for detecting potential driver genes and facilitate targeted cancer therapies.

Abstract An f‐coloring of a multigraph G is a coloring of the edges of E such that each color appears at each vertex v ∈ V at most f(v) times. The minimum number of colors needed to f‐color G is called the f‐chromatic index of G and is denoted by χ′f(G). Various scheduling problems on networks are reduced to finding an f‐coloring of a multigraph. Any simple graph G has f‐chromatic index equal to Δf(G) or Δf(G)+ 1, where Δf(G) = max v∈V{⌈ ${d(v)\over f(v)}$ ⌉} and d(v) is the degree of vertex v. A connected graph G is called f‐critical if χ′f(G)=Δf(G)+1 and χ′f(G)=Δf(G−e) < χ′f(G) for any edge e ∈ E. Some results about f‐critical graphs are given. © 2007 Wiley Periodicals, Inc. NETWORKS, Vol. 50(3), 197–202 2007