Hostname: page-component-78c5997874-lj6df Total loading time: 0 Render date: 2024-11-19T05:33:15.007Z Has data issue: false hasContentIssue false
  • English
  • Français

Automatic network reconstruction using ASP

Published online by Cambridge University Press:  06 July 2011

MARKUS DURZINSKY ,
WOLFGANG MARWAN ,
MAX OSTROWSKI ,
TORSTEN SCHAUB  and
ANNEGRET WAGLER
MARKUS DURZINSKY
Affiliation:
Magdeburg Centre for Systems Biology, Universität Magdeburg, Germany
WOLFGANG MARWAN
Affiliation:
Magdeburg Centre for Systems Biology, Universität Magdeburg, Germany
MAX OSTROWSKI
Affiliation:
Universität Potsdam, Germany
TORSTEN SCHAUB
Affiliation:
Universität Potsdam, Germany
ANNEGRET WAGLER
Affiliation:
Université Blaise Pascal, Clermont-Ferrand, France
Get access Rights & Permissions [Opens in a new window]

Abstract

Building biological models by inferring functional dependencies from experimental data is an important issue in Molecular Biology. To relieve the biologist from this traditionally manual process, various approaches have been proposed to increase the degree of automation. However, available approaches often yield a single model only, rely on specific assumptions, and/or use dedicated, heuristic algorithms that are intolerant to changing circumstances or requirements in the view of the rapid progress made in Biotechnology. Our aim is to provide a declarative solution to the problem by appeal to Answer Set Programming (ASP) overcoming these difficulties. We build upon an existing approach to Automatic Network Reconstruction proposed by part of the authors. This approach has firm mathematical foundations and is well suited for ASP due to its combinatorial flavor providing a characterization of all models explaining a set of experiments. The usage of ASP has several benefits over the existing heuristic algorithms. First, it is declarative and thus transparent for biological experts. Second, it is elaboration tolerant and thus allows for an easy exploration and incorporation of biological constraints. Third, it allows for exploring the entire space of possible models. Finally, our approach offers an excellent performance, matching existing, special-purpose systems.

Type
Regular Papers
Information
Theory and Practice of Logic Programming , Volume 11 , Special Issue 4-5: 27th International Conference on Logic Programming , July 2011 , pp. 749 - 766
Copyright
Copyright © Cambridge University Press 2011

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

Akutsu, T., Miyano, S. and Kuhara, S. 1999. Identification of genetic networks from a small number of gene expression patterns under the boolean network model. In Proceedings of the Pacific Symposium on Biocomputing, vol. 4. World Scientific Press, 17–28.Google Scholar
Baral, C. 2003. Knowledge Representation, Reasoning and Declarative Problem Solving. Oxford University Press, Oxford, UK.CrossRefGoogle Scholar
Baral, C., Chancellor, K., Tran, N., Tran, N., Joy, A. and Berens, M. 2004. A knowledge based approach for representing and reasoning about signaling networks. In Proceedings of the Twelfth International Conference on Intelligent Systems for Molecular Biology/Third European Conference on Computational Biology (ISMB'04/ECCB'04). 15–22.CrossRefGoogle Scholar
Dal Palù, A., Dovier, A. and Pontelli, E. 2009. Logic programming techniques in protein structure determination: Methodologies and results. See Erdem et al., 560–566.Google Scholar
Durzinsky, M., Marwan, W. and Wagler, A. 2010. Reconstructing extended petri nets. Journal of Mathematical Biology. Preprint series: 10–19. URL: http://www.fma.ovgu.de.Google Scholar
Durzinsky, M., Wagler, A. and Weismantel, R. 2008. A combinatorial approach to reconstruct petri nets from experimental data. Lecture Notes in Bioinformatics 5307, 328–346.Google Scholar
Durzinsky, M., Wagler, A. and Weismantel, R. 2010. An algorithmic framework for network reconstruction. Theoretical Computer Science. In Press, Corrected Proof. URL: http://www.sciencedirect.com.CrossRefGoogle Scholar
Durzinsky, M., Wagler, A., Weismantel, R. and Marwan, W. 2008. Automatic reconstruction of molecular and genetic networks from discrete time series data. Biosystems 93 (3), 181–190.CrossRefGoogle ScholarPubMed
Dworschak, S., Grell, S., Nikiforova, V., Schaub, T., and Selbig, J. 2008. Modeling biological networks by action languages via answer set programming. Constraints 13 (1–2), 21–65.CrossRefGoogle Scholar
Erdem, E. 2009. PHYLO-ASP: Phylogenetic systematics with answer set programming. See Erdem et al., 567–572.Google Scholar
Erdem, E., Lin, F. and Schaub, T., Eds. 2009. Proceedings of the Tenth International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR'09). Lecture Notes in Artificial Intelligence, vol. 5753. Springer-Verlag.CrossRefGoogle Scholar
Erdem, E. and Türe, F. 2008. Efficient haplotype inference with answer set programming. In Proceedings of the Twenty-third National Conference on Artificial Intelligence (AAAI'08), Fox, D. and Gomes, C., Eds. AAAI, 436–441.Google Scholar
Gebser, M., Guziolowski, C., Ivanchev, M., Schaub, T., Siegel, A., Thiele, S., and Veber, P. 2010. Repair and prediction (under inconsistency) in large biological networks with answer set programming. In Proceedings of the Twelfth International Conference on Principles of Knowledge Representation and Reasoning (KR'10), Lin, F. and Sattler, U., Eds. AAAI, 497–507.Google Scholar
Gebser, M., Kaminski, R., Kaufmann, B., Ostrowski, M., Schaub, T., and Thiele, S. A user's guide to gringo, clasp, clingo, and iclingo. Accessed 7 June 2011. URl: http://potassco.sourceforge.net.Google Scholar
Gebser, M., Schaub, T., Thiele, S., Usadel, B., and Veber, P. 2008. Detecting inconsistencies in large biological networks with answer set programming. In Proceedings of the Twenty-fourth International Conference on Logic Programming (ICLP'08), Garcia de la Banda, M. and Pontelli, E., Eds. Lecture Notes in Computer Science, vol. 5366. Springer-Verlag, Heidelberg, 130–144.Google Scholar
Gebser, M., Kaufmann, B., and Schaub, T. 2009. Solution enumeration for projected Boolean search problems. In Proceedings of the Sixth International Conference on Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR'09), van Hoeve, W. and Hooker, J., Eds. Lecture Notes in Computer Science, vol. 5547. Springer-Verlag, Heidelberg, 71–86.Google Scholar
Gelfond, M. 2008. Answer sets. In Handbook of Knowledge Representation, Lifschitz, V., van Hermelen, F., and Porter, B., Eds. Elsevier, Chapter 7, 285–316.CrossRefGoogle Scholar
Gifford, D. and Jaakkola, T. 2001. Using graphical models and genomic expression data to statistically validate models of genetic regulatory networks. In Proceedings of the Pacific Symposium on Biocomputing vol. 6. 422–433.Google Scholar
goforsys. Accessed 7 June 2011. URL: http://www.goforsys.de.Google Scholar
Laubenbacher, R. and Stigler, B. 2004. A computational algebra approach to the reverse engineering of gene regulatory networks. Journal of Theoretical Biology 229 (4), 523–537.CrossRefGoogle Scholar
Liang, S., Fuhrman, S. and Somogyi, R. 1998. Reveal, a general reverse engineering algorithm for inference of genetic network architectures. Pacific Symposium on Biocomputing 3, 18–29.Google Scholar
Lin, F. and Zhao, Y. 2004. ASSAT: computing answer sets of a logic program by SAT solvers. Artificial Intelligence 157 (1–2), 115–137.CrossRefGoogle Scholar
Marwan, W., Wagler, A. and Weismantel, R. 2008. A mathematical approach to solve the network reconstruction problem. Mathematical Methods of Operatios Research 67 (1), 117–132.CrossRefGoogle Scholar
Ostrowski, M. 2011. Asp encoding for automatic network reconstruction. Accessed 7 June 2011. URL: http://www.cs.uni-potsdam.de/wv/NetworkReconstruction/.Google Scholar
Peer, D., Regev, A., Elidan, G. and Friedman, N. 2001. Inferring subnetworks from perturbed expression profiles. Bioinformatics 17 (suppl 1), 215–224.CrossRefGoogle ScholarPubMed
Repsilber, D., Liljenstrm, H. and Andersson, S. 2002. Reverse engineering of regulatory networks: simulation studies on a genetic algorithm approach for ranking hypotheses. Biosystems 66 (1–2), 31–41.CrossRefGoogle ScholarPubMed
Schaub, T. and Thiele, S. 2009. Metabolic network expansion with ASP. In Proceedings of the Twenty-fifth International Conference on Logic Programming (ICLP'09), Hill, P. and Warren, D., Eds. Lecture Notes in Computer Science, vol. 5649. Springer-Verlag, Heidelberg, 312–326.Google Scholar
Simons, P., Niemelä, I. and Soininen, T. 2002. Extending and implementing the stable model semantics. Artificial Intelligence 138 (1–2), 181–234.CrossRefGoogle Scholar
Syrjänen, T. Lparse 1.0 User's Manual. Accessed 7 June 2011. URL: http://www.tcs.hut.fi/Software/smodels/lparse.ps.gz.Google Scholar
Wagler, A. 2011. Prediction of network structure. Modeling in Systems Biology 16, 307–336.CrossRefGoogle Scholar
Yeung, M., Tegn(c)r, J., and Collins, J. 2002. Reverse engineering gene networks using singular value decomposition and robust regression. Proceedings of the National Academy of Sciences of the United States of America 99 (9), 6163–6168.CrossRefGoogle ScholarPubMed