% This is LLNCS.DEM the demonstration file of
% the LaTeX macro package from Springer-Verlag
% for Lecture Notes in Computer Science,
% version 2.4 for LaTeX2e as of 16. April 2010
%
\documentclass{llncs}
%
\usepackage{makeidx}  % allows for indexgeneration
%

\usepackage{times}
\usepackage{amsmath}
\usepackage{balance}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{color}
\usepackage{algorithmic}
\usepackage{url}
\usepackage[boxed,noend]{algorithm2e}
\usepackage{mdwlist}
%\usepackage{epsfig}
\usepackage{subfigure}
\usepackage{epstopdf}
\usepackage{multirow}


\begin{document}
%
% \frontmatter          % for the preliminaries
%
\pagestyle{headings}  % switches on printing of running heads
\vspace{1cm}
\tableofcontents
%
\mainmatter              % start of the contributions
%
\title{gLabTrie: a data structure for motif discovery with constraints}
%
\titlerunning{gLabTrie}  % abbreviated title (for running head)
%                                     also used for the TOC unless
%                                     \toctitle is used
%
\author{M. Mongiov\'\i \inst{1}$^{*}$, G. Micale \inst{2}$^{*}$, A. Ferro \inst{3}, R. Giugno \inst{3}, A. Pulvirenti \inst{3} \and D. Shasha \inst{4}}
%
%
%
\institute{Semantic Technology Lab, ISTC-CNR, Catania, Italy, \\
\email{misael.mongiovi@istc.cnr.it}
\and
Department of Maths and Computer Science, Catania, Italy, \\ 
\email{micale@di.unipi.it}
\and
Department of Clinical and Experimental Medicine, Catania, Italy, \\
\email{ferro@dmi.unict.it, giugno@dmi.unict.it, apulvirenti@dmi.unict.it}
\and
Courant Institute of Mathematical Science NYU, New York, USA
\email{shasha@courant.nyu.edu}
}
\thanks{These authors contributed equally to this work}

\maketitle              % typeset the title of the contribution

\input{abstractintro}

%\input{relatedwork}


\section{gLabTrie structure}

\input{method.tex}

\input{related_and_pval_revised}

\input{experiments}

\section{Conclusion}

Our structures gLabTrie and TopoIndex contribute to all aspects of motif finding,
by giving a very fast method for finding labeled topological structures
in both input networks and related random networks.
As this is work in progress, we plan in the near future to 
(1) find analytical methods for computing p-values on labeled topological
structures to avoid the need for random graphs;
(2) extend the search algorithms to enable search for topologies having, say,
$k$ vertices, even though the TopoIndex holds topologies of only a smaller
size.

\section*{Acknownledgements}
Shasha's work has been partially supported by an INRIA International Chair and
the U.S. National Science
Foundation under grants
MCB-1412232,
IOS-1339362,
MCB-1355462,
MCB-1158273,
IOS-0922738,
and
MCB-0929339.
This support is greatly appreciated.

%
% ---- Bibliography ----
%
\begin{thebibliography}{5}
%\bibliography{ref}
%
%\bibitem {clar:eke}
%Clarke, F., Ekeland, I.:
%Nonlinear oscillations and
%boundary-value problems for Hamiltonian systems.
%Arch. Rat. Mech. Anal. 78, 315--333 (1982)

\bibitem {kurata2014biofnet}
Kurata, H., Maeda, K., Onaka, T., Takata, T.:
BioFNet: biological functional network database for analysis and synthesis of biological systems.
Briefings in Bioinformatics 15(5), pp. 699--709 (2014)

\bibitem {ribeiro2012querying}
Ribeiro, P., Silva, F.:
Querying Subgraph Sets with G-Tries.
Proceedings of the 2nd ACM SIGMOD Workshop on Databases and Social Networks, pp. 25--30 (2012)

\bibitem {alon2007network}
Alon, U.:
Network motifs: theory and experimental approaches.
Nature Reviews Genetics 8(6), pp. 450--461 (2007)

\bibitem {milo2002network}
Milo, R., Shen-Orr, S., Itzkovitz, S., Kashtan, N., Chklovskii, D., Alon, U.:
Network Motifs: Simple Building Blocks of Complex Networks.
Science 298(5594), pp. 824--827 (2002)

\bibitem {milo2004uniform}
Milo, R., Kashtan, N., Itzkovitz, S., Newman, M.E.J., Alon, U.:
On the uniform generation of random graphs with prescribed degree sequences.
Cond. Matter 2, pp. 1--4 (2004)

\bibitem {kashtan2005spontaneous}
Kashtan, N., Alon, U.
Spontaneous evolution of modularity and network motifs.
PNAS 102(39), pp. 13773--13778 (2005)

\bibitem {sole2002model}
Solé, R.V., Pastor-Satorras, R., Smith, E., Kepler, T.B.
A model of large-scale proteome evolution.
Advances in Complex Systems 5(1), pp. 43--54 (2002)

\bibitem {newman2001random}
Newman, M.E.J., Strogatz, S.H., Watts, D.J.:
Random graphs with arbitrary degree distributions and their applications.
Physical Review E 64(2), 026118 (2001) 

\bibitem {prill2005dynamic}
Prill, R.J., Iglesias, P.A., Levchenko, A.:
Dynamic properties of network motifs contribute to biological network organization.
PLoS Biology 3(11): e343 (2005)

\bibitem {shenorr2002network}
Shen-Orr, S., Milo, R., Mangan, S., Alon, U.:
Network motifs in the transcriptional regulation network of Escherichia coli.
Nature Genetics 31(1), pp. 64--68 (2002)

\bibitem {wernicke2006efficient}
Wernicke, S.:
Efficient detection of network motifs.
IEEE/ACM Transactions on Computational Biology and Bioinformatics 3(4), pp. 347--359 (2006)

\bibitem {barabasi1999emergence}
Barabasi, A.L., Albert, R.:
Emergence of Scaling in Random Networks.
Science 286(5439), pp. 509--512 (1999)

\bibitem {picard2008assessing}
Picard, F., Daudin, J., Koskas, M., Schbath, S., Robin, S.:
Assessing the Exceptionality of Network Motifs.
Journal of Computational Biology 15(1), pp. 1--20 (2008)

\bibitem {adelson1966compound}
Adelson, R.M.:
Compound poisson distributions.
OR 17(1), pp. 73--75 (1966)

\bibitem {barbour1992poisson}
Barbour, A.D., Holst, L., Janson, S.:
Poisson approximation.
Oxford Studies in Probability, Oxford-University Press (1992)

\bibitem {nuel2006cumulative}
Nuel, G.:
Cumulative distribution function of a geometric poisson distribution.
Journal of Statistical Computation and Simulation 78(3), pp. 385--394 (2006)

\bibitem {schbath2009assessing}
Schbath, S., Lacroix, V., Sagot, M.:
Assessing the exceptionality of coloured motifs in networks.
EURASIP Journal on Bioinformatics and Systems Biology 2009:616234 (2009) 

\bibitem {grochow2007network}
Grochow, J., Kellis, M.:
Network Motif Discovery Using Subgraph Enumeration and Symmetry-Breaking.
Research in Computational Molecular Biology, Lecture Notes in Computer Science 4453, pp.92--106 (2007)

\bibitem {yan2002gspan}
Yan, X., Han, J.:
gSpan: graph-based substructure pattern mining.
Proceedings of the IEEE International Conference on Data Mining (ICDM), pp. 721--724 (2002)

\bibitem {adami2011information}
Adami, C., Qian, J., Rupp, M., Hintze, A.:
Information Content of Colored Motifs in Complex Networks.
Artificial Life 17(4), pp. 375--390 (2011)

\bibitem {ribeiro2014discovering}
Ribeiro, P., Silva, F.:
Discovering Colored Network Motifs.
Complex Networks V, Studies in Computational Intelligence 549, pp. 107--118 (2014)

\bibitem {mckay1981practical}
McKay, B.D.:
Practical graph isomorphism.
Congressus Numerantium 30, pp. 45--87 (1981)

\bibitem {ribeiro2014gtrie}
Ribeiro, P., Silva, F.:
G-Tries: a data structure for storing and finding subgraphs.
Data Mining and Knowledge Discovery 28(2), pp. 337--377 (2014)

\bibitem {opsahl2011why}
Opsahl, T.:
Why anchorage is not (that) important: Binary ties and sample selection.
http://toreopsahl.com/2011/08/12, (August 2011)

\bibitem {adamic2005political}
Adamic, L.A., Glance, N.:
The Political Blogosphere and the 2004 U.S. Election: Divided They Blog.
Proceedings of the 3rd International Workshop on Link Discovery (LinkKDD), pp. 36--43, ACM, New York (2005)

\bibitem {prasad2009human}
Prasad, T.S.K., Goel, R., Kandasamy, K., Keerthikumar, S. et al.:
Human Protein Reference Database - 2009 Update.
Nucleic Acids Research 37(suppl. 1), pp. D767--D772 (2009)

\bibitem {ley2002dblp}
Ley, M.:
The DBLP Computer Science Bibliography: Evolution, Research Issues, Perspectives.
Proc. Int. Symposium on String Processing and Information Retrieval 2476, pp. 1--10 (2002)

\bibitem {batagelj2002network}
Batagelj, V., Mrvar, M., Zavesnik, M.:
Network analysis of dictionaries.
Language Technologies, pp. 135--142 (2002)

\bibitem {dimitropoulos2005inferring}
Dimitropoulos, X., Krioukov, D., Huffaker, B., Claffy, K.C., Riley, G.:
Inferring AS Relationships: Dead End or Lively Beginning?.
4th Workshop on Efficient and Experimental Algorithms (WEA), Springer Lecture Notes in Computer Science, pp. 113--125 (2005)

\bibitem {ashburner2000gene}
Ashburner, M., Ball, C.A., Blake, J.A., Botstein, D., Butler, H., et al.:
Gene Ontology: tool for the unification of biology.
Nature Genetics 25(1), pp. 25--29 (2000)

\bibitem{maere2005bingo}
Maere, S., Heymans, K., Kuiper, M.:
BiNGO: a Cytoscape plugin to assess overrepresentation of Gene Ontology categories in Biological Networks.
Bioinformatics 21(16), pp. 3448--3449

\bibitem{bindea2009cluego}
Bindea, G., Mlecnik, B., Hackl, H., Charoetong, P., Tosolini, M. et al.:
ClueGO: a Cytoscape plug-in to decipher functionally grouped gene ontology and pathway annotation networks.
Bioinformatics 25(8), pp. 1091--1093

\bibitem {dimitropoulos2006revealing}
Dimitropoulos, X., Krioukov, D., Riley, G., Claffy, K.C.:
Revealing the Autonomous System Taxonomy: The Machine Learning Approach.
Passive and Active Measurements Workshop (PAM), pp. 91--100 (2006)


\end{thebibliography}
\clearpage
\addtocmark[2]{Author Index} % additional numbered TOC entry
\renewcommand{\indexname}{Author Index}
\printindex
\clearpage
\addtocmark[2]{Subject Index} % additional numbered TOC entry
\markboth{Subject Index}{Subject Index}
\renewcommand{\indexname}{Subject Index}
\input{subjidx.ind}
\end{document}
