Systems and methods for inferring biological networks

• US 7,512,497 B2
• Filed: 08/29/2003
• Issued: 03/31/2009
• Est. Priority Date: 08/29/2002
• Status: Active Grant

• Current Assignee: Gene Network Sciences, Inc
• Original Assignee: Gene Network Sciences, Inc
• Inventors: Periwal, Vipul
• Primary Examiner(s): Zeman; Mary K
• Application Number:
  US10/652,910
• Publication Number:
  US 20040243354A1
• Time in Patent Office: 2,041 Days
• Field of Search: None
• US Class Current: 702/19
• CPC Class Codes: G01N 2333/4739 Cyclin; Prad 1
• CPC Class Codes: G01N 33/5091 for testing the pathological state of an organism
• CPC Class Codes: G16B 40/00 ICT specially adapted for biostatistics; ICT specially adapted for bioinformatics-related machine learning or data mining, e.g. knowledge discovery or pattern finding
• CPC Class Codes: G16B 5/00 ICT specially adapted for modelling or simulations in systems biology, e.g. gene-regulatory networks, protein interaction networks or metabolic networks
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

Described herein is a system for inferring one or a population of biochemical interaction networks, including topology and chemical reaction rates and parameters, from dynamical or statical experimental data, with or without spatial localization information, and a database of possible interactions. Accordingly, the systems and methods described herein may be employed to infer the biochemical interaction networks that exist in a cell. To this end, the systems and methods described herein generate a plurality of possible candidate networks and then apply to these networks a forward simulation process to infer a network. Inferred networks may be analyzed via data fitting and other fitting criteria, to determine the likelihood that the network is correct. In this way, new and more complete models of cellular dynamics may be created.

Claims

1. A method of inferring cellular structural networks, comprising:

(a) furnishing to a first physical computing device a seed network comprising a plurality of links;

(b) using the first physical computing device, iteratively;

(b1) generating a trial network by combining one or more probable links selected from a probable links database with said seed network;

(b2) filtering each said trial network according to its topology to determine if said trial network is an invalid trial network; and

(b3) repeating steps (b1) through (b2) until said filtering determines said trial network is a valid trial network;

(c) using the first physical computing device or a second physical computing device, determining a cost for each said valid trial network;

(d) using the first physical computing device or a second physical computing device, accepting or rejecting said valid trial network for inclusion in a pool of networks based on said cost;

(e) repeating steps (b) through (d) until a selected number of links in said probable links database have been combined into trial networks;

(f) repeating steps (a) through (e) until the average cost of said valid trial networks in said pool reaches equilibrium to form a final pool;

(g) using the first physical computing device or a second physical computing device, selecting one or more valid trial networks from said final pool having low cost; and

(h) outputting through a display device or a communication device the one or more valid trial networks to a user, the one or more valid trial networks configured for simulating a biological structural network on a computer and predicting a behavior of the biological structural network.

2. The method of claim 1, wherein said generating a trial network further comprises employing a spin model.

3. The method of claim 1, wherein said filtering each said trial network further comprises determining if each said trial network is scale free.

4. The method of claim 1, further comprising:

(i) before step (c), using the first physical computing device, iteratively optimizing said valid trial network, said optimizing comprising

(i1) postulating one or more parameter values for each link in said valid trial network;

(i2) simulating said valid trial network with said postulated parameter values;

(i3) comparing the results of said simulating with pre-existing data, said pre-existing data comprising experimental data;

(i4) adjusting said postulated parameter values according to the results of said comparing; and

(i5) repeating steps (i1) through (i4) until said comparing converges;

wherein said determining a cost for each said valid trial network is based at least in part on said optimizing.

5. The method of claim 4, wherein said comparing the results of said simulating with said data further comprises adding noise to said data prior to said comparing.

6. The method of claim 1, wherein said accepting or rejecting said valid trial network further comprises means for identifying and removing a valid trial network already in said pool.

7. The method of claim 6, wherein said means for identifying and removing a valid trial network comprise a simulated annealing protocol.

8. The method of claim 6, wherein said means for identifying and removing a valid trial network comprise a genetic algorithm.

9. The method of claim 1, wherein said selecting further comprises analyzing said valid trial networks in said final pool to identify one or more pathways common to a plurality of valid trial networks.

10. A system for inferring cellular networks, comprising:

(a) means for furnishing a seed network comprising a plurality of links;

(b) processing means for iteratively;

(b1) generating a trial network by combining one or more probable links selected from a probable links database with said seed network;

(b2) filtering each said trial network according to its topology to determine if said trial network is an invalid trial network; and

(b3) repeating steps (b1) through (b2) until said filtering determines said trial network is a valid trial network;

(c) processing means for determining a cost for each said valid trial network;

(d) processing means for accepting or rejecting said valid trial network for inclusion in a pool of networks based on said cost;

(e) repeating steps (b) through (d) until a selected number of links in said probable links database have been combined into trial networks;

(f) repeating steps (a) through (e) until the average cost of said valid trial networks in said pool reaches equilibrium to form a final pool;

(g) processing means for selecting one or more valid trial networks from said final pool having low cost; and

(h) displaying means for outputting the one or more valid trial networks to a user, the one or more valid trial networks configured for simulating a biological network on a computer and predicting a behavior of the biological network.

11. A computer system for use in inferring cellular networks, comprising:

a computer comprising one or more processors, a display device, and a memory device, the one or more processors configured for;

(a) furnishing a seed network comprising a plurality of links;

(b) iteratively;

(b1) generating a trial network by combining one or more probable links selected from a probable links database with said seed network;

(b2) filtering each said trial network according to its topology to determine if said trial network is an invalid trial network; and

(b3) repeating steps (b1) through (b2) until said filtering determines said trial network is a valid trial network;

(c) determining a cost for each said valid trial network;

(d) accepting or rejecting said valid trial network for inclusion in a pool of networks based on said cost;

(e) repeating steps (b) through (d) until a selected number of links in said probable links database have been combined into trial networks;

(f) repeating steps (a) through (e) until the average cost of said valid trial networks in said pool reaches equilibrium to form a final pool;

(g) selecting one or more valid trial networks from said final pool having low cost; and

(h) outputting to the display device, the one or more valid trial networks to a user, the one or more valid trial networks configured for simulating a biological network on a computer and predicting a behavior of the biological network.