\section{Related Work}

{\em Misael writes this: review definitions.
Start with Uri Alon work and then
discuss briefly the other works, but focus on ESU and on gTrie.
Show pictures of the latter two structures and explain them in detail.
Note that gTrie is better for small graphs but Ribeiro suspects
that ESU might be better otherwise.}

review definitions.
Start with Uri Alon work and then
discuss briefly the other works, but focus on ESU and on gTrie.
Show pictures of the latter two structures and explain them in detail.
Note that gTrie is better for small graphs but Ribeiro suspects
that ESU might be better otherwise.

Also, here are some other references that constitute the other works:



2002 Milo et al networks from diverse fields
contain patterns that are unlikely to occur by chance.

Statistically overrepresented sub-structures.

Feedforward loop:

X ---> Z, Y --> Z, X --> Y.

All interactions are positive happens a lot.
X induces Z, X positive towards Y, but Y represses Z
happens a lot.
In Ecoli and yeast.

Other ones like:
autoregulation, single input module, dense overlapping regulons and feedback loops, etc



====
Synthetic bio ref
http://kurata21.bio.kyutech.ac.jp/cadlive/References/Brief%20Bioinform-2013-Kurata.pdf

BioFNet: biological functional network
database for analysis and synthesis of
biological systems
Hiroyuki Kurata, Kazuhiro Maeda, Toshikazu Onaka and Takenori Takata
Briefings in Bioinformatics Advance Access published July 27, 2013
BRIEFINGS IN BIOINFORMATICS. page 1 of 11 doi:10.1093/bib/bbt048

This paper discusses motifs in both synthetic and natural networks.
Smaller motifs can be part of larger motifs, e.g. feed forward
networks can be part of first-in first-out networks.
(Figures 1 and 2) based on different kinetic coefficients.

Also" "Addition of a functional network to an existing
network can enhance the function of the existing
one. Addition of a positive feedback loop to a negative
feedback loop network enhances the oscillatory
behavior generated by the negative feedback"

Can get robustness:
"In this context, biological
design is characterized by the fact that cells must
coexist with such parameter uncertainty and noise.
In fact, some biochemical systems use noise to enhance
oscillation and bistability or to generate heterogeneity
of gene expression. Noise-generated
heterogeneity can increase the chances for some
parts of the cell population to adapt to fluctuating
environments. They may be advantageous for survival
in consistently fluctuating environments."

So conclusion is that we want to detect all motifs.
There may be overlap..

BioFNet
$http://kurata22.bio.kyutech.ac.jp/db/pub/pub_main.php?Ver=3.7$

Could look just for those motifs.

Also would want to query on edges as well.

=====

$survey_freq_subgraph.pdf$
The Knowledge Engineering Review, Vol. 00:0, 1–31.
c 2004, Cambridge University Press
DOI: 10.1017/S000000000000000 Printed in the United Kingdom
A Survey of Frequent Subgraph Mining Algorithms
Chuntao Jiang, Frans Coenen and Michele Zito

        Chuntao Jiang, Frans Coenen, Michele Zito: A survey of frequent subgraph mining algorithms. Knowledge Eng. Review 28(1): 75-105 (2013)


p. 8:
"A canonical labelling strategy defines a unique code for a given graph"

We want this to detect identical graphs (not isomorphic ones,
as the paper says, but identical ones).
One approach is simply to use the node ids but in the case
of loops this leads to ambiguity.
Another approach is to name the edges by their vertex ids
and then sort them by their vertex ids in lexicographic order.
I think this should work as long as every edge has the same label.

DISCUSS: why aren't we talking about frequent subgraph mining algorithms.

DISCUSS: "For discussion purposes, the FGM algorithms examined in this section are categorized into
“general purpose” and “pattern dependent” FGM. The distinction is that in the latter case
the nature of the patterns to be discovered is in some way specialized or limited because of
the nature of the application domain (e.g. we are only interested in subgraphs satisfying some
specific constraints). Consequently, knowledge of the nature of these special patterns allows for
a reduction of the search space."

DISCUSS: p. 22:
"Relational graphs are suitable for modelling large scale networks such as biological or social
networks. Yan et al. (2005a) indicated that relational pattern mining has three features which
serve to differentiate it from general purpose frequent subgraph mining: (i) the data has distinct
vertex labels, (ii) the data comprises very large graphs, and (iii) a focus on frequent patterns with
certain connectivity constraints (e.g. the minimum degree19 of a pattern). Thus relational graph
mining aims to identify all frequent patterns displaying a specified connectivity constraint."

Should read section 5.2 of this paper.

DISCUSS:
5.2.4 Constrained pattern mining
The main idea of user constraint based frequent pattern mining is to integrate constraints into
the mining process in order to prune the search space. Zhu et al. (2007) presented a framework,
called gPrune, to incorporate various constraints into the frequent subgraph mining process. In
gPrune, the search spaces of both data and patterns were examined and a new concept, patterninseparable-
data-anti-monotonicity (D-anti-monotonicity), introduced to support effective pruning
of the search space. However, an empirical study showed that the benefit of such D-antimonotonicity
pruning was coupled tightly with the speed of the corresponding constraint measure
function. Furthermore, experiments indicated that the effectiveness of integrating constraints
into the FSM process is influenced by many aspects, including the properties of the data and
the pruning cost. Constraint based mining algorithms therefore need to take into account the
trade-off between the pruning cost and any potential benefit.


=====

Ribeiro thesis:

p. 32:
Analytical methods to estimate the significance of motifs are
now appearing [MSB+06, PDK+08]. These methods would be able to escape the need
for the ensemble of random networks and their respective census, but there is still a
long path to be accomplished in order for them to be general and practical enough

pp. 40ff: lots of nice pictures.

p. 43: The original paper from Milo et al. [MSOI+02] uses {0.01, 4, 0.1, 1000} as the set of
respective parameters {P, U,D,N}. This is the same as saying that they used 1000
similar random networks and considered a subgraph to be a motif if: the probability
that it appears more often in a random network than in the original network is less
than 1%; it appeared at least 4 times; the difference between its frequency in the
original network and the average frequency in random networks is at least 10% of that
average frequency.

p. 49: We should also note that Birmel´e presented an alternative motif definition, in which
significance is evaluated through local over-representation, instead of global overrepresentation,
and introduced a statistical method for computing this measure without
the generation of random networks [Bir11].

p. 50 to distinguish with frequent subgraph mining:
is substantially different because its goal
is to find the most frequent subgraphs that appear in a set of graphs, while in the
network motifs we try to find the frequency of all subgraphs on a single graph.

p. 51: Figures of motifs.

p. 58: basic algorithm.

Algorithm 3.1 Typical program flow of motif discovery.
Require: Graph G and integers k and R
Ensure: Motifs of size k in graph G
1: subgraphCensus(k, G)
2: for i := 1 to R do
3: Ri := generateSimilarRandomNetwork(G)
4: subgraphCensus(k, Ri)
5: calculateSignificanceMotifs()

pp. 60 ff: description of the algorithms.

Symmetry Breaking indicates if the method only finds once each occurrence of the
motif. Since a subgraph can have several automorphisms, a careless approach could
end up finding the same subgraph following a different search path. It is therefore
desirable to find each instance only once, avoiding redundant calculations due to
symmetry.

pp. 64ff: starts with netfinder.

p. 66
ESU: the way you read it is that on the left of the comma,
you have the nodes in the growing subgraph and to the right
you have candidate neighbors (whose numbers must
be greater than the "spawning" node which seems to be
the last node added).


1 -- 3 -- 2 ==> seems like we never get all three nodes.
