Centrality and the shortest path approach in the human interactome.

Many notions and concepts for network analysis, including the shortest path approach, came to systems biology from the theory of graphs - the field of mathematics that studies graphs. We studied the relationship between the shortest paths and a biologically meaningful molecular path between vertices in human molecular interaction networks. We analyzed the sets of the shortest paths in the human interactome derived from HPRD and HIPPIE databases between all possible combinations of start and end proteins in eight signaling pathways in the KEGG database - NF-kappa B, MAPK, Jak-STAT, mTOR, ErbB, Wnt, TGF-beta, and the signaling part of the apoptotic process. We investigated whether the shortest paths match the canonical paths. We studied whether centrality of vertices and paths in the subnetworks induced by the shortest paths can highlight vertices and paths that are part of meaningful molecular paths. We found that the shortest paths match canonical counterparts only for canonical paths of length 2 or 3 interactions. The shortest paths match longer canonical counterparts with shortcuts or substitutions by protein complex members. We found that high centrality vertices are part of the canonical paths for up to 80% of the canonical paths depending on the database and the length.