Modeling the geometry of the endoplasmic reticulum network
Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Springer Verlag (Germany)
Copyright © 2014 Springer International Publishing AG, Part of Springer Science+Business Media. The final publication is available at Springer via http://dx.doi.org/10.1007/978-3-319-07953-0_11.
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. © 2014 Springer International Publishing.
First International Conference, AlCoB 2014, held in July 2014 in Tarragona, Spain.
Vol. 8542 LNBI, pp. 131 - 145