Gene Reachability Using PageRanking


Background
  • Google PageRank algorithm analyzes links and assigns a numerical weighting to each element of a hyperlinked set of elements relative to its importance.
  • This importance represents the likelihood that a surfer, surfing the hyperlinked elements, will arrive at any stochastic element, based on the element similarity, having started from another element.
  • This algorithm was used in the past to select genes [1].






 
Fig.1: Illustration of the gene selection using PageRank algorithm [1]. Here the relative ranking of the gene with low expression
could be boosted by PageRanking. We can thus select the gene with low expression as significant.
 



Our Research
  • In [2], we defined gene reachability in complex gene networks inspired by PageRanking.
  • Namely, gene reachability signifies how likely a gene is reachable in the network.
  • It discovers genes (e.g., transcription factor genes) that are not expressed significantly in the microarray measurements, yet are significant. Particularly, we
    • Computed the average connections per gene in a gene network, inspired by the Google PageRank algorithm.
    • Modified the Google PageRank algorithm, based on this average.
    • Computed this average as eight for human and three to seven for yeast. These numbers agree well with other published results.
    • Analyzed the gene reachability in gene networks, and cluster genes.
Impact: Our results are useful in clinical applications, including gene selection.




 


Fig. 1: Variance of the gene rank scores Pr(i) of a ventricular-associated pneumonia (VAP) data from human
subjects [3], as a function of the number of connections α per gene in the associated gene network. Here
Pr(i) denotes the probability of reaching the ith gene, with i from 1 to 85. We observe a peak at α=8. Using
this observation, we conclude that the average connections per gene for human is 8. 




References

[1] J. L. Morrison, R. Breitling, D. J. Higham, and D. R. Gilbert, ``GeneRank: Using search engine technology for the analysis of microarray experiments,'' BMC Bioinformatics, vol. 6:233, 2005.
[2] P. Sarder, W. Zhang, J. P. Cobb, and A. Nehorai, "Gene reachability using page ranking on gene co-expression networks," in Link Mining: Models, Algorithms, and Applications, (Ch. 21, pp. 557-568, P. S. Yu, C. Faloutsos, and J. Han, Eds.), Springer, 2010.*
[3] J. E. McDunn et. al, ``Plasticity of the systematic inflammatory response to acute infection during critical illness,'' PLoS One, vol. 3, pp. e1564, 2008.

*The above pdf files may not be exactly the same as those in the published book chapters, but should be similar.