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.
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.
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.
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!
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.
> 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.
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.
Yep, they’re just next state equations with boolean states. It is indeed very general. The interesting bit is that they typically have lots of feedback loops, which leads to behavior that’s really difficult to predict.
Fascinating, then were model checkers successful at all for finding interesting properties and behaviors?
IIRC Petri Nets are strictly more powerful than register-transfer/Boolean state machines, intuitive reason being the Petri net tokens are a dynamic set of unbounded, concurrent counters (whereas a state machine has a fixed set of state variables equivalent to a single counter). I wonder if this paper explains this distinction as it argues one reduces to the other.
Yep, model checkers are one of the more powerful tools for working with Boolean models. You might find some of the work from Jasmine Fisher's lab interesting, especially when she was at Microsoft Research.
My take on model checking for Boolean networks is that they're too rigid and too difficult to program to answer the really interesting biological questions. My understanding is that they're great for exactly proving exact correctness, but can't tell you if your model is close but not exactly correct. Given the limits of biological data, the close but not perfect models are sometimes the best. Also, you really want to be able to ask weird questions sometimes. Like, how does this model behave if we apply a perturbation, or series of perturbations to it? What if we simulate the model in some weird, non-conventional way? Then configuring the model checker to give you information about that situation can be really difficult. Like PhD thesis level difficult.
That's why I have always just relied on brute-force simulations. Compute is cheap, my time is not (even as a grad student). Much easier to just submit a job to the cluster and wait a day then try to figure out how to get Z3 to do what I want.
Others will probably disagree.
Unfortunately, I'm not really familiar enough with Petri nets to comment on the relationship to boolean models.
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.
I recognize all of these words, but have no idea what they all mean together. Pretty wild.
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.
And in reverse, does this offer any way to speed up finding factors of boolean networks?
Thank you for the explanation!
Thank you!
This sounds so weird when you are not acquainted with these concepts... I first thought it was a fake AI-generated paper ;-)
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.
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!
Is your premise that everything can be accessible to everyone with no prior training or am I misunderstanding what you’re saying?
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.
why is it interesting?
> 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.
Why are trap spaces interesting?
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.
Wait so these Boolean models are just Boolean next-state functions of finite state machines? That seems very general then.
Yep, they’re just next state equations with boolean states. It is indeed very general. The interesting bit is that they typically have lots of feedback loops, which leads to behavior that’s really difficult to predict.
Fascinating, then were model checkers successful at all for finding interesting properties and behaviors?
IIRC Petri Nets are strictly more powerful than register-transfer/Boolean state machines, intuitive reason being the Petri net tokens are a dynamic set of unbounded, concurrent counters (whereas a state machine has a fixed set of state variables equivalent to a single counter). I wonder if this paper explains this distinction as it argues one reduces to the other.
Yep, model checkers are one of the more powerful tools for working with Boolean models. You might find some of the work from Jasmine Fisher's lab interesting, especially when she was at Microsoft Research.
My take on model checking for Boolean networks is that they're too rigid and too difficult to program to answer the really interesting biological questions. My understanding is that they're great for exactly proving exact correctness, but can't tell you if your model is close but not exactly correct. Given the limits of biological data, the close but not perfect models are sometimes the best. Also, you really want to be able to ask weird questions sometimes. Like, how does this model behave if we apply a perturbation, or series of perturbations to it? What if we simulate the model in some weird, non-conventional way? Then configuring the model checker to give you information about that situation can be really difficult. Like PhD thesis level difficult.
That's why I have always just relied on brute-force simulations. Compute is cheap, my time is not (even as a grad student). Much easier to just submit a job to the cluster and wait a day then try to figure out how to get Z3 to do what I want.
Others will probably disagree.
Unfortunately, I'm not really familiar enough with Petri nets to comment on the relationship to boolean models.
[dead]
[flagged]