4 ms·

Trap spaces of Boolean networks are conflict-free siphons of their Petri net [pdf]

39 points by luu 3y ago

jd116 3y ago
[dead]
ActionHank 3y ago
I recognize all of these words, but have no idea what they all mean together. Pretty wild.
- jd115 3y ago
  The paper explores the connection between two mathematical models used to study biological systems: Boolean networks and Petri nets. Boolean networks model gene regulation and other biological processes using logical functions. The long-term behavior of these models, represented by "attractors", corresponds to observable biological states. Recently, a concept called "trap spaces" has made analyzing larger Boolean network models feasible. However, computing trap spaces relies on finding prime implicants of the logical functions, which gets harder as models get bigger and more complex. (A prime implicant is a minimal set of conditions that ensures a Boolean function will be true. ) Petri nets are another type of model using places, transitions between places, and tokens to represent the state of a system. A key concept in Petri nets is a "siphon" - a set of places that once empty of tokens, remains empty. The authors prove for the first time that there is an equivalence between trap spaces in a Boolean network and "conflict-free siphons" in the corresponding Petri net representation. This connection allows properties of trap spaces to be studied using Petri net theory. It also enables a new approach to compute trap spaces by finding siphons in the Petri net, avoiding the hard prime implicant computation. In practical terms, this pushes the boundaries of the size and complexity of biological systems that can be effectively modeled and studied using this approach.
  - burnished 3y ago
    Thank you for the explanation!
  - ActionHank 3y ago
    Thank you!
  - tgv 3y ago
    And in reverse, does this offer any way to speed up finding factors of boolean networks?
gexaha 3y ago
why is it interesting?
- Sayrus 3y ago
  > Besides important theoretical applications in studying properties of trap spaces, the connection enables us to propose an alternative approach to compute minimal trap spaces, and hence complex attractors, of a general Boolean network. It replaces the need for prime implicants by a completely different technique, namely the enumeration of maximal siphons in the Petri net encoding of the original model. We then demonstrate its efficiency and compare it to the state-of-the-art methods on a large collection of real-world and randomly generated models.
  - 01HNNWZ0MV43FF 3y ago
    Why are trap spaces interesting?
    - bglazer 3y ago
      The most common use of Boolean models is simulating biological systems, i.e. genes and proteins interacting with each other. Trap spaces are the steady states of the model. So, if you start the model in a random state then you're guaranteed to see the model in one of the trap space states after a long enough amount of simulation time. That's interesting because it tells us the most likely behavior of the biological system. Suppose we're modeling cancer cells. They have a trap space that corresponds to activation of lots of genes that cause hyperactive growth. We'd like to know how to disrupt that system so that the trap space with hyperactive growth genes goes away, causing the cancer to stop growing.
      - calf 3y ago
        Wait so these Boolean models are just Boolean next-state functions of finite state machines? That seems very general then.
ale42 3y ago
This sounds so weird when you are not acquainted with these concepts... I first thought it was a fake AI-generated paper ;-)
andrewp123 3y ago
Always depressing to see a paper like this. I can almost guarantee one could make this whole thing into a two-page document with a clearer vision and followable to, well, anyone else. The purpose of academic papers is to file a claim to ownership of ideas / progress. But it would be cool if in another place they published the intuitions they used to come up with the claim in the first place.
- dullcrisp 3y ago
  Is your premise that everything can be accessible to everyone with no prior training or am I misunderstanding what you’re saying?
  - hwbehrens 3y ago
    I don't think that was the grandparent's premise, but I actually think that it's not unreasonable to expect experts to be able to boil down their ideas for non-experts. We know it must be possible, because they themselves arrived at that point in an abstract "graph of knowledge" starting from a blank slate at birth, so going the other direction is (at worst) merely backtracking that path. However, most experts know enough other nodes/edges in the graph to identify shortcuts from their conclusion back toward the 'beaten path' that most people would know. I often argue that if you aren't able to articulate the core idea of your research to someone outside your field, you might not understand it as well as you think you do. (Re: the grandparent) When communicating with the scientific community, however, it's not unreasonable to be as precise as possible to convey the idea accurately to fellow experts. Replacing scientific papers with blog posts is not a good solution; augmenting scientific papers with blog posts might be appropriate.
- barfbagginus 3y ago
  Boolean networks and petri nets have been important in biology since the 60s and 70s. If you don't know that history, there are thousands of papers and books to get you up to speed with the intuition and practice behind them. You should not be depressed when you meet a topic with a long history like this - the history is usually linked in the papers own bibliography. Get reading instead! You are wrong about what science papers are - they're more than just territory markers to claim ownership of ideas. They also explain the idea and get people interested in building on it and using it to create value for humanity. This paper is pretty simple and sweet, but it needs more than a couple pages to: 1. Define trap spaces and sketch their history and usefulness 2. Prove they're equivalent to conflict free siphons 3. Explore some ways to calculate siphons 4. Show that these ways all beat the pants off existing trap space methods This is all intuitive - and there are a bunch of references in the bibliography if you want to learn more. One reference is the author's earlier work, which should have more intuition, but less polish, than the current paper. We could criticize the work. The author clearly took their proof from an earlier paper, bolted some benchmarks onto it, and republished it. And unless we're experts, we have to trust the author included the best possible competing solutions in that benchmark. But assuming the author is honest, the benchmarks are impressive. It took serious work to implement their methods and build the benchmark. So it's hard to hate the author here for consolidating their win. To really criticize the paper - and see if it's as useful as the tests suggest - we'd want to run the experiment and verify the competing techniques represent the state of the art and were configured correctly. It would be fun! I encourage you to learn how to read science. Science does need our criticism and contribution, very much so. But before we can criticize it constructively, we must care about a specific topic, and educate ourselves as much as possible. It doesn't help humanity to give cookie cutter criticisms about papers we don't care about. Let's unleash criticism that gives true value to humanity, and extends what science can do!
bglazer 3y ago
The first paper I wrote in my PhD was about how we could use reinforcement learning to automatically find models that have trap space (attractor) behavior that matched experimental observations. A big bottle-neck in that process is figuring out what the actual attractor states of a model are. I resorted to just running simulations until the model reached a steady state, because its flexible and easy, but it's also prohibitively slow for models that are reasonably large. So, hopefully this paper will let us find the attractors of much larger Boolean models without having to run full simulations. That said, the whole experience convinced me that modeling biology with Boolean logic is a bad idea. First, you have to force biological data, which is weird and long-tailed and multi-modal into two logical buckets, on or off, zero or one. Biology just doesn't work like that, lots of genes have graded, gradual differences in expression, not just zero/one. Then, you have to actually build a Boolean model, but you never have enough data to properly constrain the model. There are probably hundreds of wildly different model configurations that all give you equivalent behavior. Which one is right? Who knows. Finally you run the simulations and you get the attractors or trap spaces, and you show your results to a wet lab biologist and they don't believe the results because the model is way too simple. Genes aren't just on or off, and interactions between genes don't work like Boolean logic. It's way better to just write down differential equations that describe the actual biophysical processes happening. With modern computers and solvers, ODE's are basically just as easy to simulate as a Boolean model, and they're much better representations of biology than Boolean logic.
HaHaHackerNews 3y ago
[flagged]

39 points by luu 3y ago

jd116 3y ago

[dead]

ActionHank 3y ago

I recognize all of these words, but have no idea what they all mean together. Pretty wild.

jd115 3y ago
The paper explores the connection between two mathematical models used to study biological systems: Boolean networks and Petri nets. Boolean networks model gene regulation and other biological processes using logical functions. The long-term behavior of these models, represented by "attractors", corresponds to observable biological states. Recently, a concept called "trap spaces" has made analyzing larger Boolean network models feasible. However, computing trap spaces relies on finding prime implicants of the logical functions, which gets harder as models get bigger and more complex. (A prime implicant is a minimal set of conditions that ensures a Boolean function will be true. ) Petri nets are another type of model using places, transitions between places, and tokens to represent the state of a system. A key concept in Petri nets is a "siphon" - a set of places that once empty of tokens, remains empty. The authors prove for the first time that there is an equivalence between trap spaces in a Boolean network and "conflict-free siphons" in the corresponding Petri net representation. This connection allows properties of trap spaces to be studied using Petri net theory. It also enables a new approach to compute trap spaces by finding siphons in the Petri net, avoiding the hard prime implicant computation. In practical terms, this pushes the boundaries of the size and complexity of biological systems that can be effectively modeled and studied using this approach.
- burnished 3y ago
  Thank you for the explanation!
- ActionHank 3y ago
  Thank you!
- tgv 3y ago
  And in reverse, does this offer any way to speed up finding factors of boolean networks?

gexaha 3y ago

why is it interesting?

Sayrus 3y ago
> Besides important theoretical applications in studying properties of trap spaces, the connection enables us to propose an alternative approach to compute minimal trap spaces, and hence complex attractors, of a general Boolean network. It replaces the need for prime implicants by a completely different technique, namely the enumeration of maximal siphons in the Petri net encoding of the original model. We then demonstrate its efficiency and compare it to the state-of-the-art methods on a large collection of real-world and randomly generated models.
- 01HNNWZ0MV43FF 3y ago
  Why are trap spaces interesting?
  - bglazer 3y ago
    The most common use of Boolean models is simulating biological systems, i.e. genes and proteins interacting with each other. Trap spaces are the steady states of the model. So, if you start the model in a random state then you're guaranteed to see the model in one of the trap space states after a long enough amount of simulation time. That's interesting because it tells us the most likely behavior of the biological system. Suppose we're modeling cancer cells. They have a trap space that corresponds to activation of lots of genes that cause hyperactive growth. We'd like to know how to disrupt that system so that the trap space with hyperactive growth genes goes away, causing the cancer to stop growing.
    - calf 3y ago
      Wait so these Boolean models are just Boolean next-state functions of finite state machines? That seems very general then.

ale42 3y ago

This sounds so weird when you are not acquainted with these concepts... I first thought it was a fake AI-generated paper ;-)

andrewp123 3y ago

Always depressing to see a paper like this. I can almost guarantee one could make this whole thing into a two-page document with a clearer vision and followable to, well, anyone else. The purpose of academic papers is to file a claim to ownership of ideas / progress. But it would be cool if in another place they published the intuitions they used to come up with the claim in the first place.

dullcrisp 3y ago
Is your premise that everything can be accessible to everyone with no prior training or am I misunderstanding what you’re saying?
- hwbehrens 3y ago
  I don't think that was the grandparent's premise, but I actually think that it's not unreasonable to expect experts to be able to boil down their ideas for non-experts. We know it must be possible, because they themselves arrived at that point in an abstract "graph of knowledge" starting from a blank slate at birth, so going the other direction is (at worst) merely backtracking that path. However, most experts know enough other nodes/edges in the graph to identify shortcuts from their conclusion back toward the 'beaten path' that most people would know. I often argue that if you aren't able to articulate the core idea of your research to someone outside your field, you might not understand it as well as you think you do. (Re: the grandparent) When communicating with the scientific community, however, it's not unreasonable to be as precise as possible to convey the idea accurately to fellow experts. Replacing scientific papers with blog posts is not a good solution; augmenting scientific papers with blog posts might be appropriate.
barfbagginus 3y ago
Boolean networks and petri nets have been important in biology since the 60s and 70s. If you don't know that history, there are thousands of papers and books to get you up to speed with the intuition and practice behind them. You should not be depressed when you meet a topic with a long history like this - the history is usually linked in the papers own bibliography. Get reading instead! You are wrong about what science papers are - they're more than just territory markers to claim ownership of ideas. They also explain the idea and get people interested in building on it and using it to create value for humanity. This paper is pretty simple and sweet, but it needs more than a couple pages to: 1. Define trap spaces and sketch their history and usefulness 2. Prove they're equivalent to conflict free siphons 3. Explore some ways to calculate siphons 4. Show that these ways all beat the pants off existing trap space methods This is all intuitive - and there are a bunch of references in the bibliography if you want to learn more. One reference is the author's earlier work, which should have more intuition, but less polish, than the current paper. We could criticize the work. The author clearly took their proof from an earlier paper, bolted some benchmarks onto it, and republished it. And unless we're experts, we have to trust the author included the best possible competing solutions in that benchmark. But assuming the author is honest, the benchmarks are impressive. It took serious work to implement their methods and build the benchmark. So it's hard to hate the author here for consolidating their win. To really criticize the paper - and see if it's as useful as the tests suggest - we'd want to run the experiment and verify the competing techniques represent the state of the art and were configured correctly. It would be fun! I encourage you to learn how to read science. Science does need our criticism and contribution, very much so. But before we can criticize it constructively, we must care about a specific topic, and educate ourselves as much as possible. It doesn't help humanity to give cookie cutter criticisms about papers we don't care about. Let's unleash criticism that gives true value to humanity, and extends what science can do!

bglazer 3y ago

The first paper I wrote in my PhD was about how we could use reinforcement learning to automatically find models that have trap space (attractor) behavior that matched experimental observations. A big bottle-neck in that process is figuring out what the actual attractor states of a model are. I resorted to just running simulations until the model reached a steady state, because its flexible and easy, but it's also prohibitively slow for models that are reasonably large. So, hopefully this paper will let us find the attractors of much larger Boolean models without having to run full simulations. That said, the whole experience convinced me that modeling biology with Boolean logic is a bad idea. First, you have to force biological data, which is weird and long-tailed and multi-modal into two logical buckets, on or off, zero or one. Biology just doesn't work like that, lots of genes have graded, gradual differences in expression, not just zero/one. Then, you have to actually build a Boolean model, but you never have enough data to properly constrain the model. There are probably hundreds of wildly different model configurations that all give you equivalent behavior. Which one is right? Who knows. Finally you run the simulations and you get the attractors or trap spaces, and you show your results to a wet lab biologist and they don't believe the results because the model is way too simple. Genes aren't just on or off, and interactions between genes don't work like Boolean logic. It's way better to just write down differential equations that describe the actual biophysical processes happening. With modern computers and solvers, ODE's are basically just as easy to simulate as a Boolean model, and they're much better representations of biology than Boolean logic.

HaHaHackerNews 3y ago

[flagged]