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.


Walks, simple paths trails and cycles in graphs. A walk is a sequence of nodes e.g. (V2, V3, V6, V5, V3). A simple path is a walk with no repeated nodes, e.g. (V1, V4, V5, V2, V3). A trail is a walk where no edges are repeated e.g. (V1, V2, V3 V6). A cycle is a walk (V1, V2,..., VL) where V1 = VL with no other nodes repeated and L>3, e.g. (V1, V2, V5, V4, V1).
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 4: Walks, simple paths trails and cycles in graphs. A walk is a sequence of nodes e.g. (V2, V3, V6, V5, V3). A simple path is a walk with no repeated nodes, e.g. (V1, V4, V5, V2, V3). A trail is a walk where no edges are repeated e.g. (V1, V2, V3 V6). A cycle is a walk (V1, V2,..., VL) where V1 = VL with no other nodes repeated and L>3, e.g. (V1, V2, V5, V4, V1).

Mentions: A walk is a pass through a specific sequence of nodes (v1, v2,..., vL) such that {(v1, v2), (v2, v3),..., (vL-1, vL)} ⊆ E. A simple path is a walk with no repeated nodes. A cycle is a walk (v1, v2,..., vL) where v1 = vL with no other nodes repeated and L >3, such that the last node is the same with the first one. A trail is a path where no edge can be repeated. A graph is called cyclic if it contains a cycle. In any other case it is called acyclic. All of the aforementioned can be found as an example in Figure 4. A complete graph is a graph in which every pair of nodes is adjacent. If (i, j) is an edge in a graph G between nodes i and j, we say that the vertex i is adjacent to the vertex j. An undirected graph is connected if one can get from any node to any other node by following a sequence of edges. A directed graph is strongly connected if there is a directed path from any node to any other node. This does not require an all-against combination. The distance δ(i, j) from i to j is the length of the shortest path from i to j in G. If no such path exists, then we set δ(i, j) = ∞ assuming that the nodes are so far between each other so they are not connected. Practically, for the distance δ(i, j) = ∞ we can use the maximum weight of the graph by adding one. Thus δ(i, j) = ∞ = (maxd(i, j)+1). To define the shortest path problem we can briefly say that it is the methodology of finding a path between two nodes such that the sum of the weights of its constituent edges is minimized. The average path length and the diameter of a graph G are defined to be the average and maximum value of δ(i, j) taken over all pairs of distinct nodes, i, j ∈V(G) which are connected by at least one path. More specifically, the average path length of a network is the average number of edges or connections between nodes, which must be crossed in the shortest path between any two nodes. It is calculated as where δmin(i, j) is the minimum distance between nodes i and j. The diameter of a network is the longest shortest path within a network. The diameter is defined as . The most common algorithms for calculating the shortest paths are Dijkstra's greedy algorithm [65] and Floyd's dynamic algorithm [66]. Dijkstra's algorithm has running time complexity O(N2) where N is the number of vertices and returns the shortest path between a source vertex i and all other vertices in the network. Floyd's algorithm has running time complexity O(N3) and requires an all-against-all matrix that contains the distances of every node in the network to every other node in the network.


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)

Walks, simple paths trails and cycles in graphs. A walk is a sequence of nodes e.g. (V2, V3, V6, V5, V3). A simple path is a walk with no repeated nodes, e.g. (V1, V4, V5, V2, V3). A trail is a walk where no edges are repeated e.g. (V1, V2, V3 V6). A cycle is a walk (V1, V2,..., VL) where V1 = VL with no other nodes repeated and L>3, e.g. (V1, V2, V5, V4, V1).
© Copyright Policy - open-access
Related In: Results  -  Collection

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

Figure 4: Walks, simple paths trails and cycles in graphs. A walk is a sequence of nodes e.g. (V2, V3, V6, V5, V3). A simple path is a walk with no repeated nodes, e.g. (V1, V4, V5, V2, V3). A trail is a walk where no edges are repeated e.g. (V1, V2, V3 V6). A cycle is a walk (V1, V2,..., VL) where V1 = VL with no other nodes repeated and L>3, e.g. (V1, V2, V5, V4, V1).
Mentions: A walk is a pass through a specific sequence of nodes (v1, v2,..., vL) such that {(v1, v2), (v2, v3),..., (vL-1, vL)} ⊆ E. A simple path is a walk with no repeated nodes. A cycle is a walk (v1, v2,..., vL) where v1 = vL with no other nodes repeated and L >3, such that the last node is the same with the first one. A trail is a path where no edge can be repeated. A graph is called cyclic if it contains a cycle. In any other case it is called acyclic. All of the aforementioned can be found as an example in Figure 4. A complete graph is a graph in which every pair of nodes is adjacent. If (i, j) is an edge in a graph G between nodes i and j, we say that the vertex i is adjacent to the vertex j. An undirected graph is connected if one can get from any node to any other node by following a sequence of edges. A directed graph is strongly connected if there is a directed path from any node to any other node. This does not require an all-against combination. The distance δ(i, j) from i to j is the length of the shortest path from i to j in G. If no such path exists, then we set δ(i, j) = ∞ assuming that the nodes are so far between each other so they are not connected. Practically, for the distance δ(i, j) = ∞ we can use the maximum weight of the graph by adding one. Thus δ(i, j) = ∞ = (maxd(i, j)+1). To define the shortest path problem we can briefly say that it is the methodology of finding a path between two nodes such that the sum of the weights of its constituent edges is minimized. The average path length and the diameter of a graph G are defined to be the average and maximum value of δ(i, j) taken over all pairs of distinct nodes, i, j ∈V(G) which are connected by at least one path. More specifically, the average path length of a network is the average number of edges or connections between nodes, which must be crossed in the shortest path between any two nodes. It is calculated as where δmin(i, j) is the minimum distance between nodes i and j. The diameter of a network is the longest shortest path within a network. The diameter is defined as . The most common algorithms for calculating the shortest paths are Dijkstra's greedy algorithm [65] and Floyd's dynamic algorithm [66]. Dijkstra's algorithm has running time complexity O(N2) where N is the number of vertices and returns the shortest path between a source vertex i and all other vertices in the network. Floyd's algorithm has running time complexity O(N3) and requires an all-against-all matrix that contains the distances of every node in the network to every other node in the network.

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.