Skip to content Skip to navigation Skip to collection information

Connexions

You are here: Home » Content » The Art of the PFUG » Cell Assemblies: A Binary Integer Programming Problem

Navigation

Table of Contents

Lenses

What is a lens?

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • Rice Digital Scholarship

    This collection is included in aLens by: Digital Scholarship at Rice University

    Click the "Rice Digital Scholarship" link to see all content affiliated with them.

Also in these lenses

  • Lens for Engineering

    This module and collection are included inLens: Lens for Engineering
    By: Sidney Burrus

    Click the "Lens for Engineering" link to see all content selected in this lens.

Recently Viewed

This feature requires Javascript to be enabled.
 

Cell Assemblies: A Binary Integer Programming Problem

Module by: Tyler Young, Steven J. Cox. E-mail the authors

Summary: This report summarizes work done as part of the Computational Neuroscience PFUG under Rice University's VIGRE program. VIGRE is a program of Vertically Integrated Grants for Research and Education in the Mathematical Sciences under the direction of the National Science Foundation. A PFUG is a group of Postdocs, Faculty, Undergraduates and Graduate students formed round the study of a common problem. This module reproduces the work G. Palm "Towards a Theory of Cell Assemblies". This work was studied in the Rice University VIGRE/REU program in the Summer of 2009.

Module Goal

  1. Provide biological motivation for finding cell assemblies in a network of neurons
  2. Understand how mathematics and graph theory can be used to locate cell assemblies in a neural network
  3. Understand how a minimal k-core can be used to find a k-assembly
  4. Learn how to use a bulit-in MATLAB function, bintprog, to aid in the finding of cell assemblies

Introduction

Ever since psychologists and neuroscientists began studying the physiological inner workings of the brain, they have been puzzled by many questions. How are concepts stored and recalled within our brains? How does learning and memory occur? In 1949, D.O. Hebb tried to explain the answers to these questions in terms of cell assemblies in his book The Organization of Behavior. Hebb asserts that a cell assembly is a group of neurons wired in a specific manner such that when a sufficient amount of neurons in this group become excited, the entire group becomes excited in a synchronized manner. Hebb went on to explain that these cell assemblies form via synaptic plasticity. He claims that if neuron A repeatedly fires neuron B, some metabolic activity occurs increasing the efficiency in which neuron A fires neuron B. This phenomenon is more commonly known as “cells that fire together, wire together.” Hebb postulates that the ignition of a series of these groups of neurons, or cell assemblies, can explain how concepts are stored and recalled within our brains, thus allowing learning and memory to occur.

Mathematics of Cell Assemblies

In 1989, G. Palm was the first mathematician to give a mathematical definition of cell assemblies in his article Towards a Theory of Cell Assemblies. By finding a connection between graph theory and Palm's mathematical definition of cell assemblies, we have found a method for translating Palm's mathematical definition of a cell assembly into a binary integer programming problem. This has allowed us to find at least one cell assembly in a network of neurons and also gives us hope for finding more cell assemblies in the same networks. If we let G be a graph with a set of vertices {vi:i=1,⋯,n}{vi:i=1,⋯,n} and a set of edges {wi:i=1,⋯,p}{wi:i=1,⋯,p}, we can take the following from Palm to help us locate a cell assembly in a network of neurons:

Adjacency Matrix (Ad)

An adjacency matrix(Ad) is a matrix of binary elements representing the connectivity of a given network of neurons such that if Ad(n,m)=1Ad(n,m)=1 there exists a connection between neurons n and m and conversely, if Ad(n,m)=0Ad(n,m)=0 then no connection exists between neurons n and m

Figure 1: Five neuron network and the given adjacency matrix
Figure 1 (Adjacency.png)

Threshold (k)

In undirected, unweighted graphs the threshold(k) is the minimum number of inputs a neuron needs in order to become excited

The excitation map, e(x,k)

  • let X be a subgraph in G:
    xi=1ifvi∈X0ifotherwisexi=1ifvi∈X0ifotherwise
    (1)
  • Where x is a binary vector representing the presence (1) or absence (0) of a neuron.
    ei(x,k)=1if(Adx)i≥k0ifotherwiseei(x,k)=1if(Adx)i≥k0ifotherwise
    (2)
  • x is an invariant set if:
    e(x,k)=xe(x,k)=x
    (3)

Graph Theory and Cell Assemblies

Using tools from graph theory, we are able to link a certain class of Palm's cell assemblies, which we will call a k-assembly, to the closure of a minimal k-core. Using MATLAB, we are able to find a minimal k-core and it's closure allowing us to find a k-assembly in any given network of neurons.

k-cores

k-cores are a concept in graph theory that has been widely used and studied by many graph theorists for locating cohesive subsets in a given graph. A k-core can be defined as:

  • Given graph G, subgraph X is a k-core if every node in X has at lease k neighbors in X. A k-core can be described as minimal if no proper subset of the k-core is also a k-core.
Figure 2: X={1,2,4}X={1,2,4} is a minimal 2-core
Figure 2 (kcore.png)

Algorithms for Finding a k-assembly

The closure (the invariant set generated by iterating the e map) of a minimal k-core is a k-assembly

  • One type of cell assembly, we will call a k-assembly, is the closure of a minimal k-core. In order to find these k-assemblies, we needed to develop a method for finding minimal k-cores and their closures in any given network of neurons.

Finding minimal k-cores:

bintprog is a built in MATLAB function that Þnds an optimal solution to binary integer programming problems of the following form:

min x f T x min x f T x
(4)
A x ≤ b A x ≤ b
(5)
x ∈ { 0 , 1 } n x ∈ { 0 , 1 } n
(6)

bintprog arguments:f,A,bf,A,b

  • f: coefficients of the variables of the objective functions
  • A,bA,b: Using the threshold inequality we can find A:
    Adx≥kx⟹0≥(kI-Ad)xAdx≥kx⟹0≥(kI-Ad)x
    (7)
    bintprog minimizes fTxfTx constrained to Ax≤bAx≤b. Because x=0 satisfies the inequality we must add an additional constraint
    x1+x2+...+xn≥1x1+x2+...+xn≥1
    (8)
    A=kI-Ad-1-1-1...A=kI-Ad-1-1-1...
    (9)
    b=000⋮0-1b=000⋮0-1
    (10)

Algorithm Examples

bintprog Example

  • Given the following graph, its corresponding adjacency matrix and threshold of k=2k=2, bintprog can find a minimal 2-core:
    Figure 3
    Figure 3 (bintprogG.png)
    Ad=010001101011010111001010011101111010Ad=010001101011010111001010011101111010
    (11)
  • bintprog arguments:
    f=111111A=2-1000-1-12-10-1-10-12-1-1-100-12-100-1-1-12-1-1-1-10-12-1-1-1-1-1-1b=000000-1f=111111A=2-1000-1-12-10-1-10-12-1-1-100-12-100-1-1-12-1-1-1-10-12-1-1-1-1-1-1b=000000-1
    (12)
  • bintprog returns a vector, x, indicating which nodes are in the minimal k-core:
    x=110001x=110001
    (13)
  • {1,2,6} is the minimal 2-core found by bintprog
  • There are, however, many other minimal k-cores in this set of neurons such as: {3,4,5} and {2,5,6}. Our goal for the future is to find some method that enables bintprog to find all of the minimal k-cores in a given network allowing us to find all of the k-assemblies in that network.

Closure Example

We will use the same graph as the previous bintprog example:

  1. Create a subset, x. We will use the minimal 2-core found by bintprog:
  2. Find e1(x,k)e1(x,k):
    010001101011010111001010011101111010110001=222022⟹e1(x,k)=111011010001101011010111001010011101111010110001=222022⟹e1(x,k)=111011
    (14)
    Because e1≠xe1≠x we must apply ei(x,k)ei(x,k) again:
    010001101011010111001010011101111010111011=243234⟹e2(x,k)=111111010001101011010111001010011101111010111011=243234⟹e2(x,k)=111111
    (15)
    Even though e2(x,k)≠xe2(x,k)≠x, we can see that because the entire graph is excited, it will keep exciting itself, thus generating an invariant set giving us a k-assembly:
    x=111111x=111111
    (16)

Finding k-assemblies

Figure 4: bintprog found a minimal 3-core {5,6,7,15}{5,6,7,15} in the 15 node graph and then finds that minimal 3-core's closure (a k-assembly).
Figure 4 (CellAssembly.png)

Future Work for Finding Cell Assemblies

In order to find more cell assemblies in any given network of neurons, we have come up with a few methods of finding other minimal k-cores in a network of neurons:

  • Alter the arguments of bintprog
    • We have altered with the coefficients of the objective function where we would increase the value for nodes already found in a previous minimal k-core. This method has, however, proved to be exhaustive in that we must increase the value of the objective coefficients with all possible combinations of nodes of the previously found minimal k-cores to ensure that all the minimal k-cores of any given graph are located.
  • Translate other graph theoretical algorithms to fit minimal k-cores
    • We hope to use algorithms in graph theory for finding other types of subgraphs, such as a maximal clique, and translate them to fit our problem of finding all of the minimal k-cores of any given graph.
  • Use probability in random graphs
    • Using probability may allow us to figure out how many minimal k-cores a given graph may support as well as where they might be, allowing us to constrain other exhaustive methods of finding minimal k-cores.

Conclusion

This module has shown how to translate the problem of finding cell assemblies in a network of neurons into a binary integer programming problem. It has shown a clear connection between cell assemblies and graph theory and also how to find at least one cell assembly in any given network of neurons. Future work for this problem includes how to find more cell assemblies in a network of neurons.

Acknowledgements

I would like to give a big thanks to Dr. Steve Cox and Dr. Illya Hicks for guiding us through our project of finding cell assemblies. Also thanks to the REU students, Karina Aliaga, Shaunak Das, and Diane Taylor who I collaborated with on this project. Lastly I would like to thank NSF and the VIGRE program for funding me under the NSF VIGRE Grant DMS-0240058.

References

1. Hebb, Donald. (1949) The Organization of Behavior. (New York: John Wiley).

2. Palm, Gunther. (1981) Towards a Theory of Cell Assemblies. Biological Cybernetics 39, pp. 181-194.

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

A lens is a custom view of the content in the repository. You can think of it as a fancy kind of list that will let you see content through the eyes of organizations and people you trust.

What is in a lens?

Lens makers point to materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

Who can create a lens?

Any individual member, a community, or a respected organization.

What are tags? tag icon

Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

| External bookmarks