chapter

Exploring life: answer set programming in bioinformatics

Authors:

Alessandro Dal Palù,

Agostino Dovier,

Andrea Formisano,

Enrico PontelliAuthors Info & Claims

Declarative Logic Programming: Theory, Systems, and Applications

September 2018

Pages 359 - 412

https://doi.org/10.1145/3191315.3191323

Published: 01 September 2018 Publication History

Abstract

This chapter provides a broad overview of howlogic programming, and more specifically Answer Set Programming (ASP), can be used to model and solve some popular and challenging classes of problems in the general domain of bioinformatics. In particular, the chapter explores the use of ASP in Genomics studies, such as Haplotype inference and Phylogenetic inference, in Structural studies, such as RNA secondary structure prediction and Protein structure prediction, and in Systems Biology. The chapter offers a brief introduction to biology and bioinformatics and working ASP code fragments for the various problems investigated. The chapter serves a dual role: (1) it offers a declarative characterization of a number of core problems in bioinformatics, making them easily understandable; and (2) it provides an "entry point" to the extensive literature on the use of logic-based methods to address such bioinformatics problems, by offering the basic modeling of the problem and pointers to the relevant literature.

References

[1]

E. B. Abdallah, M. Folschette, O. F. Roux, and M. Magnin. 2017. Asp-based method for the enumeration of attractors in non-deterministic synchronous and asynchronous multi-valued networks. Algorithms for Molecular Biology, 12(1): 20:1--20:23. 403

[2]

D. Allouche, I. André, S. Barbe, J. Davies, S. de Givry, G. Katsirelos, B. O'Sullivan, S. D. Prestwich, T. Schiex, and S. Traoré. 2014. Computational protein design as an optimization problem. Artificial Intelligence, 212: 59--79. 404

Digital Library

[3]

G. Alterovitz and M. Ramoni, editors 2010. Knowledge-Based Bioinformatics: From Analysis to Interpretation. Wiley. 406

Digital Library

[4]

S. F. Altschul, W. Gish, W. Miller, E. W. Myers, and D. J. Lipman. 1990. Basic local alignment search tool. Journal of Molecular Biology, 215(3): 403--410. 360

[5]

C. B. Anfinsen. 1973. Principles that govern the folding of protein chains. Science, 181: 223--230. 365

[6]

N. Angelopoulos and G. Giamas. 2014. Prolog Bioinformatic Pipelines: A Case Study in Gene Dysregulation. In Workshop on Constraint-Based Methods in Bioinformatics (WCB14). Lyon, France. 406

[7]

R. Backofen. 2001. The protein structure prediction problem: A constraint optimization approach using a new lower bound. Constraints, 6(2--3): 223--255. 392, 404

Digital Library

[8]

R. Backofen and S. Will. 2006. A constraint-based approach to fast and exact structure prediction in three-dimensional protein models. Constraints, 11(1): 5--30. 392, 404

Digital Library

[9]

R. Backofen, A. Dal Palù, A. Dovier, and S. Will, Eds. 2012. Thematic series of AMB on constraints in bioinformatics. In Algorithms for Molecular Biology. BioMed Central Ltd. http://www.biomedcentral.com/collections/constr-and-bioinf. 361, 404

[10]

K. Baclawski and T. Niu. 2005. Ontologies for Bioinformatics. The MIT Press. 406

Digital Library

[11]

P. Barahona and L. Krippahl. 2008. Constraint programming in structural bioinformatics. Constraints, 13(1--2): 3--20. 404

Digital Library

[12]

P. Barahona, L. Krippahl, and O. Perriquet. 2011. Bioinformatics: A challenge to constraint programming. Hybrid Optimization, 45: 463--487. 404

[13]

C. Baral. 2003. Knowledge Representation, Reasoning and Declarative Problem Solving. Cambridge University Press. 368

Digital Library

[14]

C. Baral, K. Chancellor, N. Tran, and N. Tran. 2003. Representing and reasoning about signal networks: an illustration using NFkB dependent signaling pathways. In CSB, pp. 623--628. IEEE Computer Society. 403

Digital Library

[15]

C. Baral, K. Chancellor, N. Tran, N. Tran, A. M. Joy, and M. E. Berens. 2004. A knowledgebased approach for representing and reasoning about signaling networks. In ISMB/ECCB (Supplement of Bioinformatics), pp. 15--22. 403

Digital Library

[16]

J. Bard. 2003. Ontologies: formalising biological knowledge for bioinformatics. Functional Genomics and Bioinformatics, 25: 501--506. 406

[17]

M. Bauer, G. W. Klau, and K. Reinert. 2007. RNA pseudoknot prediction in energy-based models. BMC Bioinformatics, 8. 389

[18]

M. Bavarian and V. Dahl. November 2006. Constraint based methods for biological sequence analysis. Journal of Universal Computer Science, 12(11): 1500--1520. 386, 388, 405

[19]

L. Bortolussi, S. Fonda, and A. Policriti. 2007. Constraint-based simulation of biological systems described by molecular interaction maps. In Proceedings of the 2007 IEEE International Conference on Bioinformatics and Biomedicine, BIBM '07, pp. 288--293. IEEE Computer Society. 405

Digital Library

[20]

A. Brazma, P. Hingamp, J. Quackenbush, G. Sherlock, P. Spellman, C. Stoeckert, J. Aach, W. Ansorge, C. Ball, H. Causton, T. Gaasterland, P. Glenisson, F. Holstege, I. Kim, V. Markowitz, J. Matese, H. Parkinson, A. Robinson, U. Sarkans, S. Schulze-Kremer, J. Stewart, R. Taylor, J. Vilo, and M. Vingron. 2001. Minimum information about a microarray experiment (MIAME)-toward standards for microarray data. Nature Genetics, 4(29): 365--371. 360

[21]

D. Brooks, E. Erdem, J. Minett, and D. Ringe. 2005. Character-based cladistics and Answer Set Programming. In Practical Aspects of Declarative Languages, pp. 37--51. Springer Verlag. 377

Digital Library

[22]

D. Brooks, E. Erdem, S. Erdogan, J. Minett, and D. Ringe. 2007. Inferring phylogenetic trees using answer set programming. Journal of Automated Reasoning, 39(4): 471--511. 377

Digital Library

[23]

D. G. Brown and I. M. Harrower. 2006. Integer programming approaches to haplotype inference by pure parsimony. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3(2): 141--154. 384

Digital Library

[24]

D. Buezas, J. Almeida, and P. Barahona. 2010. Minimizing enzymes to diferenciate between species. In Workshop on Constraint Based Methods for Bioinformatics (WCB10), pp. 75--82. Edinburgh, UK. 404

[25]

A. Burger, D. Davidson, and R. Baldock. 2004. Formalization of Mouse Embryo Anatomy. Bioinformatics, 20: 259--267. 406

Digital Library

[26]

D. Cakmak. 2010. Reconstructing Weighted Phylogenetic Trees and Weighted Phylogenetic Networks using Answer Set Programming. Master's thesis, Sabanci University. 377, 379

[27]

D. Cakmak, E. Erdem, and H. Erdogan. 2009. Computing weighted solutions in answer set programming. In Logic Programming and Nonmonotonic Reasoning, pp. 416--422. Springer Verlag. 377

Digital Library

[28]

D. Cakmak, H. Erdogan, and E. Erdem. 2010. Computing weighted solutions in ASP: Representation-based method vs. search-based method. In Proc. of RCRA Workshop on Experimental Evaluation of Algorithms for Solving Problems with Combinatorial Explosion. 377

Digital Library

[29]

L. Calzone, F. Fages, and S. Soliman. 2006. Biocham:an environment for modeling biological systems and formalizing experimental knowledge. Bioinformatics, 22(14): 1805--1807. 404

Digital Library

[30]

F. Campeotto, A. Dal Palù, A. Dovier, F. Fioretto, and E. Pontelli. 2012. A filtering technique for fragment assembly- based proteins loop modeling with constraints. In M. Milano, editor, CP, vol. 7514 of Lecture Notes in Computer Science, pp. 850--866. Springer. 393

[31]

F. Campeotto, A. Dal Palù, A. Dovier, F. Fioretto, and E. Pontelli. 2013. A constraint solver for flexible protein model. Jounral of Artificial Intelligence Research (JAIR), 48: 953--1000. 393, 407

Digital Library

[32]

F. Campeotto, A. Dovier, and E. Pontelli. 2015. A declarative concurrent system for protein structure prediction on GPU. The Journal of Experimental and Theoretical Artificial Intelligence,, 27(5): 503--541. 393

[33]

A. Canutescu and R. Dunbrack. 2003. Cyclic coordinate descent: a robotics algorithm for protein loop closure. Protein Science, 12: 963--972. 393

[34]

D. Catanzaro and M. Labbé. 2009. The pure parsimony haplotyping problem: overview and computational advances. International Transactions in Operational Research, 16(5): 561--584. 384

[35]

C. Chaouiya, E. Remy, B. Mossé, and D. Thieffry. 2003. Qualitative analysis of regulatory graphs: A computational tool based on a discrete formal framework. In L. Benvenuti, A. D. Santis, and L. Farina, editors, POSTA, vol. 294 of Lecture Notes in Control and Information Sciences, pp. 119--126. Springer. 403

[36]

L. Chen, R.-S. Wang, and X.-S. Zhang. 2009. Biomolecular Networks: Methods and Applications in Systems Biology. John Wiley & Sons. 399, 403

[37]

B. Chisham, B. Wright, T. Le, T. Son, and E. Pontelli. 2011. CDAO-Store: ontology-driven data integration for phylogenetic analysis. BMC Bioinformatics, 12: 98. 361, 379, 406, 407

[38]

H. Christiansen, C. T. Have, O. T. Lassen, and M. Petit. 2010. Inference with constrained hidden markov models in prism. Theory and Practice of Logic Programming, 10(4--6): 449--464. 405

Digital Library

[39]

A. G. Clark. 1990. Inference of haplotypes from PCR amplified samples of diploid populations. Molecular Biology and Evolution, 7(2): 111--122. 384

[40]

P. Clote and R. Backofen. 2001. Computational Molecular Biology: An Introduction. John Wiley & Sons. 360, 362

[41]

E. Çoban, E. Erdem, and F. Türe. 2008. Comparing ASP, CP, ILP on some challenging problems. In The 2nd International Workshop on Logic and Search -- LaSh08. 383, 384

[42]

J. Cohen. June 2004. Bioinformatics: An introduction for computer scientists. ACM Computing Sureys., 36(2): 122--158. 362

Digital Library

[43]

G. Collet, D. Eveillard, M. Gebser, S. Prigent, T. Schaub, A. Siegel, and S. Thiele. 2013. Extending the metabolic network of Ectocarpus Siliculosus using answer set programming. In P. Cabalar and T. Son, editors, Logic Programming and Nonmonotonic Reasoning, vol. 8148 of Lecture Notes in Computer Science, pp. 245--256. Springer Berlin Heidelberg. 399, 402, 406

Digital Library

[44]

F. Corblin, S. Tripodi, E. Fanchon, D. Ropers, and L. Trilling. 2009. A declarative constraint-based method for analyzing discrete genetic regulatory networks. Biosystems, 98(2): 91--104. 403

[45]

F. Corblin, E. Fanchon, and L. Trilling. 2010. Applications of a formal approach to decipher discrete genetic networks. BMC Bioinformatics, 11: 385. 403

[46]

F. Corblin, E. Fanchon, L. Trilling, C. Chaouiya, and D. Thieffry. 2012. Automatic inference of regulatory and dynamical properties from incomplete gene interaction and expression data. In M. A. Lones, S. L. Smith, S. A. Teichmann, F. Naef, J. A. Walker, and M. Trefzer, editors, IPCAT, vol. 7223 of Lecture Notes in Computer Science, pp. 25--30. Springer. 403

Digital Library

[47]

P. Crescenzi, D. Goldman, C. Papadimitrou, A. Piccolboni, and M. Yannakakis. 1998. On the complexity of protein folding. In Proc. of STOC, pp. 597--603. 390

Digital Library

[48]

F. Crick. 1958. On protein synthesis. In F. Sanders, editor, Symposia of the Society for Experimental Biology, Number XII: The Biological Replication of Macromolecules, p. 138--163. Cambridge University Press. 362

[49]

F. Crick. 1970. Central dogma of molecular biology. Nature, 227: 561--3. 362

[50]

A. Dal Palù, A. Dovier, and F. Fogolari. 2004. Constraint logic programming approach to protein structure prediction. BMC Bioinformatics, 5: 186. 392

[51]

A. Dal Palù, A. Dovier, F. Fages, and S. Will. 2007. Constraint based methods for bioinformatics. In PART VI of Trends in Constraint Programming, pp. 125--146. Hermes Science. 361, 404

[52]

A. Dal Palù, A. Dovier, and E. Pontelli. 2007. A constraint solver for discrete lattices, its parallelization, and application to protein structure prediction. Software Practice and Experience, 37(13): 1405--1449. 392

Digital Library

[53]

A. Dal Palù, A. Dovier, and S. Will. June 2008. Introduction to the special issue on bioinformatics and constraints. Constraints, 13(1--2): 1--2. 361, 404

Digital Library

[54]

A. Dal Palù, A. Dovier, F. Fogolari, and E. Pontelli. 2010. CLP-based protein fragment assembly. TPLP, 10 (4--6): 709--724. 392

Digital Library

[55]

A. Dal Palù, M. Möhl, and S. Will. 2010. A propagator for maximum weight string alignment with arbitrary pairwise dependencies. In Proceedings of the 16th international conference on Principles and practice of constraint programming, CP'10, pp. 167--175. Springer-Verlag, Berlin, Heidelberg. 389,404

Digital Library

[56]

A. Dal Palù, A. Dovier, F. Fogolari, and E. Pontelli. 2012a. Protein structure analysis with constraint programming. In P. Cozzini, G. Kellogg, D. Rotella, and A. Martinez, editors, Computational Approaches to Nuclear Receptors, chap. 3, pp. 40--59. The Royal Society of Chemistry. 392, 407

[57]

A. Dal Palù, F. Spyrakis, and P. Cozzini. 2012b. A new approach for investigating protein flexibility based on Constraint Logic Programming: The first application in the case of the estrogen receptor. European Journal of Medicinal Chemistry, 49: 127--140. 407

[58]

E. Dantsin, T. Eiter, G. Gottlob, and A. Voronkov. Sept. 2001. Complexity and expressive power of logic programming. ACM Computing Surveys, 33(3): 374--425. 368

Digital Library

[59]

W. Day. 1983. Computationally difficult parsimony problems in phylogenetic systematics. Journal of Theoretical Biology, 103(3): 429--438.

[60]

W. Day and D. Sankoff. 1986. Computational complexity of inferring phylogenies by compatibility. Systematic Zoology, 35(2): 224--229.

[61]

D. De Maeyer, J. Renkens, L. Cloots, L. De Raedt, and K. Marchal. 2013. Phenetic: network-based interpretation of unstructured gene lists in e. coli. Molecular BioSystems, 9: 1594--1603. 405

[62]

L. Di Gaspero and A. Roli. 2008. Stochastic local search for large-scale instances of the haplotype inference problem by pure parsimony. Journal of Algorithms, 63(1--3): 55--69. 384

Digital Library

[63]

K. A. Dill. 1990. Dominant forces in protein folding. Biochemistry, 29: 7133--7155. 392

[64]

A. Dobson. 1969. Lexicostatistical grouping. Anthropological Linguistics, 11: 216--221. 371

[65]

G. Dooms, Y. Deville, and P. Dupont. 2005. CP(Graph): Introducing a graph computation domain in constraint programming. In P. van Beek, editor, Principles and Practice of Constraint Programming - CP 2005, vol. 3709 of Lecture Notes in Computer Science, pp. 211--225. Springer Berlin Heidelberg. 405

Digital Library

[66]

A. Dovier, A. Formisano, and E. Pontelli. 2007. An experimental comparison of constraint logic programming and answer set programming. In Proceedings of the Twenty-Second AAAI Conference on Artificial Intelligence, July 22--26, 2007, Vancouver, British Columbia, Canada, pp. 1622--1625. AAAI Press. 404

Digital Library

[67]

A. Dovier, A. Formisano, and E. Pontelli. 2009. An empirical study of constraint logic programming and answer set programming solutions of combinatorial problems. Journal of Experimental and Theoretical Artificial Intelligence, 21(2): 79--121. 368, 390, 404

Digital Library

[68]

W. Dubitzky, O. Wolkenhauer, K.-H. Cho, and H. Yokota. 2013. Encyclopedia of Systems Biology. Springer. 402

Digital Library

[69]

M. Durzinsky, W. Marwan, M. Ostrowski, T. Schaub, and A. Wagler. 2011. Automatic network reconstruction using ASP. TPLP, 11 (4--5): 749--766.

[70]

S. Dworschak, S. Grell, V. J. Nikiforova, T. Schaub, and J. Selbig. 2008a. Modeling biological networks by action languages via answer set programming. Constraints, 13 (1--2): 21--65. 404

Digital Library

[71]

S. Dworschak, T. Grote, A. König, T. Schaub, and P. Veber. 2008b. The system BioC for reasoning about biological models in action language C. In ICTAI (1), pp. 11--18. IEEE Computer Society. 404

Digital Library

[72]

J. Eisen and P. Hanawalt. 1999. A phylogenomic study of DNA repair genes, proteins, and processes. Mutation Research - DNA Repair, 435(3): 171--213. 371

[73]

E. Erdem. 2011. Applications of answer set programming in phylogenetic systematics. In M. Balduccini and T. C. Son, editors, Logic Programming, Knowledge Representation, and Nonmonotonic Reasoning, vol. 6565 of Lecture Notes in Computer Science, pp. 415--431. Springer. 377, 406

Digital Library

[74]

E. Erdem and U. Oztok. 2012. BioQuery-ASP: Querying Biomedical Databases and Ontologies Using Answer Set Programming. EMBnet. journal, 18. 406

[75]

E. Erdem and F. Türe. 2008. Efficient haplotype inference with answer set programming. In D. Fox and C. P. Gomes, editors, Proceedings of the Twenty-Third AAAI Conference on Artificial Intelligence, AAAI 2008, Chicago, IL, July 13--17, 2008, pp. 436--441. AAAI Press. 381, 382, 383

Digital Library

[76]

E. Erdem, V. Lifschitz, L. Nakhleh, and D. Ringe. 2003. Reconstructing the evolutionary history of Indo-European languages using answer set programming. In Practical Aspects of Declarative Languages, pp. 160--176. Springer Verlag. 378

Digital Library

[77]

E. Erdem, V. Lifschitz, and D. Ringe. 2006. Temporal phylogenetic networks and logic programming. Theory and Practice of Logic Programming, 6(5): 539--558. 378, 379

Digital Library

[78]

E. Erdem, O. Erdem, and F. Türe. 2009. HAPLO-ASP: Haplotype inference using answer set programming. In E. Erdem, F. Lin, and T. Schaub, editors, Logic Programming and Nonmonotonic Reasoning, 10th International Conference, LPNMR 2009, Potsdam, Germany, September 14--18, 2009. Proceedings, vol. 5753 of Lecture Notes in Computer Science, pp. 573--578. Springer. 383

Digital Library

[79]

G. Estabrook. 1997. Ancestor-descendant relations and incompatible data: Motivation for research in discrete mathematics. In Mathematical Hierarchies and Biology, vol. 27 of DIMAS Series in Discrete Mathematics, pp. 1--28. American Mathematical Society. 374

[80]

E. Fanchon, F. Corblin, L. Trilling, B. Hermant, and D. Gulino. 2005. Modeling the molecular network controlling adhesion between human endothelial cells: Inference and simulation using constraint logic programming. In V. Danos and V. Schachter, editors, Computational Methods in Systems Biology, vol. 3082 of Lecture Notes in Computer Science, pp. 104--118. Springer Berlin Heidelberg. 405

Digital Library

[81]

T. Fayruzov, M. D. Cock, C. Cornelis, and D. Vermeir. 2009. Modeling protein interaction networks with answer set programming. In BIBM, pp. 99--104. IEEE Computer Society. 403

Digital Library

[82]

T. Fayruzov, J. Janssen, C. Cornelis, D. Vermeir, and M. De Cock. 2010. Extending boolean regulatory network models with answer set programming. In Proceedings 2010 IEEE International Conference on Bioinformatics and Biomedicine Workshops (BIBMW 2010), pp. 207--212. IEEE. 403

[83]

T. Fayruzov, J. Janssen, D. Vermeir, C. Cornelis, and M. D. Cock. 2011. Modelling gene and protein regulatory networks with answer set programming. IJDMB, 5(2): 209--229. 403

Digital Library

[84]

F. Fioretto and E. Pontelli. 2013. Constraint programming in community-based gene regulatory network inference. In A. Gupta and T. Henzinger, editors, Computational Methods in Systems Biology, vol.8130 of Lecture Notes in Computer Science, pp.135--149. Springer Berlin Heidelberg. 405

Digital Library

[85]

L. F. Fitime, O. F. Roux, C. Guziolowski, and L. Paulevé. 2017. Identification of bifurcation transitions in biological regulatory networks using answer-set programming. Algorithms for Molecular Biology, 12(1): 19:1--19:14.

[86]

C. A. Floudas. 2007. Computational methods in protein structure prediction. Biotechnology and Bioengineering, 97(2): 207--213. 392

[87]

M. Folschette, L. Paulevé, K. Inoue, M. Magnin, and O. Roux. 2012. Concretizing the process hitting into biological regulatory networks. In D. Gilbert and M. Heiner, editors, CMSB, vol. 7605 of Lecture Notes in Computer Science, pp. 166--186. Springer. 403

[88]

C. Frioux, T. Schaub, S. Schellhorn, A. Siegel, and P. Wanko. 2017. Hybrid metabolic network completion. In M. Balduccini and T. Janhunen, editors, Logic Programming and Nonmonotonic Reasoning - 14th International Conference, LPNMR 2017, Espoo, Finland, July 3--6, 2017, Proceedings, vol. 10377 of Lecture Notes in Computer Science, pp. 308--321. Springer. 402

[89]

M. Gebser, C. Guziolowski, M. Ivanchev, T. Schaub, A. Siegel, S. Thiele, and P. Veber. 2010a. Repair and prediction (under inconsistency) in large biological networks with answer set programming. In F. Lin, U. Sattler, and M. Truszczyński, editors, Principles of Knowledge Representation and Reasoning, 2010. Toronto, Canada. 397, 403

Digital Library

[90]

M. Gebser, A. König, T. Schaub, S. Thiele, and P. Veber. 2010b. The BioASP library: ASP solutions for systems biology. In ICTAI (1), pp. 383--389. IEEE Computer Society. 403

Digital Library

[91]

M. Gebser, T. Schaub, S. Thiele, and P. Veber. 2011. Detecting inconsistencies in large biological networks with answer set programming. TPLP, 11 (2--3): 323--360. 396, 397, 402, 403, 407, 411

Digital Library

[92]

M. Gelfond. 2008. Answer sets. In F. van Harmelen, V. Lifschitz, B. Porter, Editors, Handbook of Knowledge Representation. chap. 7. Elsevier.

[93]

M. Gelfond and V. Lifschitz. 1988. The stable model semantics for logic programming. In R. A. Kowalski and K. A. Bowen, editors, Logic Programming, Proceedings of the Fifth International Conference and Symposium, Seattle, Washington, August 15--19, 1988 (2 vols.), pp. 1070--1080. MIT Press. 366, 367

[94]

I. Gent, P. Prosser, B. Smith, and W. Wei. 2003. Supertree construction with constraint programming. In F. Rossi, editor, Principles and Practice of Constraint Programming---CP 2003, vol. 2833 of Lecture Notes in Computer Science, pp. 837--841. Springer Berlin Heidelberg. 404

Digital Library

[95]

H. Gleason. 1959. Counting and calculating for historical reconstruction. Anthropological Linguistics, 1: 22--32. 371

[96]

G. H. Gonnet. 2004. Some string matching problems from bioinformatics which still need better solutions. Journal of Discrete Algorithms, 2(1): 3 -- 15. The 9th International Symposium on String Processing and Information Retrieval. 360

Digital Library

[97]

A. Graça, J. Marques-Silva, I. Lynce, and A. Oliveira. 2007. Efficient haplotype inference with pseudo-boolean optimization. In Proceedings of the Algebraic Biology Conference. 383

Digital Library

[98]

A. Graça, I. Lynce, J. Marques-Silva, and A. L. Oliveira. 2010. Haplotype inference by pure parsimony: A survey. Journal of Computational Biology, 17(8): 969--992. 384

[99]

A. Graça, J. Marques-Silva, and I. Lynce. 2011. Haplotype inference using propositional satisfiability. In R. Bruni, editor, Mathematical Approaches to Polymer Sequence Analysis and Related Problems, pp. 127--147. Springer. 384

[100]

T. Gruber. 1995. Toward principles for the design of ontologies used for knowedge sharing. International Journal of Human Computer Studies, 43(5--6). 371

Digital Library

[101]

D. Gusfield. 1997. Algorithms on Strings, Trees, and Sequences: Computer Science and Computational Biology. Cambridge University Press, New York. 360, 362

Digital Library

[102]

D. Gusfield. 2002a. Haplotyping as perfect phylogeny: conceptual framework and efficient solutions. In Sixth Annual International Conference on Computational Biology, pp. 166--175. ACM. 384

Digital Library

[103]

D. Gusfield. 2002b. An overview of combinatorial methods for haplotype inference. In S. Istrail, M. S. Waterman, and A. G. Clark, editors, Computational Methods for SNPs and Haplotype Inference, vol. 2983 of Lecture Notes in Computer Science, pp. 9--25. Springer. 380

[104]

D. Gusfield and S. H. Orzack. 2005. Haplotype inference. In S. Aluru, editor, Handbook of Computational Molecular Biology, Computer & Information Science, chap. 18. Chapman & Hall/CRC. 380, 384

[105]

C. Guziolowski, S. Videla, F. Eduati, S. Thiele, T. Cokelaer, A. Siegel, and J. Saez-Rodriguez. 2013. Exhaustively characterizing feasible logic models of a signaling network using answer set programming. Bioinformatics, 29(18): 2320--2326. 403

[106]

B. V. Halldórsson, V. Bafna, N. Edwards, R. Lippert, S. Yooseph, and S. Istrail. 2002. A survey of computational methods for determining haplotypes. In S. Istrail, M. S. Waterman, and A. G. Clark, editors, Computational Methods for SNPs and Haplotype Inference, vol. 2983 of Lecture Notes in Computer Science, pp. 26--47. Springer. 380, 384

[107]

R. Hoehndorf, F. Loebe, J. Kelso, and H. Herre. 2007. Representing default knowledge in biomedical ontologies: application to the integration of anatomy and phenotype ontologies. BMC Bioinformatics, 8: 377. 406

[108]

R. Hudson. 2002. Generating samples under a wrightfisher neutral model of genetic variation. Bioinformatics, 18: 337--338. 384

[109]

International Human Genome Sequencing Consortium. 2004. Finishing the euchromatic sequence of the human genome. Nature, 431: 931--45.

[110]

G. Jin, L. Nakhleh, S. Snir, and T. Tuller. 2007. Inferring phylogenetic networks by the maximum parsimony criterion: a case study. Molecular Biology and Evolution, 24(1): 324--337. 379

[111]

N. C. Jones and P. Pevzner. 2004. An Introduction to Bioinformatics Algorithms. Computational Molecular Biology. MIT Press, Cambridge, MA, London. 362

[112]

T. Kelsey, L. Kotthoff, C. Jefferson, S. Linton, I. Miguel, P. Nightingale, and I. Gent. 2014. Qualitative modelling via constraint programming. Constraints, 19(2): 163--173. 405

[113]

A. Kimmig, V. S. Costa, R. Rocha, B. Demoen, and L. D. Raedt. 2008. On the efficient execution of problog programs. In Logic Programming, 24th International Conference, ICLP 2008, Udine, Italy, December 9--13 2008, Proceedings, pp. 175--189. 405

Digital Library

[114]

L. Koponen, E. Oikarinen, T. Janhunen, and L. Säilä. 2015. Optimizing phylogenetic supertrees using answer set programming. TPLP, 15(4-5): 604--619. 378

[115]

G. Lancia, M. C. Pinotti, and R. Rizzi. 2004. Haplotyping populations by pure parsimony: Complexity of exact and approximation algorithms. INFORMS Journal on Computing, 16 (4): 348--359. 380, 381

Digital Library

[116]

A. Larhlimi and A. Bockmayr. 2009. A new constraint-based description of the steady-state flux cone of metabolic networks. Discrete Applied Mathematics, 157(10): 2257--2266. Networks in Computational Biology. 405

Digital Library

[117]

T. Le, H. Nguyen, E. Pontelli, and T. Son. 2012. ASP at Work: An ASP Implementation of PhyloWS. In International Conference on Logic Programming, pp. 359--369. 379, 406

[118]

W. Le Quesne. 1969. A method of selection of characters in numerical taxonomy. Systematic Zoology, 18: 201--205. 372

[119]

W. Le Quesne. 1972. Further studies based on the uniquely derived character concept. Systematic Zoology, 21: 281--288. 372

[120]

J. Lee, D. Lee, H. Park, E. Coutsias, and C. Seok. 2010. Protein Loop Modeling by Using Fragment Assembly and Analytical Loop Closure. Proteins, 78(16): 3428--3436. 393

[121]

A. Lesk. 2008. Introduction to Bioinformatics. Oxford University Press. 360

Digital Library

[122]

D. Liberles and M. Wayne. 2002. Tracking adaptive evolutionary events in genomic sequences. Genome Biol., 3(6). 371

[123]

P. Liu, F. Zhu, D. Rassokhin, and D. Agrafiotis. 2009.Aself-organizing algorithmfor modeling protein loops. PLOS Computational Biology, 5(8).

[124]

J. W. Lloyd. 1987. Foundations of Logic Programming. Springer-Verlag. 366, 368

Digital Library

[125]

I. Lynce and J. Marques-Silva. 2006. Efficient haplotype inference with boolean satisfiability. In Proceedings of the National Conference on Artificial Intelligence (AAAI). 383

Digital Library

[126]

R. Lyngso and C. Pedersen. 2000. RNA pseudoknot prediction in energy-based models. Journal of Computational Biology, 7(3--4): 409--427.

[127]

M. Mann, F. Nahar, N. Schnorr, R. Backofen, P. F. Stadler, and C. Flamm. 2014. Atom mapping with constraint programming. Algorithms for Molecular Biology, 9: 23. 404

[128]

V. W. Marek and M. Truszczyński. 1999. Stable models and an alternative logic programming paradigm. In The Logic Programming Paradigm, pp. 375--398. Springer Verlag. 366

[129]

E. Mayr. 1964. Systematics and the Origin of Species. Dover Publications. 379

[130]

J. S. McCaskill. 1990. The equilibrium partition function and base pair binding probabilities for RNA secondary structure. Biopolymers, 29(6--7): 1105--1119. 386, 388

[131]

S. Muggleton, A. Srinivasan, R. D. King, and M. J. E. Sternberg. 1998. Biochemical knowledge discovery using inductive logic programming. In S. Arikawa and H. Motoda, editors, Discovery Science, First International Conference, DS '98, Fukuoka, Japan, December 14--16, 1998, Proceedings, vol. 1532 of Lecture Notes in Computer Science, pp. 326--341. Springer. 405

Digital Library

[132]

C. Mungall. 2009. Experiences Using Logic Programming in Bioinformatics. In International Conference on Logic Programming, pp. 1--21. Springer Verlag. 406

Digital Library

[133]

S. Mørk and I. Holmes. 2012. Evaluating bacterial gene-finding hmm structures as probabilistic logic programs. Bioinformatics, 28(5): 636--642. 405

Digital Library

[134]

L. Nakhleh, T. Warnow, C. Linder, and K. St John. 2005. Reconstructing reticulate evolution in species-theory and practice. Journal of Computational Biology, 12(6): 796--811. 379

[135]

A. Neumaier. 1997. Molecular modeling of proteins and mathematical prediction of protein structure. SIAM Review, 39: 407--460. 392

Digital Library

[136]

J. Nichols and T. Warnow. 2008. Tutorial on computational linguistic phylogeny. Language and Linguistics Compass, 2/5: 760--820. 379

[137]

I. Niemelä. 1999. Logic programs with stable model semantics as a constraint programming paradigm. Annals of Mathematics and Artificial Intelligence, 25(3--4): 241--273. 366

Digital Library

[138]

Z. Nikoloski, S. Grimbs, P. May, and J. Selbig. 2008a. Metabolic networks are NP-hard to reconstruct. Journal of Theoretical Biology, 254(4): 807--816. 400

[139]

Z. Nikoloski, S. Grimbs, J. Selbig, and O. Ebenhöh. 2008b. Hardness and approximability of the inverse scope problem. In K. A. Crandall and J. Lagergren, editors, WABI, vol. 5251 of Lecture Notes in Computer Science, pp. 99--112. Springer. 399, 400

Digital Library

[140]

R. Nussinov and A. B. Jacobson. 1980. Fast algorithm for predicting the secondary structure of single-stranded RNA. Proceedings of the National Academy of Sciences USA, 77(11): 6309--6313. 386, 388

[141]

M. Ostrowski, L. Paulevé, T. Schaub, A. Siegel, and C. Guziolowski. 2016. Boolean network identification from perturbation time series data combining dynamics abstraction and logic programming. Biosystems, 149: 139--153. 403

[142]

Y. Pan, E. Pontelli, and T. Son. 2010. BSIS: An Experiment in Automating Bioinformatics Tasks Through Intelligent Workflow Construction. In Semantic e-Science, pp. 189--238. Springer Verlag. 360

[143]

F. Prosdocimi, B. Chisham, E. Pontelli, J. Thompson, and A. Stoltzfus. 2009. Initial implementation of a comparative data analysis ontology. Evolutionary Bioinformatics, 5: 47--66. 379, 407

[144]

S. Raman, R. Vernon, J. Thompson, M. Tyka, R. Sadreyev, J. Pei, D. Kim, E. Kellogg, F. DiMaio, O. Lange, L. Kinch, W. Sheffler, B.-H. Kim, R. Das, N. V. Grishin, and D. Baker. 2009. Structure prediction for CASP8 with all-atom refinement using Rosetta. Proteins, 77(Suppl. 9): 89--99. 393

[145]

O. Ray, T. Soh, and K. Inoue. 2010. Analyzing pathways using ASP-based approaches. In K. Horimoto, M. Nakatsui, and N. Popov, editors, ANB, vol. 6479 of Lecture Notes in Computer Science, pp. 167--183. Springer. 403

Digital Library

[146]

D. Ringe, T. Warnow, and A. Taylor. 2002. Indo-European and computational cladistics. Transactions of the Philological Society, 100(1): 59--129. 371

[147]

G. Rodrigo, J. Carrera, and A. Jaramillo. 2011. Computational design of synthetic regulatory networks from a genetic library to characterize the designability of dynamical behaviors. Nucleic Acids Research, 39(20): e138--e138. 405

[148]

R. Rossnes, I. Eidhammer, and D. Liberles. 2007. Phylogenetic reconstruction of ancestral character states for gene expression and mRNA splicing data. BMC Bioinformatics, 6(1): 127. 372

[149]

M. Sanchez, S. Givry, and T. Schiex. June 2008. Mendelian error detection in complex pedigrees using weighted constraint satisfaction techniques. Constraints, 13 (1--2): 130--154. 405

Digital Library

[150]

D. Sankoff. 1985. Simultaneous solution of the RNA folding, alignment and protosequence problems. SIAM Journal on Applied Mathematics, 45 (5): 810--825. 388

Digital Library

[151]

T. Sato. 1995. A statistical learning method for logic programs with distribution semantics. In Proceedings of the 12th International Conference on Logic Programming (ICLP 95), pp. 715--729. 405

[152]

T. Schaub and S. Thiele. 2009. Metabolic network expansion with answer set programming. In P. M. Hill and D. S. Warren, editors, ICLP, vol. 5649 of Lecture Notes in Computer Science, pp. 312--326. Springer. 399, 401, 402, 406

Digital Library

[153]

N. Schuurman and A. Leszczynski. 2008. Ontologies for bioinformatics. Bioinformatics and Biology Insights, 2: 187--200. 406

[154]

R. Sharan, B. V. Halldórsson, and S. Istrail. 2006. Islands of tractability for parsimony haplotyping. IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3(3): 303--311. 384

Digital Library

[155]

S. Soliman, F. Fages, and O. Radulescu. 2014. A constraint solving approach to model reduction by tropical equilibration. Algorithms for Molecular Biology, 9(1): 24. 405

[156]

T. Son, E. Pontelli, and T. Le. 2013. Two Applications of the ASP-Prolog System: Decomposable Programs and Multi-context Systems. In Practical Aspects of Declarative Languages. Springer Verlag. 377

Digital Library

[157]

E. Stone and A. Sidow. 2005. Physicochemical constraint violation by missense substitutions mediates impairment of protein function and disease severity. Genome Research, 15(7): 978--986. 371

[158]

A. Taylor, T. Warnow, and D. Ringe. 2000. Character-based reconstruction of a linguistic cladogram. In J. Smith and D. Bentley, editors, Historical Linguistics, vol. 1, pp. 393--408. Benjamins. 371

[159]

D. Thau. 2010. Reasoning about Taxonomies. Ph.D. thesis, U.C. Davis. 379 379

Digital Library

[160]

P. Thebault, S. De Givry, T. Schiex, and C. Gaspin. 2006. Searching rna motifs and their intermolecular contacts with constraint networks. Bioinformatics, 22(17): 2074--2080. 405

Digital Library

[161]

S. Thiele. 2012. Modeling Biological Systems with Answer Set Programming. Doctor rerum naturalium thesis, Universität Potsdam. 412

[162]

R. Thomas. 1991. Regulatory networks seen as asynchronous automata: A logical description. Journal of Theoretical Biology, 153(1): 1--23. 403

[163]

R. Thomas and M. Kaufman. 2001. Multistationarity, the basis of cell differentiation and memory. I. structural conditions of multistationarity and other nontrivial behavior. Chaos: An Interdisciplinary Journal of Nonlinear Science, 11(1): 170--179. 403

[164]

R. Thomas, D. Thieffry, and M. Kaufman. 1995. Dynamical behaviour of biological regulatory networks---I. biological role of feedback loops and practical use of the concept of the loop-characteristic state. Bulletin of Mathematical Biology, 57(2): 247--276. 403

[165]

J. Thorne. 2000. Models of protein sequence evolution and their applications. Current Opinions in Genetics& Development,, 10(6): 602--605.

[166]

E. Tillier and T. Lui. 2003. Using multiple interdependency to separate functional from phylogenetic correlations in protein alignments. Bioinformatics, 19(6): 750--755. 371

[167]

E. Tillier, L. Biro, G. Li, and D. Tillo. 2006. Codep: maximizing co-evolutionary inter-dependencies to discover interacting proteins. Proteins, 63(4): 822--831. 371

[168]

I. Tinoco, O. Uhlenbeck, and M. Levine. 1971. Estimation of secondary structure in ribonucleic acids. Nature, 230: 363--367. 388

[169]

N. Tran and C. Baral. 2007. Reasoning about non-immediate triggers in biological networks. Annals of Mathematics and Artificial Intelligence, 51(2--4): 267--293. 403

Digital Library

[170]

N. Tran and C. Baral. 2009. Hypothesizing about signaling networks. Journal of Applied Logic, 7(3): 253--274. 403

[171]

N. Tran, C. Baral, V. J. Nagaraj, and L. Joshi. 2005. Knowledge-based integrative framework for hypothesis formation in biochemical networks. In B. Ludäscher and L. Raschid, editors, DILS, vol. 3615 of Lecture Notes in Computer Science, pp. 121--136. Springer. 403

Digital Library

[172]

M. Truszczyński. 2007. Logic programming for knowledge representation. In V. Dahl and I. Niemelä, editors, Logic Programming, 23rd International Conference, ICLP 2007, pp. 76--88. 368

Digital Library

[173]

M. Truszczynski. 2018. An Introduction to the Stable and the Well-Founded Semantics of Logic Programs. In M. Kifer and A. Liu, editors, Declarative Logic Programming: Theory, Systems, and Applications. ACM.

Digital Library

[174]

M. Turcotte, S. Muggleton, and M. J. E. Sternberg. 2000. Use of inductive logic programming to learn principles of protein structure. Electronic Transactions of Artificial Intelligence, 4(B): 119--124. 405

[175]

M. Turcotte, S. Muggleton, and M. J. E. Sternberg. 2002. Generating protein three-dimensional fold signatures using inductive logic programming. Computers & Chemistry, 26(1): 57--64. 405

[176]

P. Veber, M. Le Borgne, A. Siegel, S. Lagarrigue, and O. Radulescu. 2006. Complex qualitative models in biology: A new approach. Complexus, 2(3--4): 140--151. 396

[177]

L. Wang and Y. Xu. 2003. Haplotype inference by maximum parsimony. Bioinformatics, 19(14): 1773--1780. 384

[178]

Web references of ASP solvers, 2018. Clasp: potassco.sourceforge.net; Cmodels: www.cs.utexas.edu/users/tag/cmodels; DLV: www.dbai.tuwien.ac.at/proj/dlv; Smodels: www.tcs.hut.fi/Software/smodels. 368

[179]

C. Woese and N. Pace. 1993. Probing RNA Structure, Function, and History by Comparative Analysis. In The RNA World, pp. 91--117. Cold Spring Harbor Laboratory Press. 370

[180]

G. Wu, J. You, and G. Lin. 2007. Quartet-based phylogeny reconstruction with answer set programming. IEEE/ACM Transactions on Computational Biology and Bioinformatics,, 4(1): 139--152. 378

Digital Library

[181]

X. Xia. 2007. Bioinformatics and the Cell: Modern Computational Approaches in Genomics, Proteomics and Transcriptomics. Springer. 360

[182]

Y. Zhao, Y. Xu, Q. Zhang, and G. Chen. 2007. An overview of the haplotype problems and algorithms. Frontiers of Computer Science in China, 1(3): 272--282. 384

[183]

M. Zuker and P. Stiegler. 1981. Optimal computer folding of large RNA sequences using thermodynamics and auxiliary information. Nucleic Acid Research, 9(1): 133--148. 388

Cited By

Czerniachowska KLutosławski K(2024)Optimising order picking efficiency in a warehouse and distribution centreProcedia Computer Science10.1016/j.procs.2023.10.070225:C(832-841)Online publication date: 4-Mar-2024
https://dl.acm.org/doi/10.1016/j.procs.2023.10.070
Nadia L(2023)Using Artificial Intelligence for Flexible Job Shop Scheduling Problem Solving2023 Third International Conference on Theoretical and Applicative Aspects of Computer Science (ICTAACS)10.1109/ICTAACS60400.2023.10449588(1-9)Online publication date: 5-Dec-2023
https://doi.org/10.1109/ICTAACS60400.2023.10449588
Dal Palù ADovier AFormisano APontelli E(2023)Prolog Meets BiologyProlog: The Next 50 Years10.1007/978-3-031-35254-6_26(318-333)Online publication date: 17-Jun-2023
https://doi.org/10.1007/978-3-031-35254-6_26
Show More Cited By

Exploring life: answer set programming in bioinformatics

Recommendations

Computing Life's Family Tree

Call it yet another biological gold rush. When Charles Darwin published The Origin of Species in 1859, scientists began working in earnest to document the world's plant and animal species and build a phylogeny—a map of how all those species relate to ...
Exploring single-sample SNP and INDEL calling with whole-genome de novo assembly

Motivation: Eugene Myers in his string graph paper suggested that in a string graph or equivalently a unitig graph, any path spells a valid assembly. As a string/unitig graph also encodes every valid assembly of reads, such a graph, provided that it can ...
On exploring genome rearrangement phylogenetic patterns
RECOMB-CG'10: Proceedings of the 2010 international conference on Comparative genomics

The study of genome rearrangement is much harder than the corresponding problems on DNA and protein sequences, because of the occurrences of numerous combinatorial structures. By explicitly exploring these combinatorial structures, the recently ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Books

Declarative Logic Programming: Theory, Systems, and Applications

September 2018

615 pages

ISBN:9781970001990

DOI:10.1145/3191315

Editors:
Michael Kifer
Stony Brook University
,
Yanhong Annie Liu
Stony Brook University

Publisher

Association for Computing Machinery and Morgan & Claypool

Publication History

Published: 01 September 2018

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Chapter

Appears in

ACM Books

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
57
Total Downloads

Downloads (Last 12 months)3
Downloads (Last 6 weeks)1

Reflects downloads up to 14 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Czerniachowska KLutosławski K(2024)Optimising order picking efficiency in a warehouse and distribution centreProcedia Computer Science10.1016/j.procs.2023.10.070225:C(832-841)Online publication date: 4-Mar-2024
https://dl.acm.org/doi/10.1016/j.procs.2023.10.070
Nadia L(2023)Using Artificial Intelligence for Flexible Job Shop Scheduling Problem Solving2023 Third International Conference on Theoretical and Applicative Aspects of Computer Science (ICTAACS)10.1109/ICTAACS60400.2023.10449588(1-9)Online publication date: 5-Dec-2023
https://doi.org/10.1109/ICTAACS60400.2023.10449588
Dal Palù ADovier AFormisano APontelli E(2023)Prolog Meets BiologyProlog: The Next 50 Years10.1007/978-3-031-35254-6_26(318-333)Online publication date: 17-Jun-2023
https://doi.org/10.1007/978-3-031-35254-6_26
Dal Palù ADovier AFormisano APontelli E(2018)ASP Applications in Bio-informatics: A Short TourKI - Künstliche Intelligenz10.1007/s13218-018-0551-y32:2-3(157-164)Online publication date: 18-Jun-2018
https://doi.org/10.1007/s13218-018-0551-y

View Options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Chapter

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents