How can I rank paths through an HMM? I have a profile hidden Markov model that I use to identify all instances of a user-defined pattern of symbols in a long sequence of symbols. I use the Viterbi algorithm to find the most probable path that generates that long sequence of symbols, and it all works very well to identify the user's pattern. But I'm now interested in extending this, and identifying the k-most probable paths through my model that would generate some long sequence. Is there an existing algorithm to do this? I've come across something called the "1-best" or "k-best" algorithm, but I can't find much of anything describing it. 

I've also considered what I'm sure would be a heuristic, by finding the most probable path and then returning the neighbourhood around it. This would be found by iterating over each move between states in the most probable path, setting that particular step to 0, and resolving using Viterbi. This would obviously increase the run-time by a factor of (length of the path ~= length of pattern), which I suspect will be reasonable for my purposes.

Has anybody come across something like this, or can anybody see anything obviously wrong in my neighbourhood idea? I'd appreciate any feedback. As a note, this has been cross-posted to the Data Science forum.
Why not expand the HMM to a state graph and apply a k-shortest-paths algorithm to the graph? I have a recent survey on k-best enumeration that includes the k-shortest paths problem at http://bulletin.eatcs.org/index.php/beatcs/article/view/322.