A generic algorithm for layout of biological networks

Abstract

Background: Biological networks are widely used to represent processes in biological systems and to capture interactions and dependencies between biological entities. Their size and complexity is steadily increasing due to the ongoing growth of knowledge in the life sciences. To aid understanding of biological networks several algorithms for laying out and graphically representing networks and network analysis results have been developed. However, current algorithms are specialized to particular layout styles and therefore different algorithms are required for each kind of network and/or style of layout. This increases implementation effort and means that new algorithms must be developed for new layout styles. Furthermore, additional effort is necessary to compose different layout conventions in the same diagram. Also the user cannot usually customize the placement of nodes to tailor the layout to their particular need or task and there is little support for interactive network exploration.

Results: We present a novel algorithm to visualize different biological networks and network analysis results in meaningful ways depending on network types and analysis outcome. Our method is based on constrained graph layout and we demonstrate how it can handle the drawing conventions used in biological networks.

Conclusion: The presented algorithm offers the ability to produce many of the fundamental popular drawing styles while allowing the exibility of constraints to further tailor these layouts.

Figure 1

Layout steps: Our layout method involves taking an (a) initial layout, (b) Finding a feasible layout that satisfies all the placement constraints, and performing gradient projection to produce (c) a final optimized layout. This gene regulatory network has two bi-fan motifs drawn similarly and one path emphasized via constraints.

Figure 2

Procedure find-feasible-position (C - set of constraints, G - graph); see text for details.

Figure 3

Procedure improve ((x, y) - initial position for the nodes, F - cost function, C - set of constraints); see text for details.

Figure 4

A metabolic pathway arranged with standard drawing conventions emphasized using various constraints. Metabolic pathways show chemical reactions occurring within a cell.

Figure 5

The presented method provides a generic approach to network visualization. It produces the drawings above which previously had to be produced using two totally different algorithms: (a) is a drawing of a gene regulatory network (showing the indirect interaction of genes through their RNA and protein expression products) using a Sugiyama layered layout style (note the two bi-fan motifs highlighted and drawn similarly), (b) is a protein interaction network (showing the interaction of proteins in a cell) using a force-directed layout style (Figure 7 shows the affect of adding constraints to this layout).

Figure 6

Handling of convex and rectangular clusters allows network hierarchy to be emphasized. (a) shows an example a metabolic pathway (showing chemical reactions occurring within a cell, in this example a part of the Glycolysis and Gluconeogenesis pathway is used) with compartments manually drawn (manual layout derived from the MetaCrop database [30]), (b) shows the same network drawn automatically.

Figure 7

Emphasizing relationships of interest: a protein interaction network with 3 radial band constraints (rings around the center) to place the most important proteins (red) at the center; see Figure 5(b) for the unconstrained version of the layout. The importance of proteins can be given by different methods such as computationally by centrality analysis or experimentally by knock-out mutants.

Figure 8

Typical constraints used to produce the layouts in Figures 5-7.