Perhaps a quite old book, but very relevant for any bioinformatician! Have recently read Gusfields 'algorithms on strings', I think this one is the more relevant text on algorithms for biological sequences. The reason for this is that for working with real-life data a sound probabilistic framework is required! Anyone familiar with the standard machine learning tools will likely see how to link these methods and how to apply them for building classifiers for example.
The introduction on dynamics programming and HMM is good, though very descriptive. Might be necessary to consult additional material if you want to implement these tools yourself.
The part about inferring phylogenies was interesting and shows the difficulty of the field.
The last part about stochastic grammers and RNA was, to me extremely fascinating. The authors present some world which really goes at the heart of bioinformatics (or language modelling in general) and what we can and cannot do. A pity this section is only two chapters.