Systems and methods for inferring biological networks

• US 20040243354A1
• Filed: 08/29/2003
• Published: 12/02/2004
• Est. Priority Date: 08/29/2002
• Status: Active Grant

• Current Assignee: Gene Network Sciences, Inc
• Original Assignee: Gene Network Sciences, Inc
• Inventors: Periwal, Vipul
• Granted Patent: US 7,512,497 B2
• Time in Patent Office: Days
• US Class Current: 702/188
• 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 networks, comprising:

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

(b) iteratively;

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

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

(b.3) repeating steps (b.1) through (b.2) until said filtering determines said trial network is a valid trial network;

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

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

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

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

(h) selecting one or more valid trial networks from said final pool having low cost.

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:

(c) before step (d), iteratively optimizing said valid trial network, said optimizing comprising

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

(c.2) simulating said valid trial network with said postulated parameter values;

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

(c.4) adjusting said postulated parameter values according to the results of said comparing; and

(c.5) repeating steps (c.1) through (c.4) 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) means for iteratively;

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

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

(b.3) repeating steps (b.1) through (b.2) until said filtering determines said trial network is a valid trial network;

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

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

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

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

(h) means for selecting one or more valid trial networks from said final pool having low cost.

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

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

(b) iteratively;

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

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

(b.3) repeating steps (b.1) through (b.2) until said filtering determines said trial network is a valid trial network;

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

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

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

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

(h) selecting one or more valid trial networks from said final pool having low cost.

12. A computer-readable medium storing a computer program executable by a plurality of server computers, the computer program comprising computer instructions for:

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

(b) iteratively;

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

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

(b.3) repeating steps (b.1) through (b.2) until said filtering determines said trial network is a valid trial network;

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

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

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

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

(h) selecting one or more valid trial networks from said final pool having low cost.

13. A computer data signal embodied in a carrier wave, comprising computer instructions for:

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

(b) iteratively;

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

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

(b.3) repeating steps (b.1) through (b.2) until said filtering determines said trial network is a valid trial network;

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

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

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

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

(h) selecting one or more valid trial networks from said final pool having low cost.