Networks play a central role in biological investigation of organisms. They are used to represent processes in biological systems and to capture interactions and dependencies between biological entities such as genes, transcripts, proteins and metabolites. One large application area for network-centered analysis and visualization is Systems Biology, an increasingly important research field which aims at a comprehensive understanding and remodeling of the processes in living beings [1
]. Due to the steady growth of knowledge in the life sciences such networks are increasingly large and complex. To tackle this complexity and help in analyzing and interpreting the complicated web of interactions meaningful visualizations of biological networks are crucial.
Methods for automatic network visualization have gained increased attention from the research community over recent years and various layout algorithms have been developed, e. g. [3
]. Often standard layout methods such as force directed [12
], layered [14
] and circular [16
] approaches are used to draw these networks. However, the direct use of standard layout methods is somewhat unsatisfactory since biological networks often have specialized layout requirements reflecting the drawing conventions historically used in manually laid out diagrams (which have been developed to better emphasize relevant biological relationships and concepts). This has led to the development of network- and application-specific layout algorithms, for example, for signal transduction maps [17
], protein interaction networks [3
], metabolic pathways [4
] and protein-domain interaction networks [20
]. Advanced solutions combine different layout styles (such as linear, circular and branching layouts) for sub-networks or use specific layouts styles for particular network parts such as cycles [7
However, current approaches for the automatic visualization of biological networks have four major drawbacks resulting from the specialized nature of these algorithms:
1. Different kinds of biological networks (e. g. protein interaction or metabolic networks) have different layout conventions and this requires the implementation and sometimes development of specialized layout algorithms for each convention.
2. It is not easy to combine networks with different layout conventions in the one drawing since the layout algorithms use quite different approaches and so cannot be easily combined.
3. The user cannot tailor the standard layout algorithms for their particular need or task by e. g. emphasizing the pathways of interest by making them straight.
4. The algorithms do not sufficiently support interactive network exploration. Usually with these algorithms small modifications in the network structure and re-layout of the network results in very different pictures. However, such sudden and large changes destroy the user's mental map (i. e. the user's understanding of the network based on the previous view) and therefore hinder interactive understanding of the network.
Here we present a new algorithm for layout of biological networks that overcomes these limitations. It is based on a powerful new graph drawing technique, constrained graph layout
]. Like force-directed layout [12
] constrained graph layout works by minimizing an objective function that measures the quality of the layout. However it extends force-directed layout by allowing minimization of the objective to be done subject to placement constraints on the objects in the network. This is achieved by using mathematically rigorous optimization techniques based on gradient projection [23
]. Efficient implementation is made possible by restricting the placement constraints to be separation constraints
of the form u
≤ (=) v
, enforcing a minimum (or precise) gap g
between the positions u
of pairs of objects in either the x
dimensions of the drawing.
A significant contribution of this paper is to show that separation constraints, despite their apparent simplicity and their limitation to act on a single dimension can in fact be used to encode the wide variety of specialized layout requirements arising in biological networks. Examples of such requirements are placement of nodes below other nodes in directed graphs, drawing cycles on a rectangle, alignment of nodes, non-overlap of nodes, orthogonal ordering between nodes, containment of nodes in clusters, standard layout of motifs and containment in a page. A key technique is to generate separation constraints that approximate complex non-linear constraints such as non-overlap and to update this approximation dynamically as the final layout is computed. Furthermore, these separation constraints can be automatically derived from the visualization requirements, network analysis results and interactive network changes. With this algorithm it is possible to obtain layout results which are close to the results of different existing layout algorithms.
The presented approach provides a generic, universal algorithm for layout of biological networks:
1. It greatly simplifies the implementation of layout methods for life sciences, systems and synthetic biology tools, which have previously had to utilize very different layout algorithms for different types of biological networks (or different layout requirements).
2. It allows the use of different layout styles for different parts of one large network.
3. It allows the user to customize the layout by adding separation constraints.
4. It lends itself to mental-map-preserving dynamic layout in interactive systems, thereby supporting interactive exploration of large and complex networks.
This paper is structured as follows: in the Methods section we introduce some terminology, detail the constrained graph layout method, present the kinds of placement constraints that are needed to fulfill layout requirements of different biological networks and discuss how they can be automatically generated and then implemented in terms of the separation constraints supported by the layout method. The Results section provides examples of the layout method for a number of different kinds of networks and shows its advantages over current layout methods. Finally, the Conclusion contains the discussion and some suggestions for future work.