Human Genome Center, Institute of Medical Science, University of Tokyo, Minato-ku, Japan.
BMC Bioinformatics. 2010 Jun 18;11:335. doi: 10.1186/1471-2105-11-335.
Graph drawing is one of the important techniques for understanding biological regulations in a cell or among cells at the pathway level. Among many available layout algorithms, the spring embedder algorithm is widely used not only for pathway drawing but also for circuit placement and www visualization and so on because of the harmonized appearance of its results. For pathway drawing, location information is essential for its comprehension. However, complex shapes need to be taken into account when torus-shaped location information such as nuclear inner membrane, nuclear outer membrane, and plasma membrane is considered. Unfortunately, the spring embedder algorithm cannot easily handle such information. In addition, crossings between edges and nodes are usually not considered explicitly.
We proposed a new grid-layout algorithm based on the spring embedder algorithm that can handle location information and provide layouts with harmonized appearance. In grid-layout algorithms, the mapping of nodes to grid points that minimizes a cost function is searched. By imposing positional constraints on grid points, location information including complex shapes can be easily considered. Our layout algorithm includes the spring embedder cost as a component of the cost function. We further extend the layout algorithm to enable dynamic update of the positions and sizes of compartments at each step.
The new spring embedder-based grid-layout algorithm and a spring embedder algorithm are applied to three biological pathways; endothelial cell model, Fas-induced apoptosis model, and C. elegans cell fate simulation model. From the positional constraints, all the results of our algorithm satisfy location information, and hence, more comprehensible layouts are obtained as compared to the spring embedder algorithm. From the comparison of the number of crossings, the results of the grid-layout-based algorithm tend to contain more crossings than those of the spring embedder algorithm due to the positional constraints. For a fair comparison, we also apply our proposed method without positional constraints. This comparison shows that these results contain less crossings than those of the spring embedder algorithm. We also compared layouts of the proposed algorithm with and without compartment update and verified that latter can reach better local optima.
图形绘制是理解细胞内或细胞间通路水平生物学调控的重要技术之一。在许多可用的布局算法中，弹簧嵌入算法由于其结果的协调性而被广泛应用于通路绘图、电路布局和 www 可视化等领域。对于通路绘图，位置信息对于理解是必不可少的。然而，当考虑到核内膜、核外膜和质膜等环形位置信息时，需要考虑复杂的形状。不幸的是，弹簧嵌入算法不容易处理这种信息。此外，边缘和节点之间的交叉通常不会明确考虑。
我们提出了一种新的基于弹簧嵌入算法的网格布局算法，该算法可以处理位置信息并提供具有协调外观的布局。在网格布局算法中，搜索最小化成本函数的节点到网格点的映射。通过对网格点施加位置约束，可以轻松考虑包括复杂形状在内的位置信息。我们的布局算法将弹簧嵌入成本作为成本函数的一个组成部分。我们进一步扩展了布局算法，以实现每个步骤中隔室的位置和大小的动态更新。
新的基于弹簧嵌入的网格布局算法和弹簧嵌入算法被应用于三种生物通路；内皮细胞模型、Fas 诱导的细胞凋亡模型和 C. elegans 细胞命运模拟模型。从位置约束来看，我们算法的所有结果都满足位置信息，因此与弹簧嵌入算法相比，得到了更易于理解的布局。从交叉点数量的比较来看，由于位置约束，基于网格布局的算法的结果往往包含更多的交叉点。为了进行公平比较，我们还应用了没有位置约束的我们提出的方法。该比较表明，这些结果比弹簧嵌入算法的结果包含更少的交叉点。我们还比较了具有和不具有隔室更新的提议算法的布局，并验证了后者可以达到更好的局部最优。
