String matching and bioinformatics
The list of open problems in bioinformatics: string matching is outlined in Some string matching problems from Bioinformatics which still need better solutions this article is old, but problems remain.
There is also presentation Analytic pattern matching: From DNA to Twitter.

Some are related to graph automorphism (so may remain open for a bit longer) for example:   


  Extend String Pattern Matching to Graph Pattern Matching, that is, replace the text T by a graph G and find the number of occurrences of a given subgraph/pattern g in G for different models of graph G generation.