This post is the notes for Mithani et al. (2009).
- Most current research in network evolution: Duplication Attachment model where the network is only allowed to grow.
- The evolution of metabolic networks is characterized by gain as well as loss of reactions.
- Describe metabolic network evolution as a discrete space continuous time Markov process;
- Introduce a neighbor-dependent model for the evolution of metabolic networks where the fraction of neighboring reactions present in the network.
- Present a Gibbs sampler for estimating the parameters of evolution without exploring the whole seach space by iteratively sampling from the conditional distributions of the paths and parameters.
- A number of models to study evolution of biological networks.
- The evolution of metabolic networks is characterized by gain and loss of reactions (or enzymes) connecting two or more metabolites.
- Most of the current research focuses on Duplication Attachment model (new nodes and edges are probabilistically added depending on a set of parameters, NOT allow deletions of nodes or edges)
- Current models represent networks as directed or undirected graphs where nodes represent biological entities (proteins or metabolites), and the presence of an edge between two nodes indicates the presence of some sort of relation between the nodes. Drawback: cannot capture the relationships between more than two nodes, e.g, multiple metabolites in a reaction.
- discrete space continuous time Markov process allowing both insertion and deletion of reactions.
- represent metabolic networks as directed hypergraphs, loss or gain of reactions can be regarded as loss or gain of hyperedges.
- neighbor-dependent model where the rates with which reactions are added or removed depend on the fraction of neighboring reactions present in the network, two actions are considered to be neighbors if they share at least one metabolite.
- the likelihood of evolution from one network to another for fixed parameter values can be calculated by integrating over the paths between the two networks.
- Metropolis-Hastings algorithm: approximate the likehood of evolution by summing over the unique paths visited by the sampler.
- Gibbs sampler estimates the parameters without exploring the whole search space by iteratively sampling from the conditional distributions of the paths and parameters.
- fix the number of nodes $N$
- a set of hyperedges $\cal \epsilon$
- reference network, assuming that hyperedges in the reference network are labeled $1$ to $M$
- a reversible reaction is represented by two hyperedges. The total number of hyperedge $M$ in a metabolic network then corresponds to $R$ reactions out of which $K$ are reversible, i.e $M=R+K$.
- consider a metabolic network represented as a hypergraph. At each step of the network evolution, an hyperedge is either added or deleted until the desired network is obtained. Modeling network evolution as a Markov process implies that the future dynamics of the system is determined by the current state of the network where a state is defined as the current configuration of the network
- The waiting time between the events are exponentially distributed and the average waiting time of the network before an insertion or deletion event takes place is a function of the entire network and depends on the number of edges that can be inserted or deleted from the network and the rates at which hyperedges can be changed.
- core and prohibited hyperedges. core edges: hyperedges that cannot be deleted during the course of evolution, and prohibited edges, hyperedges that cannot be added to a network.
- Independent edge model. problem: the reactions in metabolic networks do not evolve independently.
- Neighbor-dependent model: hyperedge are inserted or deleted depending on their neighbors.
- event: the addition or deletion of an edge, and define a path between two networks as a sequence of events that thansform the first network into the second.
- Likelihood calculation: Metroplis-Hastings algorithm (for given parameter values)
- Parameter estimation: Gibbs sampler
- We can estimate the parameters of evolution between different pairs of bacteria and can use network structure to provide clues about the metabolic similarity of bacteria.
- A logical extension to the work presented here would be to calculate the likelihood and estimate the parameters over a phylogeny, which is known through sequence analysis.
- network: $x$
- number of hyperedge: $M$
- neighboring hyperedges: $\Phi(x_i)$
- rate matrix: $\Gamma$
- neighborhood component $F(x_i,\Phi(x_i))$
- hybrid model
- an edge was then selected based on these rates and was inserted if absent from the current network and deleted otherwise.
- evolution on a phylogeny
- sampling internal nodes
- can the allowed hyperedge reduce the dimensionality?
- sequence analysis–> SDA??