Finding common label sequences in a directed acyclic graph

I have a directed acyclic graph with ~250k nodes, each node has one of about 100 symbols as label. Letting a word be the sequence of n symbols that corresponds to a path containing n nodes in the graph, how can I find the most common words? What known algorithms should I study?

An interesting extension is to let edges also have one of about 100 symbols (the set of edge symbols does not intersect the set of node symbols) as label, redefining a word to be the sequence of length n+(n-1) symbols that corresponds to a path containing n nodes and n-1 edges.

Reading tips and wikipedia links are appreciated as well as more elaborate answers.

• This is similar to a hidden Markov model. The directed acyclic graph is analogous to the underlying Markov chain, and the symbols are analogous to the visible output. There's been a lot of research on hidden Markov models, although I don't know of any that addresses your question. If you took a random walk on the graph for a while, and observed the next n symbols, your question would indeed be about hidden Markov models. If you're looking for a uniform distribution on paths of length n, this is a somewhat different question. – Peter Shor Mar 12 '11 at 17:02