Skip to Main content Skip to Navigation
Conference papers

Modeling the Geometry of the Endoplasmic Reticulum Network

Abstract : 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.
Complete list of metadatas
Contributor : Laurent Lemarchand <>
Submitted on : Thursday, April 24, 2014 - 6:49:14 AM
Last modification on : Wednesday, June 24, 2020 - 4:19:23 PM


  • 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⟩