Topics in Modelling, Simulation and Optimization

Project Ideas

1. Criticality in NP-Complete Problems. This project will go a little deeper in the analysis of NP-complete problems for their criticality behavior, starting with SAT. Recall that the paper on SAT showed that hard problems emerge at an optimal variable-to-clause ratio. The measure used was the number of recursive calls in the DP algorithm. In this project, you should examine the pattern of calls as they relate to changes in the variable values during backtracking. The conjecture is that, in hard problems, there should be cascades of change that cause the problem hardness. This project will examine these cascades in detail for both SAT and some other NP-complete problem.

2. The value of degradation in Boolean network models. The paper by C.Tang et al describes a unique B-net model for the cell cycle. It is unique in that some nodes in the network are made to "degrade" without external input. As it turns out, this is a key part of the model. This project will explore the general use of such automatic degradation in Boolean networks. The issues here are:
   • Key question: do B-nets with degradation behave in a fundamentally different manner than B-nets without?
   • How does one systematically study this question? By generating large numbers of random networks? Or enumerating all possible small networks?
   • How do the attractor-basin portraits differ across the two types? Do both types have the "highway" feature described in the paper? Do cycle-length or path-to-attractor lengths differ substantially?

3. Evolving Boolean networks to perform computations. Just as the papers by Crutchfield et al evolved 1D cellular automata to perform computations, this project will explore the evolution of Boolean networks (B-nets) to perform computations. There are several issues to investigate:
   • What is a reasonable definition of a Boolean network to perform a computation? In the case of a 1D CA, the final configuration was interpreted as the computation result. Can we do that for a B-net? Or should we associate "actions" with the states so that there is some output.
   • What computations are worth investigating. For example, can a B-net be evolved to perform sorting?
   • How do we generate random B-nets for the initial population? What mutation/crossover operators should be used?
   • What is the complexity of the resulting B-net? How does one quantify this?
   • What is the attractor-basin portrait of the resulting B-net? How is it different from the ones that failed?
   • Is there critical phase-transition like behavior observable?

4. Robustness in molecular networks. The paper by Barkai and Leibler is a classic in network dynamics. It postulates that some kinds of network behavior are robust in the space of parameters, i.e., that changes in parameter result in the same behavior. This project will study the Barkai-Leibler model and explore simplifying it further, and also to see whether adding network components fundamentally affects its robustness. This project will require some computation with ODE's; if you've never done that before, I can help you get started.

5. Tool for systematically studying biochemical reactions. How can one design a canonical ordering of systems of biochemical networks? This project will develop a tool to perform such enumerations and to study network dynamics using this tool. This project will require some computation with ODE's; if you've never done that before, I can help you get started.

6. Do network structures exhibit the HOT property? This project will explore what we summarized in class after the papers on HOT. Recall that in the forest fire example, there were two parameters, p and q that determined the system (natural or HOT). The yield was defined as the number of unburnt (surviving trees). The following are some possibilities for networks:
   • The yield analogy in a network is the connectivity: the number of node pairs that are connected.
   • Here's one idea to simulate growth and destruction. Start with a random network. Then p is the growth parameter in that links are added between nodes with probability p. Similarly, q, the "destruction" parameter, can be the probability that a node is destroyed.
   • To study a designed system (for HOT behavior), use the genetic algorithm to evolve networks to perform well in terms of yield. What would be the equivalent of firewalls? One approach is to simply let the network structure evolve without any firewalls. Another approach may be the addition of expensive backup links.
   • The goal is to study the resulting network structures to see if any patterns emerge. For example, do they have the small-world or power-law properties?