Metabopolis: scalable network layout for biological pathway diagrams in urban map style

Abstract

Background: Biological pathways represent chains of molecular interactions in biological systems that jointly form complex dynamic networks. The network structure changes from the significance of biological experiments and layout algorithms often sacrifice low-level details to maintain high-level information, which complicates the entire image to large biochemical systems such as human metabolic pathways.

Results: Our work is inspired by concepts from urban planning since we create a visual hierarchy of biological pathways, which is analogous to city blocks and grid-like road networks in an urban area. We automatize the manual drawing process of biologists by first partitioning the map domain into multiple sub-blocks, and then building the corresponding pathways by routing edges schematically, to maintain the global and local context simultaneously. Our system incorporates constrained floor-planning and network-flow algorithms to optimize the layout of sub-blocks and to distribute the edge density along the map domain. We have developed the approach in close collaboration with domain experts and present their feedback on the pathway diagrams based on selected use cases.

Conclusions: We present a new approach for computing biological pathway maps that untangles visual clutter by decomposing large networks into semantic sub-networks and bundling long edges to create space for presenting relationships systematically.

Keywords: Biological pathways; Edge routing; Floor planning; Graph drawing; Map metaphor; Orthogonal layout.

Fig. 1

Examples of urban maps, where a depicts a map of Chicago in 1857, and b shows an abstraction of an urban map

Fig. 2

An example of major pathways in human metabolism, including eleven categories highlighted in differently colored blocks. The red route indicates a path for cytoplasmatic oxidation of glucose in cytoplasm in order to obtain ATP (energy), and the blue route shows how humans transform ammonia to urea to eliminate the toxic ammonia in the Urea Cycle. Our visualization shows that the first procedure only occurs in Glycolysis Gluconeogenesis (orange block) locally, while the chemical components globally move across multiple categories (e.g., mitochondria to cytoplasm through the transport pathways) in the second process. The green route further highlights how the energy generated from the glucose oxidation comes to support catalyzing the urea synthesis. Users can simultaneously read the local and global information using the diagram generated by our system

Fig. 3

Our visualization framework to support pathway analysis, including (1) constructing a user-specified connectivity graph, (2) overlap-free rectangle placement, (3) maximizing screen space, (4) constructing orthogonal layout of each subgraph and (5) highlight relationships among different categories

Fig. 4

Our design for long edges, including a a long directed path decomposition and b the corresponding color coding of discriminating types of communication

Fig. 5

Examples of building our graph skeleton, including a a K4 graph, b a chordless graph, c a degree 4 star graph, and d an appropriate order for initial crossing-free layout

Fig. 6

Illustrations of our mathematical constraints, including a block representation using Chebyshev distance, b alignment of blocks along boundaries, c configuration space by Minkowski sum, and d overlap free condition

Fig. 7

Illustrations of relative positioning constraints, including a preservation of spatial relationship and b barycenter of a triangle face

Fig. 8

Examples of global and local edge routing, based on a a TreeMap decomposition. b A local flow network for guiding lines connecting reactions and chemical components settled on the block, and c restricted capacity to avoid multiple flows passing on one intermediates node. d A global flow network to build up line-set visualization for chemical components

Fig. 9

Redrawing the human metabolic pathway map of KEGG [68] by using Metabopolis. Blocks with warm colors are grouped to the right and cool colors are grouped to the left as originally designed in the KEGG overview map

Fig. 10

Compared to Fig. 9, the relative positions of urban blocks are manually adjusted by referring to the semantic categories defined in the KEGG overview pathway map [68]

Fig. 11

Human metabolism reconstructed from the Recon project [4, 5]