EP1483725A2 - Procede permettant d'analyser des donnees afin d'identifier des motifs de reseau - Google Patents

Procede permettant d'analyser des donnees afin d'identifier des motifs de reseau

Info

Publication number
EP1483725A2
EP1483725A2 EP03731803A EP03731803A EP1483725A2 EP 1483725 A2 EP1483725 A2 EP 1483725A2 EP 03731803 A EP03731803 A EP 03731803A EP 03731803 A EP03731803 A EP 03731803A EP 1483725 A2 EP1483725 A2 EP 1483725A2
Authority
EP
European Patent Office
Prior art keywords
graph
sub
network
analyzing
networks
Prior art date
Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
Ceased
Application number
EP03731803A
Other languages
German (de)
English (en)
Other versions
EP1483725A4 (fr
Inventor
Uri Alon
Shai S. Shen-Orr
Ron Milo
Current Assignee (The listed assignees may be inaccurate. Google has not performed a legal analysis and makes no representation or warranty as to the accuracy of the list.)
Yeda Research and Development Co Ltd
Original Assignee
Yeda Research and Development Co Ltd
Priority date (The priority date is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the date listed.)
Filing date
Publication date
Application filed by Yeda Research and Development Co Ltd filed Critical Yeda Research and Development Co Ltd
Publication of EP1483725A2 publication Critical patent/EP1483725A2/fr
Publication of EP1483725A4 publication Critical patent/EP1483725A4/fr
Ceased legal-status Critical Current

Links

Classifications

    • G—PHYSICS
    • G16—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR SPECIFIC APPLICATION FIELDS
    • G16B—BIOINFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR GENETIC OR PROTEIN-RELATED DATA PROCESSING IN COMPUTATIONAL MOLECULAR BIOLOGY
    • G16B5/00—ICT specially adapted for modelling or simulations in systems biology, e.g. gene-regulatory networks, protein interaction networks or metabolic networks
    • G—PHYSICS
    • G16—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR SPECIFIC APPLICATION FIELDS
    • G16B—BIOINFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR GENETIC OR PROTEIN-RELATED DATA PROCESSING IN COMPUTATIONAL MOLECULAR BIOLOGY
    • G16B5/00—ICT specially adapted for modelling or simulations in systems biology, e.g. gene-regulatory networks, protein interaction networks or metabolic networks
    • G16B5/30—Dynamic-time models
    • G—PHYSICS
    • G16—INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR SPECIFIC APPLICATION FIELDS
    • G16B—BIOINFORMATICS, i.e. INFORMATION AND COMMUNICATION TECHNOLOGY [ICT] SPECIALLY ADAPTED FOR GENETIC OR PROTEIN-RELATED DATA PROCESSING IN COMPUTATIONAL MOLECULAR BIOLOGY
    • G16B5/00—ICT specially adapted for modelling or simulations in systems biology, e.g. gene-regulatory networks, protein interaction networks or metabolic networks
    • G16B5/10—Boolean models

Definitions

  • the present invention is of a method for analyzing data for identifying at
  • the motif is identified according to a pattern of a plurality of
  • gene regulation networks are complex, and thus new
  • motif defined as a
  • DNA sequences and protein structures 9 DNA sequences and protein structures 9 .
  • a combinatorial explosion may occur if the number of components
  • the method is suitable for any network which is
  • the method of the present invention can as an example optionally be used
  • biological networks such as neuronal networks 11 , or gene
  • regulation networks 1 particularly those involved in the regulation of transcription.
  • Neuronal networks orchestrate all nerve signals to the different parts of the body
  • the method of the present invention enables such networks to be
  • each class of networks is required 16 .
  • the present invention provides a method for
  • the method of the present invention is optionally and preferably used to
  • the comparison may yield a difference
  • the present invention may also optionally be useful for analyzing electronic
  • circuits and chips for chip design for example. Analysis of a chip design may be
  • the present invention is particularly useful for systems that feature a
  • analyzing the system includes analyzing
  • FIG. 1 is a flow chart of an exemplary method according to the present
  • FIG. 2 a shows examples of interactions represented by directed edges
  • transcription factor protein X binds regulatory DNA
  • FIG. 3 shows a schematic view of network motif detection.
  • FIG. 4 is a representation of a gene transcriptional network as a directed
  • FIG. 5 Network motifs found in the E. coli transcriptional regulation
  • FIG. 5 A shows an example of a motif, termed 'fan-out', defined by a set of
  • FIG. 5B shows a particular example of the "fan-out" motif for the arginine
  • FIG. 5C shows an example of a second motif, termed 'gate array', which is
  • FIG. 5D shows a particular example of this second motif for the set of
  • FIG. 5E shows an example of a third motif, termed 'feedforward loop'
  • transcription factor X that regulates a second transcription factor Y
  • FIG. 5F shows a particular example of this third motif for the L-arabinose
  • FIG. 6 shows the concentration, C, of the feedforward loop motif in real
  • FIG. 7 shows the network motifs found in the two gene-regulation, one
  • FIG. 8 shows a representation of the entire known E. coli transcriptional
  • FIG. 9A shows a feedforward loop (FFL) that can be used as a 'persistence
  • FIG. 9B displays a simple regulation (SR) circuit, in which one operon
  • FIG. 9C presents the response of FFL and SR circuits to a short and a long
  • FIG 10 shows network motifs found in biological and technological
  • yeast S. cerevisae M. C. Costanzo et al, Nucleic Acids Res
  • nodes represent logic gates and flip-flops (presented are all 5 partial scans of
  • World-Wide Web hyperlinks between web pages in a single domain (A. L.
  • the present invention is of a method for analyzing data, such as biological
  • the method of the present invention can optionally be applied to
  • biological systems such as gene regulatory systems or neuronal network for
  • the present invention optionally and preferably provides a method for
  • the method preferably includes analyzing
  • each sub-graph containing a plurality of nodes connected by at least one edge; and analyzing the plurality of sub-graphs
  • sub-graphs further includes constructing a randomized graph; and comparing a
  • the motif is formed with the type of sub-graph.
  • the randomized graph has at least one feature similar to the
  • the method is
  • a connectivity matrix which represents
  • An element (i,j) 1 if a first component i is
  • Submatrices may optionally and preferably be enumerated efficiently by recursively searching for nonzero elements (i,j), then scanning row i and column j
  • a search may also optionally be performed for identical
  • a "fan-out" occurs when a plurality
  • overlapping regions of a plurality of components of the system are optionally
  • the group is
  • a distance measure is optionally and more preferably used to determine this
  • This distance measure is most preferably selected according to the type
  • the matrix is preferably scanned for all possible n-
  • Each network contains numerous types of n-node circuits. To focus on circuits that
  • the randomized networks are selected.
  • Each node has precisely the same single-node characteristics as the real network:
  • randomized ensemble accounts for patterns that appear only because of the single- node characteristics of the network (for example, the presence of highly connected
  • a statistical significance is assigned to each circuit by comparing the
  • N eff (A) N real (A) ⁇ B N rand (B)/N real (B)
  • N rea i is the number of times a circuit appears in the real network and N rand is
  • the network motifs are preferably motifs that satisfy two conditions.
  • the graph is preferably analyzed by scanning all nodes in an
  • connectivity matrices is constructed, wherein each connectivity matrix represents a
  • the first part involves analyzing the system. This part is performed by
  • stage 2 the graph is searched for a plurality of sub ⁇
  • the second part preferably involves determining the significance of the
  • stage 3 optionally and preferably, a
  • This randomized graph preferably has at least
  • graph may be considered to be a motif. Significance may optionally and
  • significance may optionally and preferably be determined according to statistical significance of the
  • Each network contains
  • the real network is preferably compared to suitably randomized
  • each node in the randomized networks has the same number of
  • the network motifs are preferably those patterns for which the probability P
  • M jk -1 and M k l. This is recursively repeated with elements (i,k), (k,i), (j,k) and
  • the number of appearances of each type of subgraph in the random ensemble is the number of appearances of each type of subgraph in the random ensemble.
  • edges and nodes are edges and nodes, multi-partite graphs etc.
  • network motifs are subgraphs which meet the following criteria:
  • Gate array detection An algorithm for detecting dense regions of
  • the splitting distance (-0.36).
  • the splitting distance is a measure of the separation of the
  • cluster is merged into a larger cluster minus the linkage distance at which its two
  • Algorithm A A Markov-chain algorithm was employed (S. Shen-Orr, R.
  • Algorithm B Identical statistics were obtained using a direct construction
  • the goal is to create a randomized connectivity matrix, Mrand,
  • directed edge switches (XI ->Y1, X2 ⁇ Y2 is replaced by X1 - Y2, X2- Y ⁇ ) are
  • Vrand t be the corresponding vector in the randomized network.
  • the process starts by fully randomizing the network according to algorithm
  • T is the difference in energy before and after the switch, and T is an effective
  • Algorithms for non-directed networks Algorithm A was used, treating all edges
  • Table 1 shows subgraphs and motifs in non-directed networks. Shown are
  • the networks are a 2212 node / 4406 edge yeast protein-interaction
  • Anti-motifs are subgraphs which satisfy: (i)
  • Nrand - Nreal > 0.1 Nrand.
  • Example 1 was tested for the analysis of the E. coli and S. cerevisiae
  • the motif has a specific function in determining gene expression.
  • the motifs also serve as
  • TFs transcription factors
  • operons are one or more of the operons they regulate (an operon is one or more of the transcription factors (TFs) and the operons they regulate (an operon is one or more of the transcription factors (TFs) and the operons they regulate (an operon is one or more of the transcription factors (TFs) and the operons they regulate (an operon is one or more of the transcription factors (TFs) and the operons they regulate (an operon is one or more
  • RegulonDB 1>22 ' 23 .
  • the RegulonDB database was enhanced by an
  • the dataset consists of established interactions
  • operon is compact, whereas the distribution of the number of operons regulated by
  • a TF is long-tailed with an average of ⁇ 5.
  • the S. cerevisiae transcriptional network with 690 nodes and 1094
  • arrows are transcription factors.
  • yeast several transcription factors jointly
  • transcription factors that function in a complex was united into a single node.
  • the transcriptional network can be represented as a directed graph.
  • Edges represent direct transcriptional interactions. Each edge
  • the first motif termed 'fan-out', is defined by a set of operons that are
  • TF is usually autoregulatory, all of the operons are under control of the same sign
  • TFs exhibiting the fan-out motif are usually autoregulatory (70%, mostly
  • the second motif termed 'gate array', is a layer of overlapping interactions
  • the gate arrays are defined by an algorithm aimed at
  • TFs see Methods.
  • An example is the set of operons regulated by RpoS upon
  • every output operon is controlled by a
  • Gate arrays are dense regions of interactions in
  • Operons in gate arrays are regulated by 3.1 TFs on
  • Gate arrays occur rarely in randomized networks (P-0.001) since there is a low probability for a high
  • the third motif, a 3-node motif termed 'feedforward loop' 17 is defined by a
  • transcription factor X that regulates a second transcription factor Y, such that both
  • Factor X may be termed
  • a feedforward loop motif may be termed 'coherent' if the direct effect of
  • Feedforward loops are stylized structures, which occur
  • circuits recur throughout the network, but at numbers that are less than the mean
  • nodes represent operons
  • lines represent
  • transcriptional regulation directed so that the regulating TF is above the regulated
  • each TF name is preceded by the sign of its autoregulation (if
  • Feedforward loops and fan-outs often occur at the outputs of
  • operons are controlled by relatively shallow cascades. A depth for each operon
  • operons are at depth 2. There are few long cascades, such as cascades of depth 5
  • the gate array layer may therefore represent
  • Transcriptional feedback loops occur in other organisms, such as the
  • gate arrays allow the ratios between the expression of the output operons to be tuned by multiple inputs.
  • gate arrays appear in systems where complex responses are mobilized
  • the stationary phase gate array can be any suitable stationary phase gate array.
  • the stationary phase gate array can be any suitable stationary phase gate array.
  • the feedforward loop motif often occurs where external signals cause a
  • node subgraphs recur throughout the networks, but at numbers that are less than
  • Nodes represent neurons (or neuron
  • connections represent synaptic connections between the neurons.
  • the C. elegans neuronal synaptic connectivity network with 67 nodes and
  • network motifs may point to a fundamental similarity in the design constraints of
  • Both networks function to carry information from
  • sensory components sensor neurons / transcription factors regulated by
  • the nodes X and Y represent transcription factors
  • the node Z is the output gene or motor neuron.
  • circuit is x(t) (activation of the transcription factor X by a biochemical signal or
  • the output node Z be activated.
  • the circuit functions as a 'persistence
  • the FFL circuit is essentially an AND gate over a one step cascade ( Figure
  • a two-step cascade has a slow
  • the FFL has a fast turn-off rate but does not effectively suppress transient inputs.
  • circuit can both suppress transient inputs and has a turn-off rate as fast as a one-
  • step cascade Indeed, the vast majority (90%) of the input nodes in the neuronal
  • feedforward loops are sensory neurons, which may require this type of information
  • the nodes represent groups of species and connections are directed from
  • Each of the food webs displays one or two 3-node network motifs and one
  • the 'consensus motifs' can be defined as the network motifs shared by
  • motifs' can be defined as the motifs shared by networks of a given type. Five of
  • the 3-node motif termed '3-chain' is significant, while the 3-node
  • omn ⁇ vores are selected against.
  • the 'bi-parallel' motif (described in example 3) indicates that prey of a
  • the technological networks studied include the ISCAS89 benchmark set of
  • the motifs separate the circuits into classes that correspond to the circuit's
  • multipliers share three motifs including 3- and 4-node feedback loops.
  • World-Wide Web motifs may reflect a design aimed at short paths between related pages.
  • Application of the present approach to non-directed networks shows
  • motifs can define broad classes of networks, each with specific types of
  • the motifs may have specific functions
  • the present invention may also optionally be used to analyze such "man-
  • Business processes are a description of how a particular company or
  • Eschrichia coli and Salmonella Cellular and molecular biology (ed.

Landscapes

  • Physics & Mathematics (AREA)
  • Health & Medical Sciences (AREA)
  • Life Sciences & Earth Sciences (AREA)
  • Engineering & Computer Science (AREA)
  • Bioinformatics & Cheminformatics (AREA)
  • Biophysics (AREA)
  • Molecular Biology (AREA)
  • Physiology (AREA)
  • Bioinformatics & Computational Biology (AREA)
  • Biotechnology (AREA)
  • Evolutionary Biology (AREA)
  • General Health & Medical Sciences (AREA)
  • Medical Informatics (AREA)
  • Spectroscopy & Molecular Physics (AREA)
  • Theoretical Computer Science (AREA)
  • Management, Administration, Business Operations System, And Electronic Commerce (AREA)

Abstract

L'invention concerne un procédé permettant d'analyser des données telles que, par exemple, des données biologiques afin d'identifier un ou plusieurs motif(s) de réseau ou modèle(s) récurant(s) de relations et/ou connexions comportementales entre les composants d'un système complexe. Ledit procédé s'applique éventuellement et de préférence à des systèmes biologiques tels que, par exemple, des systèmes de régulation génique.
EP03731803A 2002-01-22 2003-01-22 Procede permettant d'analyser des donnees afin d'identifier des motifs de reseau Ceased EP1483725A4 (fr)

Applications Claiming Priority (5)

Application Number Priority Date Filing Date Title
US34936502P 2002-01-22 2002-01-22
US349365P 2002-01-22
US42073002P 2002-10-24 2002-10-24
US420730P 2002-10-24
PCT/IL2003/000053 WO2003062943A2 (fr) 2002-01-22 2003-01-22 Procede permettant d'analyser des donnees afin d'identifier des motifs de reseau

Publications (2)

Publication Number Publication Date
EP1483725A2 true EP1483725A2 (fr) 2004-12-08
EP1483725A4 EP1483725A4 (fr) 2008-10-29

Family

ID=27616739

Family Applications (1)

Application Number Title Priority Date Filing Date
EP03731803A Ceased EP1483725A4 (fr) 2002-01-22 2003-01-22 Procede permettant d'analyser des donnees afin d'identifier des motifs de reseau

Country Status (5)

Country Link
US (1) US20040204925A1 (fr)
EP (1) EP1483725A4 (fr)
AU (1) AU2003237982A1 (fr)
IL (1) IL162413A0 (fr)
WO (1) WO2003062943A2 (fr)

Families Citing this family (22)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
US7171639B2 (en) * 2004-03-18 2007-01-30 Intel Corporation Comparison of circuit layout designs
US7558768B2 (en) * 2005-07-05 2009-07-07 International Business Machines Corporation Topological motifs discovery using a compact notation
WO2007038414A2 (fr) * 2005-09-27 2007-04-05 Indiana University Research & Technology Corporation Exploitation de reseaux d'interactions entre proteines
JP2008152731A (ja) * 2006-12-20 2008-07-03 Sony Corp 情報処理装置および方法、並びにプログラム
US8781754B2 (en) * 2007-01-10 2014-07-15 International Business Machines Corporation Method and apparatus for detecting consensus motifs in data sequences
US8775475B2 (en) * 2007-11-09 2014-07-08 Ebay Inc. Transaction data representations using an adjacency matrix
US8046324B2 (en) * 2007-11-30 2011-10-25 Ebay Inc. Graph pattern recognition interface
US8000262B2 (en) * 2008-04-18 2011-08-16 Bonnie Berger Leighton Method for identifying network similarity by matching neighborhood topology
US8341740B2 (en) * 2008-05-21 2012-12-25 Alcatel Lucent Method and system for identifying enterprise network hosts infected with slow and/or distributed scanning malware
US8612160B2 (en) * 2008-11-14 2013-12-17 Massachusetts Institute Of Technology Identifying biological response pathways
US8645210B2 (en) * 2010-05-17 2014-02-04 Xerox Corporation Method of providing targeted communications to a user of a printing system
US8504948B2 (en) * 2010-09-30 2013-08-06 William Marsh Rice University Designing synthetic biological circuits using optimality and nonequilibrium thermodynamics
GB201107251D0 (en) * 2011-05-03 2011-06-15 Univ Dublin Netowrk analysis tool
US20130325203A1 (en) * 2012-06-05 2013-12-05 GM Global Technology Operations LLC Methods and systems for monitoring a vehicle for faults
EP2869209A1 (fr) 2013-11-05 2015-05-06 Max-Planck-Gesellschaft zur Förderung der Wissenschaften e.V. Recouvrements par sous-graphes en tant que représentations de graphes creux
CN103729296B (zh) * 2013-12-31 2017-02-15 北京理工大学 一种基于网络Motif的软件稳定性评估方法
US10366343B1 (en) * 2015-03-13 2019-07-30 Amazon Technologies, Inc. Machine learning-based literary work ranking and recommendation system
US11030246B2 (en) * 2016-06-10 2021-06-08 Palo Alto Research Center Incorporated Fast and accurate graphlet estimation
US11120069B2 (en) 2016-07-21 2021-09-14 International Business Machines Corporation Graph-based online image queries
US10728105B2 (en) * 2018-11-29 2020-07-28 Adobe Inc. Higher-order network embedding
CN110473591B (zh) * 2019-08-20 2022-09-27 西南林业大学 基于量子计算的基因网络功能模块挖掘及分析方法
US20250278326A1 (en) * 2024-03-01 2025-09-04 Hitachi, Ltd. Asset operation recommendation based on dynamic & static event detection and pattern discovery for hidden failure analysis

Family Cites Families (1)

* Cited by examiner, † Cited by third party
Publication number Priority date Publication date Assignee Title
WO2002072868A2 (fr) * 2001-03-10 2002-09-19 Bioinformatics Dna Codes, Llc Methodes et instruments pour la selection et la production d'analyses de sequences d'acides nucleiques

Non-Patent Citations (3)

* Cited by examiner, † Cited by third party
Title
MILO R ET AL: "Network motifs: Simple building blocks of complex networks" SCIENCE 20021025 US, vol. 298, no. 5594, 25 October 2002 (2002-10-25), pages 824-827, XP002496255 ISSN: 0036-8075 *
See also references of WO03062943A2 *
XU Y ET AL: "Protein domain decomposition using a graph-theoretic approach" BIOINFORMATICS, OXFORD UNIVERSITY PRESS, SURREY, GB, vol. 16, no. 12, 1 January 2000 (2000-01-01), pages 1091-1104, XP002973481 ISSN: 1367-4803 *

Also Published As

Publication number Publication date
WO2003062943A3 (fr) 2004-02-26
IL162413A0 (en) 2005-11-20
AU2003237982A1 (en) 2003-09-02
US20040204925A1 (en) 2004-10-14
WO2003062943A2 (fr) 2003-07-31
EP1483725A4 (fr) 2008-10-29

Similar Documents

Publication Publication Date Title
WO2003062943A2 (fr) Procede permettant d'analyser des donnees afin d'identifier des motifs de reseau
Rood et al. Toward a foundation model of causal cell and tissue biology with a Perturbation Cell and Tissue Atlas
Bergmann et al. Similarities and differences in genome-wide expression data of six organisms
Prill et al. Dynamic properties of network motifs contribute to biological network organization
Ideker et al. Discovery of regulatory interactions through perturbation: inference and experimental design
Brazma et al. Gene expression data analysis
Gustafsson et al. Constructing and analyzing a large-scale gene-to-gene regulatory network Lasso-constrained inference and biological validation
Kaya MOGAMOD: Multi-objective genetic algorithm for motif discovery
Gabora et al. An evolutionary process without variation and selection
Borella et al. PsiNorm: a scalable normalization for single-cell RNA-seq data
Otero-Muras et al. Design principles of biological oscillators through optimization: forward and reverse analysis
Zhang et al. A big world inside small-world networks
Gerber et al. Automated discovery of functional generality of human gene expression programs
Vorontsov et al. Cross-platform DNA motif discovery and benchmarking to explore binding specificities of poorly studied human transcription factors
Gutiérrez-Avilés et al. LSL: A new measure to evaluate triclusters
Qader et al. Motif discovery and data mining in bioinformatics
Deshpande et al. Efficient strategies for screening large-scale genetic interaction networks
Salem et al. MFMS: Maximal frequent module set mining from multiple human gene expression data sets
Vorontsov et al. Cross-platform motif discovery and benchmarking to explore binding specificities of poorly studied human transcription factors
Fox et al. Stochasticity or noise in biochemical reactions
Adl et al. PQSAR: The membrane quantitative structure-activity relationships in cheminformatics
Boscolo et al. Functionality Encoded in Topology? Discovering Macroscopic Regulatory Modules from Large-Scale Protein-DNA Interaction Networks
Kadelka Canalization as a stabilizing principle of gene regulatory networks: a discrete dynamical systems perspective
Araujo et al. The eco-evolutionary assembly of complex communities with multiple interaction types
Smidtas et al. Model of interactions in biology and application to heterogeneous network in yeast

Legal Events

Date Code Title Description
PUAI Public reference made under article 153(3) epc to a published international application that has entered the european phase

Free format text: ORIGINAL CODE: 0009012

17P Request for examination filed

Effective date: 20040616

AK Designated contracting states

Kind code of ref document: A2

Designated state(s): AT BE BG CH CY CZ DE DK EE ES FI FR GB GR HU IE IT LI LU MC NL PT SE SI SK TR

AX Request for extension of the european patent

Extension state: AL LT LV MK RO

RAP1 Party data changed (applicant data changed or rights of an application transferred)

Owner name: YEDA RESEARCH AND DEVELOPMEMT CO., LTD.

RAP1 Party data changed (applicant data changed or rights of an application transferred)

Owner name: YEDA RESEARCH AND DEVELOPMENT CO., LTD.

A4 Supplementary search report drawn up and despatched

Effective date: 20081001

17Q First examination report despatched

Effective date: 20081125

STAA Information on the status of an ep patent application or granted ep patent

Free format text: STATUS: THE APPLICATION HAS BEEN REFUSED

18R Application refused

Effective date: 20091010