Limits...
Using graph theory to analyze biological networks.

Pavlopoulos GA, Secrier M, Moschopoulos CN, Soldatos TG, Kossida S, Aerts J, Schneider R, Bagos PG - BioData Min (2011)

Bottom Line: The myriad components of a system and their interactions are best characterized as networks and they are mainly represented as graphs where thousands of nodes are connected with thousands of vertices.In this article we demonstrate approaches, models and methods from the graph theory universe and we discuss ways in which they can be used to reveal hidden properties and features of a network.This network profiling combined with knowledge extraction will help us to better understand the biological significance of the system.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Computer Science and Biomedical Informatics, University of Central Greece, Lamia, 35100, Greece. pavlopou@embl.de.

ABSTRACT
Understanding complex systems often requires a bottom-up analysis towards a systems biology approach. The need to investigate a system, not only as individual components but as a whole, emerges. This can be done by examining the elementary constituents individually and then how these are connected. The myriad components of a system and their interactions are best characterized as networks and they are mainly represented as graphs where thousands of nodes are connected with thousands of vertices. In this article we demonstrate approaches, models and methods from the graph theory universe and we discuss ways in which they can be used to reveal hidden properties and features of a network. This network profiling combined with knowledge extraction will help us to better understand the biological significance of the system.

No MeSH data available.


Closeness and Betweeness centralities. Closeness centrality. V1: d1 = 4 × 1 + 1 × 2 + 1 × 3 = 9, Cclo(1) = 6/9. V1 accesses 4 nodes (V2, V5, V6, V7) with step 1, 1 node (V3) with step 2 and 1 node (V4) with step 3. 6 nodes can be accessed in total by V1. V2: d2 = 2 × 1 + 4 × 2 = 10 > d1, Cclo(2) = 6/10. V2 accesses 2 nodes (V1, V3) with step 1 and 4 nodes (V4, V5, V6, V7) with step 2. 6 nodes can also be accessed in total by V2. As a result, V1 is more central than node V2 since d1>d2. Betweenness centrality. Np(1) = 12 shortest paths that pass through node V1. The paths from the starting to the ending node are {V2-V5, V2-V6, V2-V7, V3-V5, V3-V6, V3-V7, V4-V5, V4-V6, V4-V7, V5-V6, V5-V7, V6-V7}. Np(2) = 8 shortest paths that pass through node V2. The paths are {V1-V3, V1-V4, V3-V5, V3-V6, V3-V7, V4-V5, V4-V6, V4-V7}. Np(3) = 5 {V1-V4, V2-V4, V4-V5, V4-V6, V4-V7}. Np(4) = Np(5) = Np(6) = Np(7) = 0. Np = 25 the total sum of shortest paths that pass through the nodes, thus Np= Np(1)+Np(2)+Np(3)+Np(4)+Np(5)+Np(6)+Np(7). The centralities are Cb (1) = 12/25 = 0.48, Cb (2) = 8/25 = 0.32, Cb (3) = 5/25 = 0.20, Cb (4) = Cb (5) = Cb (6) = Cb (7) = 0, thus node V1 is more central.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
getmorefigures.php?uid=PMC3101653&req=5

Figure 7: Closeness and Betweeness centralities. Closeness centrality. V1: d1 = 4 × 1 + 1 × 2 + 1 × 3 = 9, Cclo(1) = 6/9. V1 accesses 4 nodes (V2, V5, V6, V7) with step 1, 1 node (V3) with step 2 and 1 node (V4) with step 3. 6 nodes can be accessed in total by V1. V2: d2 = 2 × 1 + 4 × 2 = 10 > d1, Cclo(2) = 6/10. V2 accesses 2 nodes (V1, V3) with step 1 and 4 nodes (V4, V5, V6, V7) with step 2. 6 nodes can also be accessed in total by V2. As a result, V1 is more central than node V2 since d1>d2. Betweenness centrality. Np(1) = 12 shortest paths that pass through node V1. The paths from the starting to the ending node are {V2-V5, V2-V6, V2-V7, V3-V5, V3-V6, V3-V7, V4-V5, V4-V6, V4-V7, V5-V6, V5-V7, V6-V7}. Np(2) = 8 shortest paths that pass through node V2. The paths are {V1-V3, V1-V4, V3-V5, V3-V6, V3-V7, V4-V5, V4-V6, V4-V7}. Np(3) = 5 {V1-V4, V2-V4, V4-V5, V4-V6, V4-V7}. Np(4) = Np(5) = Np(6) = Np(7) = 0. Np = 25 the total sum of shortest paths that pass through the nodes, thus Np= Np(1)+Np(2)+Np(3)+Np(4)+Np(5)+Np(6)+Np(7). The centralities are Cb (1) = 12/25 = 0.48, Cb (2) = 8/25 = 0.32, Cb (3) = 5/25 = 0.20, Cb (4) = Cb (5) = Cb (6) = Cb (7) = 0, thus node V1 is more central.

Mentions: Closeness Centrality indicates important nodes that can communicate quickly with other nodes of the network. Let G = (V, E) be an undirected graph. Then, the centrality is defined as where dist(i, j) denotes the distance or else the shortest path p between the nodes i and j. An example is shown in Figure 7. Closeness centrality has been used to identify the top central metabolites in genome-based large-scale metabolic networks [79], to compare unicellular and multicellular eukarya, to rank pathways and obtain a perspective on the evolution of metabolic organization [80]. A decrease in closeness centrality of components has been observed as a consequence of increased distance between pathways throughout evolution [80]. It has been chosen as the best centrality measure that can be used extract the metabolic core of a network [81].


Using graph theory to analyze biological networks.

Pavlopoulos GA, Secrier M, Moschopoulos CN, Soldatos TG, Kossida S, Aerts J, Schneider R, Bagos PG - BioData Min (2011)

Closeness and Betweeness centralities. Closeness centrality. V1: d1 = 4 × 1 + 1 × 2 + 1 × 3 = 9, Cclo(1) = 6/9. V1 accesses 4 nodes (V2, V5, V6, V7) with step 1, 1 node (V3) with step 2 and 1 node (V4) with step 3. 6 nodes can be accessed in total by V1. V2: d2 = 2 × 1 + 4 × 2 = 10 > d1, Cclo(2) = 6/10. V2 accesses 2 nodes (V1, V3) with step 1 and 4 nodes (V4, V5, V6, V7) with step 2. 6 nodes can also be accessed in total by V2. As a result, V1 is more central than node V2 since d1>d2. Betweenness centrality. Np(1) = 12 shortest paths that pass through node V1. The paths from the starting to the ending node are {V2-V5, V2-V6, V2-V7, V3-V5, V3-V6, V3-V7, V4-V5, V4-V6, V4-V7, V5-V6, V5-V7, V6-V7}. Np(2) = 8 shortest paths that pass through node V2. The paths are {V1-V3, V1-V4, V3-V5, V3-V6, V3-V7, V4-V5, V4-V6, V4-V7}. Np(3) = 5 {V1-V4, V2-V4, V4-V5, V4-V6, V4-V7}. Np(4) = Np(5) = Np(6) = Np(7) = 0. Np = 25 the total sum of shortest paths that pass through the nodes, thus Np= Np(1)+Np(2)+Np(3)+Np(4)+Np(5)+Np(6)+Np(7). The centralities are Cb (1) = 12/25 = 0.48, Cb (2) = 8/25 = 0.32, Cb (3) = 5/25 = 0.20, Cb (4) = Cb (5) = Cb (6) = Cb (7) = 0, thus node V1 is more central.
© Copyright Policy - open-access
Related In: Results  -  Collection

License
Show All Figures
getmorefigures.php?uid=PMC3101653&req=5

Figure 7: Closeness and Betweeness centralities. Closeness centrality. V1: d1 = 4 × 1 + 1 × 2 + 1 × 3 = 9, Cclo(1) = 6/9. V1 accesses 4 nodes (V2, V5, V6, V7) with step 1, 1 node (V3) with step 2 and 1 node (V4) with step 3. 6 nodes can be accessed in total by V1. V2: d2 = 2 × 1 + 4 × 2 = 10 > d1, Cclo(2) = 6/10. V2 accesses 2 nodes (V1, V3) with step 1 and 4 nodes (V4, V5, V6, V7) with step 2. 6 nodes can also be accessed in total by V2. As a result, V1 is more central than node V2 since d1>d2. Betweenness centrality. Np(1) = 12 shortest paths that pass through node V1. The paths from the starting to the ending node are {V2-V5, V2-V6, V2-V7, V3-V5, V3-V6, V3-V7, V4-V5, V4-V6, V4-V7, V5-V6, V5-V7, V6-V7}. Np(2) = 8 shortest paths that pass through node V2. The paths are {V1-V3, V1-V4, V3-V5, V3-V6, V3-V7, V4-V5, V4-V6, V4-V7}. Np(3) = 5 {V1-V4, V2-V4, V4-V5, V4-V6, V4-V7}. Np(4) = Np(5) = Np(6) = Np(7) = 0. Np = 25 the total sum of shortest paths that pass through the nodes, thus Np= Np(1)+Np(2)+Np(3)+Np(4)+Np(5)+Np(6)+Np(7). The centralities are Cb (1) = 12/25 = 0.48, Cb (2) = 8/25 = 0.32, Cb (3) = 5/25 = 0.20, Cb (4) = Cb (5) = Cb (6) = Cb (7) = 0, thus node V1 is more central.
Mentions: Closeness Centrality indicates important nodes that can communicate quickly with other nodes of the network. Let G = (V, E) be an undirected graph. Then, the centrality is defined as where dist(i, j) denotes the distance or else the shortest path p between the nodes i and j. An example is shown in Figure 7. Closeness centrality has been used to identify the top central metabolites in genome-based large-scale metabolic networks [79], to compare unicellular and multicellular eukarya, to rank pathways and obtain a perspective on the evolution of metabolic organization [80]. A decrease in closeness centrality of components has been observed as a consequence of increased distance between pathways throughout evolution [80]. It has been chosen as the best centrality measure that can be used extract the metabolic core of a network [81].

Bottom Line: The myriad components of a system and their interactions are best characterized as networks and they are mainly represented as graphs where thousands of nodes are connected with thousands of vertices.In this article we demonstrate approaches, models and methods from the graph theory universe and we discuss ways in which they can be used to reveal hidden properties and features of a network.This network profiling combined with knowledge extraction will help us to better understand the biological significance of the system.

View Article: PubMed Central - HTML - PubMed

Affiliation: Department of Computer Science and Biomedical Informatics, University of Central Greece, Lamia, 35100, Greece. pavlopou@embl.de.

ABSTRACT
Understanding complex systems often requires a bottom-up analysis towards a systems biology approach. The need to investigate a system, not only as individual components but as a whole, emerges. This can be done by examining the elementary constituents individually and then how these are connected. The myriad components of a system and their interactions are best characterized as networks and they are mainly represented as graphs where thousands of nodes are connected with thousands of vertices. In this article we demonstrate approaches, models and methods from the graph theory universe and we discuss ways in which they can be used to reveal hidden properties and features of a network. This network profiling combined with knowledge extraction will help us to better understand the biological significance of the system.

No MeSH data available.