Modeling reaction pathways

• US 20030154003A1
• Filed: 01/23/2002
• Published: 08/14/2003
• Est. Priority Date: 01/23/2002
• Status: Active Grant

• Current Assignee: SRI International, Inc.
• Original Assignee: SRI International, Inc.
• Inventors: Lincoln, Patrick Denis, Eker, Steven Mark
• Granted Patent: US 7,308,363 B2
• Time in Patent Office: Days
• US Class Current: 700/266
• CPC Class Codes: G16B 5/00 ICT specially adapted for modelling or simulations in systems biology, e.g. gene-regulatory networks, protein interaction networks or metabolic networks
• CPC Class Codes: G16B 5/10 Boolean models

Abstract

Biological and chemical systems are represented as a symbolic model. Minimal sets of elements of the system are identified from the model, for example, by automatic inference. The model can be constructed from Boolean propositions that are mapped to a binary decision diagram. The model can also be probed using a branch and bound algorithm.

Claims

1. A method comprising:

generating a symbolic model that represents a network comprising chemical reactions; and

evaluating the symbolic model to identify a set of precursor compounds and/or chemical reactions that are sufficient to produce a set of target compounds or a set of precursor compounds and/or chemical reactions that are insufficient to produce the set of target compounds.

2. The method of claim 1 in which the identified set is a minimal set.

3. The method of claim 1 in which a plurality of sets that are sufficient are identified.

4. The method of claim 1 in which any arbitrary number of, up to and including all sets that are sufficient are identified.

5. The method of claim 1 further comprising, prior to the evaluating, reducing the number of elements in the model.

6. The method of claim 5 wherein said reducing comprises one or more of the following:

Bootstrap elimination, impossible rule deletion, needed compound elimination, factoring by equivalences, simplifying LHS/RHS overlaps, LHS subsumption, useless compound elimination, and reaction combination.

7. The method of claim 1 wherein the symbolic model comprises a Boolean function that returns a predetermined value if the set of target compounds is produced.

8. The method of claim 7 further comprising expressing the Boolean function in if-then-else normal form.

9. The method of claim 8 further comprising mapping each if-then-else expression of the set to a diagram of nodes, wherein each node of the diagram maps to an expression of the set of if-then-else expressions, depends on a Boolean variable associated with the expression and is directionally connected to two lower nodes in accordance with relationships implied by the expression, wherein each of the two lower nodes is either a node that maps to another expression of the set or a terminal node, and

wherein the evaluating comprises identifying a path from a node of the diagram that is not a lower node of any other node to one of the terminal nodes of the diagram.

10. The method of claim 9 wherein the path is a least-cost path.

11. The method of claim 1 in which the network comprises at least 100 chemical reactions.

12. A method comprising:

representing a network of chemical reactions as a symbolic model, the model comprising elements that include compounds and reactant-product relationships between compounds;

determining a Boolean function from the symbolic model, wherein the Boolean function returns a predetermined value if the network produces a set of target compounds; and

evaluating the Boolean function to identify a set of precursor compounds and/or relationships that is sufficient to produce the set of target compounds and/or a set of precursor compounds and/or chemical reactions that are insufficient to produce the set of target compounds.

13. The method of claim 12 in which the model comprises at least 100 elements.

14. The method of claim 12 further comprising reducing the number of elements of the model.

15. The method of claim 12 in which the evaluating comprises finding one or more implicants and/or implicates of the Boolean function.

16. The method of claim 15 in which the evaluating comprises finding one or more prime implicants and/or prime implicates of the Boolean function.

17. The method of claim 16 in which the evaluating comprises finding any number up to and including all prime implicants and/or prime implicates of the Boolean function.

18. The method of claim 12 in which the evaluating comprises use of a binary decision diagram.

19. The method of claim 12 in which the evaluating comprises use of a branch-and-bound algorithm.

20. The method of claim 12 in which the evaluating comprises use of a fixed point method.

21. The method of claim 12 in which the model is transformed and the evaluating comprises evaluating a Boolean function determined from the transformed model.

22. The method of claim 21 in which the evaluating identifies a set of relationships that is sufficient to produce the set of target compounds or a set of relationships that is insufficient to produce the set of target compounds.

23. An article of machine-readable media having encoded thereon software configured to cause a processor to:

store a symbolic model of a network of chemical reactions, the model comprising elements that include compounds and reactant-product relationships between compounds;

determine a Boolean function from the symbolic model, wherein the Boolean function returns a predetermined value if the network produces a set of target compounds; and

evaluate the Boolean function to identify a set of precursor compounds and/or relationships that is sufficient to produce the set of target compounds and/or a set of precursor compounds and/or chemical reactions that are insufficient to produce the set of target compounds.

24. The article of claim 23 wherein the software is further configured to cause the processor to receive information about the network of chemical reactions and generate the stored symbolic model.

25. A method comprising:

representing a network of chemical reactions as a symbolic model, the model comprising elements that include compounds and reactant-product relationships between compounds;

reducing the number of elements in the model; and

evaluating the model to identify a set of precursor compounds and/or relationships that is sufficient to produce the set of target compounds and/or a set of precursor compounds and/or chemical reactions that are insufficient to produce the set of target compounds.

26. The method of claim 25 in which the reducing comprises reducing compounds.

27. The method of claim 25 in which the reducing comprises reducing relationships.

28. The method of claim 26 in which the reducing comprises reducing relationships.

29. The method of claim 25 in which the reducing comprises one or more of the following:

Bootstrap elimination, impossible rule deletion, needed compound elimination, factoring by equivalences, simplifying LHS/RHS overlaps, LHS subsumption, useless compound elimination, and reaction combination.

30. The method of claim 25 in which the reducing comprises iteratively removing elements of the model.

31. The method of claim 25 in which the reducing comprises transforming the model, and the evaluating comprises identifying a solution for the transformed model and transforming the solution to identify the set of precursor compounds and/or relationships that is sufficient to produce the set of target compounds.

32. An article of machine-readable media having encoded thereon software configured to cause a processor to:

reduce number of elements of a symbolic model of a network of chemical reactions, the elements include compounds and reactant-product relationships between compounds; and

evaluate the model to identify a set of precursor compounds and/or relationships that is sufficient to produce a set of target compounds and/or a set of precursor compounds and/or chemical reactions that are insufficient to produce the set of target compounds.

33. A method comprising:

representing a network of chemical reactions as a symbolic model, the model comprising elements, at least some of the elements representing compounds, and at least some elements representing reactant-product relationships between compounds; and

automatically deducing from the model a set of the elements that determine a production state of the network.

34. The method of claim 33 in which the deduced set has a reduced number of elements relative to number of elements in the model.

35. The method of claim 33 in which the deduced set is a minimal set.

36. The method of claim 35 in which any arbitrary number of, up to and including all, minimal sets of elements are deduced.

37. The method of claim 33 in which the deduced set comprises compounds that are reactants.

38. The method of claim 37 in which the deduced set comprises compounds that are precursor compounds.

39. The method of claim 38 in which the deduced set comprises compounds that are transportable compounds.

40. The method of claim 33 in which the deduced set comprises reactant-product relationships.

41. The method of claim 33 in which the deduced set includes only reactant-product relationships or only compounds.

42. The method of claim 33 in which the production state is such that one or a set of target compounds is produced.

43. The method of claim 42 in which the production state is such that a set of target compounds is produced, and the target compounds comprise compounds essential for viability of a living cell.

44. The method of claim 33 in which the production state is such that at least one target compound is not produced.

45. The method of claim 33 in which the production state is such that each compound of a set of target compounds is not produced.

46. The method of claim 33 in which the model comprises a Boolean proposition.

47. The method of claim 33 in which the model comprises a monotone Boolean function.

48. The method of claim 46 in which the propositions are mapped to a binary decision diagram.

49. The method of claim 33 in which the model comprises a Boolean function that depends on variables, each variable indicating a presence of a precursor compound, and the function returning a predetermined value for every case in which a set of target compounds can be formed from the precursor compound.

50. The method of claim 33 in which the deducing comprises transforming the model to a second model.

51. The method of claim 50 in which the second model contains a reduced number of relationships or a reduced number of reactants relative to the model before transformation.

52. The method of claim 50 in which the transforming comprises one or more of the following:

Bootstrap elimination, impossible rule deletion, needed compound elimination, factoring by equivalences, simplifying LHS/RHS overlaps, LHS subsumption, useless compound elimination, and reaction combination.

53. The method of claim 50 in which the second model enables determining of a set of compounds that indicate a set of relationships that determine a production state of the network.

54. The method of claim 50 in which the reactants further comprise bootstrap compounds.

55. The method of claim 33 in which the deducing comprises transforming the model to a second model that comprises relationships between reactants and products, wherein the reactants do not include any of the bootstrap compounds.

56. The method of claim 33 in which at least one of the reactants or products is a metabolite.

57. The method of claim 33 in which at least one of the reactant comprises an RNA molecule.

58. The method of claim 57 in which at the RNA molecule is catalytic.

59. The method of claim 33 in which at least one of the reactants comprises an enzyme.

60. The method of claim 33 in which at least one of the reactants comprises a toxic, therapeutic, or pathogenic agent.

61. The method of claim 33 in which at least one of the reactants comprises a chromatin component.

62. The method of claim 33 in which the reactant-product relationships comprise a relationship at least between a reactant that is a gene and a product that is a polypeptide encoded by the gene.

63. The method of claim 33 in which the reactant-product relationships comprise a relationship at least between a reactant that is a polypeptide and a product that is a modified form of the polypeptide.

64. The method of claim 63 in which the modified form comprises a phosphorylated, proteolyzed, glycosylated, methylated, or ubiquitinated form.

65. The method of claim 63 in which the polypeptide is a signaling polypeptide.

66. The method of claim 33 in which at least some elements of the deduced set are associated with a cost and the deducing further comprises identifying a least-cost set of elements.

67. The method of claim 39 further comprising formulating a medium for growth of the living cell such that the medium comprises all of the transportable compounds of the deduced set.

68. The method of claim 39 further comprising formulating a medium for growth of the living cell such that the medium consists of each transportable compound of the deduced set less one of the compounds of the deduced set.

69. The method of claim 67 further comprising cultivating the living cell in the medium.

70. The method of claim 42 in which the target compounds comprise a modified protein that is required for a cell behavior.

71. The method of claim 70 in which the cell behavior comprises cell proliferation, cell motility, or apoptosis.

72. A machine-accessible medium, which, when accessed, results in a digital data processing system performing operations comprising:

from a model that represents a network of chemical reactions as a symbolic model and comprises elements, at least some of the elements representing compounds, and at least some elements representing reactant-product relationships between compounds, deducing a set of the elements that determine a production state of the network.

73. A computer-readable medium having stored thereon one or more sequences of instructions for causing a digital data processing system to perform operations comprising:

storing information representing a symbolic model of a chemical reaction network, the model comprising elements, at least some of the elements representing compounds, and at least some elements representing reactant-product relationships between compounds; and

automatically deducing from the model a set of the elements that determine a production state of the network.

74. A method comprising:

representing each of a first and a second networks of chemical reactions as a symbolic model, each model comprising a plurality of elements; and

deriving from the model a minimal set of elements of the first network that is not a minimal set of elements of the second network with respect to whether the first and second networks satisfy a given condition.

75. The method of claim 74 in which any arbitrary number up to and including all sets of elements of the first network that are not minimal sets of elements of the second network are derived.

76. The method of claim 74 in which the deriving comprises comparing a set of minimal sets of elements of the first network to a set of minimal elements of the second network.

77. The method of claim 74 in which the deriving comprises logically deducing.

78. The method of claim 74 in which the first network of chemical reactions represents chemical reactions in a first living cell, and the second network of chemical reactions represents chemical reactions in a second living cell.

79. The method of claim 78 in which the chemical reactions map reactants to products, and at least some of the reactants comprise transportable compounds.

80. The method of claim 78 in which the chemical reactions comprises intracellular reactions.

81. The method of claim 78 in which the given condition comprises production or non-production of a complete set of products essential for the viability of the first and/or second living cell.

82. The method of claim 78 in which the plurality of elements comprise transportable compounds, and the deriving comprises deriving a minimal set of transportable compounds such that when any one or more transportable compounds of the minimal set are withheld, the first network does not produce a complete set of essential products for the viability of the first living cell, but the second network does produce a complete set of essential products for the viability of the second living cell.

83. The method of claim 78 in which the plurality of elements comprise transportable compounds, and the deriving comprises deriving a minimal set of transportable compounds such that when each transportable compound of the set is withheld, the first network does not produce a complete set of essential products for the viability of the first living cell, but the second network does produce a complete set of essential products for the viability of the second living cell.

84. The method of claim 82 further comprising culturing the first and/or second living cell under culture conditions in which one or more compounds of the minimal set of transportable compounds is withheld.

85. The method of claim 78 in which the plurality of elements comprises chemical reactions, and the deriving comprises deriving a minimal set of chemical reactions that when any one or more chemical reactions of the minimal set is blocked, the first network does not produce a complete set of essential products for the viability of the first living cell, but the second network produces a complete set of essential products for the viability of the second living cell.

86. The method of claim 78 in which the plurality of elements comprises chemical reactions, and the deriving comprises deriving a minimal set of chemical reactions that when each chemical reactions of the minimal set is blocked, the first network does not produce a complete set of essential products for the viability of the first living cell, but the second network produces a complete set of essential products for the viability of the second living cell.

87. The method of claim 85 further comprising cultivating the first and/or second living cell in the presence of an inhibitor, the inhibitor blocking a chemical reaction of the minimal set of chemical reactions.

88. The method of claim 78 in which the first living cell is a pathogen.

89. The method of claim 88 in which the second living cell is a host cell.

90. The method of claim 78 in which the first living cell is a mammalian cell.

91. The method of claim 90 in which the first living cell is a diseased mammalian cell.

92. The method of claim 91 in which the first living cell is a diseased mammalian cell having an aberrant proliferative or abnormal differentiative state.

93. The method of claim 92 in which the first living cell is a cancer cell.

94. The method of claim 78 in which the second living cell is a mammalian cell.

95. The method of claim 92 in which the second living cell is a mammalian cell having a normal proliferative and normal differentiative state.

96. The method of claim 78 in which the deducing comprises identifying at least first and second Boolean functions, the first Boolean function expressing relationships between elements in the first network, and the second Boolean function expressing relationships between elements in the second network.

97. The method of claim 74 further comprising:

representing a third network of chemical reactions as a symbolic model; and

deriving from the model a minimal set of elements of the first network that is not a minimal set of elements of the second or third networks with respect to whether the first, second, and third networks satisfy a given condition.

98. A machine-based method comprising:

expressing relationships between compounds, the relationships representing chemical reactions and the compounds including precursor compounds and target compounds; and

identifying any arbitrary number of, up to and including all, minimal sets of elements, each set being sufficient or required for production of the target compounds.

99. A method comprising:

inferring a Boolean function from a chemical reaction network that includes relationships between compounds, the relationships representing chemical reactions and the compounds including precursor compounds and target compounds,

wherein the Boolean function depends on variables, each variable indicates a presence of one of the precursor compounds, and the function returns a predetermined value for every case in which the target compounds can be formed from the precursor compounds.

100. The method of claim 99 further comprising identifying a prime implicant or prime implicate of the Boolean function.

101. The method of claim 100 further comprising identifying any arbitrary number, up to and including all prime implicants or prime implicates of the Boolean function.

102. The method of claim 99 further comprising transforming the Boolean function into a binary decision diagram.

103. The method of claim 99 in which inferring comprises recursively constructing a symbolic representation of the Boolean function from the relationships.

104. The method of claim 103 in which the symbolic representation comprises nodes, each node corresponding to a variable.

105. An article of machine-readable media having encoded thereon information representing a Boolean function that represents a chemical reaction network that includes relationships between compounds, the relationships representing chemical reactions and the compounds including precursor compounds and target compounds, wherein the Boolean function depends on variables, each variable indicates a presence of one of the precursor compounds, and the function returns a predetermined value for every case in which the target compounds can be formed from the precursor compounds.

106. A machine-accessible medium, which when accessed results in a digital data processing system performing operations comprising:

storing a Boolean function that represents model of a chemical reaction network that includes relationships between compounds, the relationships representing chemical reactions and the compounds including precursor compounds and target compounds, wherein the Boolean function depends on variables, each variable indicates a presence of one of the precursor compounds, and the function returns a predetermined value for every case in which the target compounds can be formed from the precursor compounds, and

identifying an implicate or implicant of the Boolean function.

107. A method comprising:

defining a Boolean function that models a chemical reaction network, returns a predetermined value if each of a first group of network elements is in a defined state, and depends on variables hat each describe a state of an element from a second group of network elements; and

comparing variables from first sets of variables to infer a second set of variables, each first set of variables being a minimal set that returns the predetermined value for the function, the second set of variables being a set that returns the predetermined value for the function and differs from each first set of variables.

108. The method of claim 107 in which the comparing comprises a branch and bound algorithm.

109. The method of claim 107 further comprising minimizing the second set of variables by iteratively testing each variable of the second set to determine if it is required for the function to return the predetermined value.

110. The method of claim 109 in which a variable is discarded from the second set after it is tested and before another variable of the second set is tested.

111. The method of claim 107 in which comparing variables from the first sets comprises:

identifying a third set of variables, each variable of the third set being true if the variable is true in at least one of the first sets; and

inferring the second set of variables by negating the third set of variables.