If you like definition-theorem-proof-example and exercise books, Gusfield's book is the definitive text for string algorithms. The algorithms are abstracted from their biological applications, and the book would make sense without reading a single page of the biological motivations. Gusfield aims his book at readers who are fluent in basic algorithms and data structures (at the level of Cormen, Leisersohn and Rivest's excellent text). The exercises are wonderfully illustrative, being neither trivial nor impossible.
All of the major exact string algorithms are covered, including Knuth-Morris-Pratt, Boyer-Moore, Aho-Corasick and the focus of the book, suffix trees for the much harder probem of finding all repeated substrings of a given string in linear time. In addition to exact string matching, there are extensive discussions of inexact matching. Even the discussions of widely known topics like dynamic programming for edit distance are insightful; for instance, we find how to easily cut space requirements from quadratic to linear. There is also a short chapter on semi-numerical matching methods, which are also of use in information retrieval applications. Inexact matching is extended to the threshold all-against-all problem, which finds all substrings of a string that match up to a given edit distance threshold. The theoretical development concludes with the much more difficult problem of aligning multiple sequences with ultrametric trees, with applications to phylogenetic alignment for evolutionary trees (an approach that has also been applied to the evolution of natural languages).
Note that there is no discussion of statistical string matching. For that, Durbin, Eddy, Krogh and Mitchison's "Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acides" is a good choice, or for those more interested in language than biology, Manning and Schuetze's "Statistical Natural Language Processing". There is also no information on more structured string matching models such as context-free grammars, as are commonly used to analyze RNA folding or natural language syntax. Luckily, Durbin et al. and Manning and Schuetze also provide excellent coverage of these higher-order models in their books.
This book is not about efficient implementation. If you need to build these algorithms, you'll also need to know how to write efficient code and tune it for your needs. This is an algorithms book, pure and simple.
As a computer scientist, I found the discussions of computational biology to be more enlightening than in other textbooks on similar topics such as Durbin et al., because Gusfield does not assume the reader has any background in cellular biology. Instead, he provides his own clear and gentle introductions illustrated with algorithms, applications, open problems and extensive references. Like most Cambridge University Press books, this one is beautifully typeset and edited.
Enjoy fast, free delivery, exclusive deals, and award-winning movies & TV shows with Prime
Try Prime
and start saving today with fast, free delivery
Loading your book clubs
There was a problem loading your book clubs. Please try again.
Not in a club? Learn more
Join or create book clubs
Choose books together
Track your books
Bring your club to Amazon Book Clubs, start a new book club and invite your friends to join, or find a club that’s right for you for free.
Download the free Kindle app and start reading Kindle books instantly on your smartphone, tablet, or computer - no Kindle device required.
Read instantly on your browser with Kindle for Web.
Using your mobile phone camera - scan the code below and download the Kindle app.
Limited-Time Offer
3 Months FREE of Audible Premium Plus. Get this deal
Frequently bought together
$88.22
Get it as soon as Tuesday, Feb 13
Only 4 left in stock - order soon.
Total price:
To see our price, add these items to your cart.
Choose items to buy together.
Customers who viewed this item also viewed
Page 1 of 1 Start overPage 1 of 1
About the author
Follow authors to get new release updates, plus improved recommendations.
Reviews with images
Top reviews from the United States
There was a problem filtering reviews right now. Please try again later.
Reviewed in the United States on January 4, 2003
Reviewed in the United States on June 2, 2020
Reviewed in the United States on May 4, 2023
Reviewed in the United States on November 13, 2021
Images in this review
Top reviews from other countries
Mr. S. Fernea
good price and recommended
Reviewed in the United Kingdom on March 18, 2015
