System and method for reconstructing pathways in large genetic networks from genetic perturbations

• US 20030023388A1
• Filed: 05/07/2002
• Published: 01/30/2003
• Est. Priority Date: 05/07/2001
• Status: Active Grant

• Current Assignee: Science & Technology Corporation
• Original Assignee: Science & Technology Corporation
• Inventors: Wagner, Andreas
• Granted Patent: US 7,124,032 B2
• Time in Patent Office: Days
• US Class Current: 702/20
• 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

Abstract

A system and method for reconstructing pathways in large genetic networks from genetic perturbations comprises an analysis method and system that applies a recursive algorithm for determining the path between every gene pair in an arbitrarily large genetic network from large-scale gene perturbation data and reconstructs all direct and indirect regulatory gene interactions in the network. Graph theory mathematics is applied to genetic network reconstruction in the following manner: Genetic perturbation data is used to identify all genes accessible from a perturbed gene to generate an accessibility list for the gene. Graph theory mathematics is applied to the accessibility list and its graph to determine a condensation of the graph as defined by the condensation'"'"'s accessibility list. Graph theory mathematics is applied to the accessibility list, such as through a recursive algorithm performed on a desktop computer, to obtain an adjacency list for the gene that characterizes a genetic network.

Claims

1. A method for determining all direct and indirect genetic interactions in a graph representation of a genetic network of an organism, comprising:

obtaining a first accessibility list of said graph representation of said genetic network from appropriate genetic perturbation data;

applying graph theory mathematics to the first accessibility list and its graph to determine a condensation of the graph as defined by the condensation'"'"'s accessibility list;

applying graph theory mathematics to the condensation'"'"'s accessibility list to determine an adjacency list characterizing all direct and indirect genetic interactions in said genetic network.

2. The method of claim 1, wherein said graph theory mathematics are applied using a recursive algorithm.

3. The method of claim 2, wherein said recursive algorithm determines the adjacency list of a most parsimonious graph.

4. The method of claim 2, wherein said recursive algorithm determines a list of the longest path of said graph.

5. The method of claim 2, wherein said recursive algorithm implements steps comprised in pseudocode below:

6. The method of claim 4, wherein said recursive algorithm implements steps comprised in pseudocode below:

7. The method of claim 2, wherein determining a condensation of the graph comprises an algorithm implementing steps comprised in pseudocode below:

8. A method of comparing the structures of a plurality of genetic networks, comprising:

obtaining adjacency lists for each of said plurality of genetic networks by the method of claim 1;

generating a reconstructed network graph for each adjacency list; and

comparing the reconstructed network graphs, wherein the reconstructed network graphs characterize the structure of each genetic network.

9. The method of claim 1, wherein said genetic perturbation data and resulting adjacency list are selected from a group consisting of:

all genes of an organism whose activity has been measured, all genes of a genetic network of an organism whose activity has been measured, and all genes of a genetic sub-network of an organism whose activity has been measured.

10. The method of claim 1 where the genetic perturbation is selected from the group consisting of:

overexpression, site directed mutagenesis, single knockouts, double knockouts, gene deletion, antisense RNA, recombination, point mutation, underexpression, post translational modification, inhibition of transcription, inhibition of translation, any covalent modification, and any non-covalent modification.

11. The method of claim 1, wherein said gene perturbation data is associated with a plant and is related to genetic interactions selected from the group consisting of reproduction, host defense, tolerance to environmental stress, insecticidal activity, and other pathogen resistance.

12. The method of claim 1, wherein said gene perturbation data is associated with genetic interactions related to a potential or actual pharmaceutical.

13. The method of claim 8, wherein said gene perturbation data is associated with genetic interactions related to a potential or actual pharmaceutical.

14. The method of claim 1, wherein said gene perturbation data is associated with genetic interactions related to a potential or actual therapeutic treatment for an organism.

15. A reconstructed network graph of a genetic network created from an adjacency list produced by the method of claim 1.

16. A system for determining all direct and indirect genetic interactions in a graph representation of a genetic network of an organism, comprising:

a general purpose computer;

software instructions operating on said computer and adapted to input a first accessibility list from appropriate genetic perturbation data;

additional software instructions operating on said computer and adapted to apply graph theory mathematics to the first accessibility list and its graph to determine a condensation of the graph as defined by the condensation'"'"'s accessibility list;

further software instructions operating on said computer and adapted to applying graph theory mathematics to the condensation'"'"'s accessibility list to determine an adjacency list characterizing all direct and indirect genetic interactions in said genetic network.

17. The system of claim 16, further comprising software instructions operating on said computer and adapted to produce a graph representation of a structure of said genetic network.