An efficient biological pathway layout algorithm combining grid-layout and spring embedder for complicated cellular location information.
An efficient biological pathway layout algorithm combining grid-layout and spring embedder for complicated cellular location information.
复制标题
DOI：
10.1186/1471-2105-11-335
复制
发表时间：
2010-06-18
影响因子：
3
通讯作者：
Miyano S
中科院分区：
文献类型：
--
作者：
Kojima K;Nagasaki M;Miyano S
作图是在信号通路水平上理解细胞内或细胞间生物学调节的重要技术之一。在众多的布局算法中，弹簧嵌入算法由于其布局结果的协调性，不仅在路径绘制中，而且在电路布局和WWW可视化等方面得到了广泛的应用。对于路径图，位置信息对于理解路径图是必不可少的。然而，当考虑诸如核内膜、核外膜和质膜的环形位置信息时，需要考虑复杂的形状。不幸的是，spring embedder算法无法轻松处理这些信息。此外，通常不明确考虑边和节点之间的交叉。提出了一种新的基于弹簧嵌入算法的网格布局算法，该算法可以处理位置信息，并提供具有协调外观的布局。在网格布局算法中，搜索使成本函数最小化的节点到网格点的映射。通过对网格点施加位置约束，可以容易地考虑包括复杂形状的位置信息。我们的布局算法包括弹簧嵌入器成本作为成本函数的一个组成部分。我们进一步扩展的布局算法，使动态更新的位置和大小的车厢在每一步。将新的基于spring嵌入的网格布局算法和spring嵌入算法应用于内皮细胞模型、Fas诱导的细胞凋亡模型和C. elegans细胞命运模拟模型。从位置约束，我们的算法的所有结果满足位置信息，因此，更容易理解的布局相比，弹簧嵌入算法。从交叉点数量的比较，基于网格布局的算法的结果往往包含更多的交叉点比弹簧嵌入算法由于位置的限制。为了公平的比较，我们也应用我们提出的方法没有位置约束。这种比较表明，这些结果包含较少的交叉比弹簧嵌入算法。我们还比较了所提出的算法的布局与不分区更新，并验证了后者可以达到更好的局部最优。
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.
登录
查看更多内容
影响因子：
5.8
作者：
Garcia, Olivier;Saveanu, Cosmin;Aittokallio, Tero
通讯作者：
Aittokallio, Tero
影响因子：
64.8
作者：
Jeong, H;Mason, SP;Oltvai, ZN
通讯作者：
Oltvai, ZN
影响因子：
5.8
作者：
Barsky, Aaron;Gardy, Jennifer L.;Munzner, Tamara
通讯作者：
Munzner, Tamara
影响因子：
5.8
作者：
Li, WJ;Kurata, H
通讯作者：
Kurata, H
DOI：
10.1186/ar576
发表时间：
2002
期刊：
Arthritis research
影响因子：
--
作者：
Pober JS
通讯作者：
Pober JS