A. Abboud, A. Backurs, and V. Williams, Tight hardness results for LCS and other sequence similarity measures, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, pp.59-78, 2015.

T. Akutsu, A linear time pattern matching algorithm between a string and a tree, 4th Symposium on Combinatorial Pattern Matching, pp.1-10, 1993.

A. Amir, M. Lewenstein, and N. Lewenstein, Pattern matching in hypertext, J. Algorithms, vol.35, issue.1, pp.82-99, 2000.

R. Angles and C. Gutierrez, Survey of graph database models, ACM Comput. Surv, vol.40, issue.1, 2008.

A. Backurs and P. Indyk, Edit distance cannot be computed in strongly subquadratic time (unless seth is false), Proceedings of the Forty-seventh Annual ACM Symposium on Theory of Computing, STOC '15, pp.51-58, 2015.

A. Backurs and P. Indyk, Which regular expression patterns are hard to match?, IEEE 57th Annual Symposium on Foundations of Computer Science, FOCS 2016, pp.457-466, 2016.

A. Backurs and C. Tzamos, Improving viterbi is hard: Better runtimes imply faster clique algorithms, Proceedings of the 34th International Conference on Machine Learning, vol.70, pp.311-321, 2017.

K. Bringmann and M. Kunnemann, Quadratic conditional lower bounds for string problems and dynamic time warping, Proceedings of the 2015 IEEE 56th Annual Symposium on Foundations of Computer Science (FOCS), FOCS '15, pp.79-97, 2015.

, The Computational Pan-Genomics Consortium. Computational pan-genomics: status, promises and challenges, Briefings in Bioinformatics, vol.19, issue.1, pp.118-135, 2018.

A. Conte, G. Ferraro, R. Grossi, A. Marino, K. Sadakane et al., Node similarity with q -grams for real-world labeled networks, Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining, pp.1282-1291, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01964716

M. Equi, Pattern matching in labeled graphs, 2018.

M. Equi, R. Grossi, V. Mäkinen, and A. I. Tomescu, On the complexity of exact pattern matching in graphs: Determinism and zig-zag matching, 2019.

N. Francis, A. Green, P. Guagliardo, L. Libkin, T. Lindaaker et al., Cypher: An evolving query language for property graphs, Proceedings of the 2018 International Conference on Management of Data, SIGMOD Conference, pp.1433-1445, 2018.
URL : https://hal.archives-ouvertes.fr/hal-01803524

T. Gagie, G. Manzini, and J. Sirén, Wheeler graphs: A framework for bwtbased data structures, Theor. Comput. Sci, vol.698, pp.67-78, 2017.

G. Erik, S. Jouni, N. Adam, M. , H. Glenn et al., Variation graph toolkit improves read mapping by representing genetic variation in the reference, Nature Biotechnology, vol.36, p.875, 2018.

S. Hido and H. Kashima, A linear-time graph kernel, The Ninth IEEE International Conference on Data Mining, pp.179-188, 2009.

R. Impagliazzo and R. Paturi, On the complexity of k-sat, Journal of Computer and System Sciences, vol.62, issue.2, pp.367-375, 2001.

C. Jain, H. Zhang, Y. Gao, and S. Aluru, On the Complexity of Sequence to Graph Alignment. bioRxiv, vol.84, p.15, 2019.

D. E. Knuth, J. H. Morris, and V. R. Pratt, Fast Pattern Matching in Strings, SIAM Journal on Computing, vol.6, issue.2, pp.323-350, 1977.

U. Manber and S. Wu, Approximate string matching with arbitrary costs for text and hypertext, IAPR Workshop on Structural and Syntactic Pattern Recognition, pp.22-33, 1992.

G. Navarro, Improved approximate pattern matching on hypertext, Theoretical Computer Science, vol.237, issue.1-2, pp.455-463, 2000.

K. Park and D. Kim, String matching in hypertext, 6th Symposium on Combinatorial Pattern Matching, p.318, 1995.

E. Prud, &. , and A. Seaborne, SPARQL query language for RDF. World Wide Web Consortium, Recommendation REC-rdf-sparql-query-20080115, 2008.

M. Rautiainen and T. Marschall, Aligning sequences to general graphs in O(V +mE) time. bioRxiv, pp.216-127, 2017.

M. A. Rodriguez, The gremlin graph traversal machine and language (invited talk), Proceedings of the 15th Symposium on Database Programming Languages, pp.1-10, 2015.

K. Schneeberger, J. Hagmann, S. Ossowski, N. Warthmann, S. Gesing et al., Simultaneous alignment of short reads against multiple genomes, Genome Biology, vol.10, p.98, 2009.

C. Shi, Y. Li, J. Zhang, Y. Sun, and P. S. Yu, A survey of heterogeneous information network analysis, IEEE Trans. Knowl. Data Eng, vol.29, issue.1, pp.17-37, 2017.

J. Sirén, N. Välimäki, and V. Mäkinen, Indexing graphs for path queries with applications in genome research, IEEE/ACM Trans. Comput. Biol. Bioinformatics, vol.11, issue.2, pp.375-388, 2014.

K. Vaddadi, N. Sivadasan, K. Tayal, and R. Srinivasan, Sequence alignment on directed graphs, 2017.

J. Yang and J. Leskovec, Defining and evaluating network communities based on ground-truth, 12th IEEE International Conference on Data Mining, ICDM 2012, pp.745-754, 2012.