Biology:PageRank algorithm in biochemistry

From HandWiki
Short description: none

The PageRank algorithm has several applications in biochemistry. ("PageRank" is an algorithm used in Google Search for ranking websites in their results, but it has been adopted for other purposes also. According to Google, PageRank works by "counting the number and quality of links to a page to determine a rough estimate of how important the website is," the underlying assumption being that more important websites are likely to receive more links from other websites.[1])

Application in analyzing protein networks

The relative importance-measuring property of the PageRank link analysis algorithm could be used to identify new possible drug targets in proteins.[2] A PageRank-based algorithm could identify important protein targets in the pathogen organism better than a method considering only the number of incoming edges (in-degree) of a node in the metabolic network. The reason for this is that some already known, important protein targets do not have a high degree (are not hubs) and also, perturbing some hubs could result in unwanted physiological effects.[3]

Description

The clinical use of most antibiotics result in a mutation of the pathogen organism leading to their resistance against the drug. Therefore, development of new drugs is always needed. A potential first step in developing new drugs against currently threatening diseases (e.g. tuberculosis) is to find new drug targets in the causative agent of the disease, i.e. the pathogen microorganism, let it be either a bacterium, or a protozoan parasite. After finding the target protein in the bacterium (or protozoan parasite), one could design small molecular drug compounds that bind to the protein and inhibit it.

Public availability of biological network data[4][5][6][7] makes the process of searching for new drug targets easier than it was before. By using the available metabolic networks, it is possible to find important nodes with link analysis algorithms, like PageRank. In a recently published paper,[8] biochemical reactions are treated as nodes of the metabolic network. In this directed network, reaction A has a directed edge towards reaction B if the product of the former enters the latter reaction as a substrate or co-factor.

To select important nodes that could serve as drug targets, we might think of selecting high in-degree nodes (hubs; nodes with many incoming edges). It was shown however[2], that targeting hub proteins with many vital functions may unintentionally harm the living cell as well. A PageRank-based scoring method could detect important nodes that are not hubs and therefore might be better drug targets.

The PageRank of a node A is the stationary limit probability distribution that the random walker is at node A.[2] In its original application, the personalization vector w captured the personal interest of a web-surfer: interesting websites to a surfer appeared with a higher probability in the distribution given in vector w.[8] In this metabolic network, w is personalized to proteins; w is larger for those proteins that appear in higher concentrations in the proteomics analysis of certain diseases. This personalized PageRank may identify other related proteins to the disease.[2][8]

However, by using only the personalized PageRank to identify important nodes, hubs still get a high score on average.[9] To find non-hub important nodes instead, we should consider scoring the nodes by their "relativized personalized PageRank"; i.e. their personalized PageRank scores over the number of edges pointing towards them (over their in-degree): The relativized personalized PageRank (rPPR(v)) for a node v is given by:

[math]\displaystyle{ rPPR(v)=\frac{PPageRank(v)}{d_v} }[/math]

where PpageRank(v) is the personalized PageRank score of node v, and d_(v) is its in-degree. It was shown, that by using this method, numerous already validated drug targets can be found (e.g. in the Mycobacterium tuberculosis), therefore, new, currently unknown targets might be detected as well.[8]

References

  1. "Facts about Google and Competition". Archived from the original on 4 November 2011. https://web.archive.org/web/20111104131332/https://www.google.com/competition/howgooglesearchworks.html. Retrieved 12 July 2014. 
  2. 2.0 2.1 2.2 Iván G, Grolmusz V (2011). "When the Web meets the cell: using personalized PageRank for analyzing protein interaction networks". Bioinformatics 27 (3): 405–7. [1]
  3. Russell RB, Aloy P (2008). "Targeting and tinkering with interaction networks". Nat Chem Biol 4: 666–673.[2]
  4. Prasad TSK, Kandasamy K, Pandey A (2009). "Human protein reference database and human proteinpedia as discovery tools for systems biology". Methods Mol Biol 577: 67–79.[3]
  5. Zanzoni A, Montecchi-Palazzi L, Quondam M, Ausiello G, Helmer-Citterich M, et al. (2002). "Mint: a molecular interaction database". FEBS Lett 513: 135–140.[4]
  6. Xenarios I, Salwinski L, Duan XJ, Higney P, Kim SM, et al. (2002). "Dip, the database of interacting proteins: a research tool for studying cellular networks of protein interactions". Nucleic Acids Res 30: 303–305.[5]
  7. Farkas IJ, Korcsmaros T, Kovacs IA, Mihalik A, Palotai R, et al. (2011). "Network-based tools for the identification of novel drug targets". Sci Signal 4: pt3.[6]
  8. 8.0 8.1 8.2 8.3 Bánky D, Iván G, Grolmusz V (2013). "Equal Opportunity for Low-Degree Network Nodes: A PageRank-Based Method for Protein Target Identification in Metabolic Graphs". PLoS ONE 8(1): e54204.[7]
  9. Fortunato S, Boguna M, Flammini A, Menczer F (2008). "Approximating pagerank from in-degree". Lecture Notes in Computer Science 4936: 59–71.[8]