Modeling the Geometry of the Endoplasmic Reticulum Network - Université de Bretagne Occidentale Access content directly
Conference Papers Year : 2014

Modeling the Geometry of the Endoplasmic Reticulum Network


We have studied the network geometry of the endoplasmic reticulum by means of graph theoretical and integer programming models. The purpose is to represent this structure as close as possible by a class of finite, undirected and connected graphs the nodes of which have to be either of degree three or at most of degree three. We determine plane graphs of minimal total edge length satisfying degree and angle constraints, and we show that the optimal graphs are close to the ER network geometry. Basically, two procedures are formulated to solve the optimization problem: a binary linear program, that iteratively constructs an optimal solution, and a linear program, that iteratively exploits additional cutting planes from different families to accelerate the solution process. All formulations have been implemented and tested on a series of real-life and randomly generated cases. The cutting plane approach turns out to be particularly efficient for the real-life testcases, since it outperforms the pure integer programming approach by a factor of at least 10.
No file

Dates and versions

hal-00982498 , version 1 (24-04-2014)


  • HAL Id : hal-00982498 , version 1


Laurent Lemarchand, Reinhardt Euler, Congping Lin, Imogen Sparkes. Modeling the Geometry of the Endoplasmic Reticulum Network. 1st International Conference on Algorithms for Computational Biology -- AlCob'14, Jul 2014, Tarragona, Spain. pp.132-146. ⟨hal-00982498⟩
203 View
0 Download


Gmail Facebook X LinkedIn More