2007
- ▪P. Berman, B. Dasgupta, E.D. Sontag, "Algorithmic issues in reverse engineering of protein and gene networks via the modular response analysis method", Annals of the NY Academy of Sciences, vol. 1115, pp. 132-141, 2007. pdfsystems biology · reaction networks · gene and protein networks · reverse engineering · systems identification · graph algorithms
Abstract
This paper studies a computational problem motivated by the modular response analysis method for reverse engineering of protein and gene networks. This set-cover problem is hard to solve exactly for large networks, but efficient approximation algorithms are given and their complexity is analyzed.
- ▪P. Berman, B. Dasgupta, E.D. Sontag, "Randomized approximation algorithms for set multicover problems with applications to reverse engineering of protein and gene networks", Discrete Applied Mathematics Special Series on Computational Molecular Biology, vol. 155, pp. 733-749, 2007. pdfsystems biology · reaction networks · gene and protein networks · systems identification · reverse engineering
Abstract
This paper investigates computational complexity aspects of a combinatorial problem that arises in the reverse engineering of protein and gene networks, showing relations to an appropriate set multicover problem with large "coverage" factor, and providing a non-trivial analysis of a simple randomized polynomial-time approximation algorithm for the problem.
2006
- ▪B. Dasgupta, P. Berman, E.D. Sontag, "Computational complexities of combinatorial problems with applications to reverse engineering of biological networks", In Advances in Computational Intelligence: Theory & Applications, pp. 303–316, 2006.