Algorithms on strings, trees, and sequences

What Hacker News says

1. stillworksOct 2016
   > Also, why is it suddenly in vogue to bash TAOCP and CLRS?

   I guess for the same reasons people want to bash the current interviewing institution in place.

   Personally, I go with "it is what it is, deal with it if you want THAT job"

   Back to the context, I think I find CLRS much more approachable than TAOCP. It relies on pseudo-code and fairly simple mathematical symbology to formalise the algorithms it is treating.

   With TAOCP I have tried by can't get past the language of the imaginary CPU which it uses.

   Also, there are other simply excellent texts on Algorithms which I personally found much more useful than TAOCP (in decreasing order of "easiness")

   - Python Algorithms

   - The Algorithm Design Manual

   - CLRS

   - Algorithms in Java (somehow I found CLRS easier to follow than this)

   - And then I found this recently, "Algorithms on Strings,Trees and Sequences: Computer Science and Computational Biology" (one should have at least gone through the first two recommendations before starting with this one to make it easier to read this one)

   Disclaimer : I have a growing interest in learning Algorithms due to the requirements of interviews, however I have come to believe that the knowledge will go a long way.

   Show morethread
2. rickbradleyJun 2014
   This appears to be just reinvention of known algorithms on suffix trees. I recommend (and recommended as a comment on the original article) Dan Gusfield's book "Algorithms on Strings, Trees, and Sequences" which does a pretty thorough job of covering the relevant algorithms and data structures.
   thread
3. ahelwerApr 2012
   I've not read that textbook, but another excellent text is "Algorithms on Strings, Trees, and Sequences" by Dan Gusfield (http://www.amazon.ca/Algorithms-Strings-Trees-Sequences-Comp...). It has a strong bioinformatics leaning, so you learn all sorts of interesting near-real-world applications for the algorithms.

   Starts off talking about all the standard exact pattern matching algorithms, then moves on to suffix trees, then inexact matching, then finishes off with some advanced topics (that I have not read yet). Anyway, I'm really enjoying reading it and definitely recommend it.

   Show morethread
4. ahelwerMar 2012
   Does anyone have any advice for a computer science student seriously looking at the field of computational biology as a place for a career? I'd all but forgotten about biology until reading The Diamond Age right before seeing a video of ATP synthase in action [1].

   Now, I know stuff like that doesn't have a lot to do with what is done in computational biology, but it did fire the imagination. I'm working my way through Algorithms on Strings, Trees, and Sequences - Computer Science and Computational Biology by Dan Gusfield [2], and have implemented (with tests) all of the algorithms encountered thus far in addition to some of the exercises [3]. So far, I really enjoy all the material.

   Clearly reading a textbook is not enough to break into a field, but my degree is one in computer science and pure math with an internship in the HPC field. It's getting bit late to throw in a minor in biology or anything like that. However, all of my research-leaning friends in physics and such tell me that what everyone wants is someone who knows how to code, which is certainly something I know well. Is that similar to the situation in computational biology?

   Any other advice or knowledge of what it's like to work in the field would also be greatly appreciated :)

   [1] http://www.mrc-mbu.cam.ac.uk/node/448

   [2] http://books.google.ca/books/about/Algorithms_on_Strings_Tre...

   [3] https://github.com/ahelwer/IvoryTower/tree/master/ASTS

   Show morethread
5. palaiologosFeb 2025
   Hi, tool author here.

   Huffman coding is a static minimum-redundancy code. What this means is that it finds an optimal assignment of bit sequences to letters in the input alphabet (commonly US-ASCII or extensions). This however means that Huffman coding can not exploit redundancies that stem from the concrete sequence of characters. For example, you could easily predict that an `e` comes after `Th`, but Huffman coding can not know that.

   Hence after applying the Burrows-Wheeler transform you need to have some sort of a higher-order transform (i.e. a transform that considers more than just individual bytes) which somehow reaps from the changed distribution of the result of the algorithm. But we will get to that in a second.

   The joke here is that the Burrows-Wheeler transform is closely related to suffix trees and suffix arrays, which are often used in bioinformatics and HPC for full-text search. If you wanted to find a pattern of length `p` in a text of length `n`, if you already have a suffix tree of the original text, the search is linear in the length /of the pattern/ - i.e. O(p). The suffix tree stores all suffixes of a string in a compressed manner (i.e. it has a linear space overhead, approximately O(20n) as given by Gusfield, D. (1997). Algorithms on Strings, Trees and Sequences: Computer Science and Computational Biology. Cambridge University Press), so you can search for a word in it by simply traversing from the root node to an internal or leaf node by following a sequence of bytes that comprise the word.

   As such, a suffix tree (and equivalently suffix array and the BWT, which is trivially computed from a suffix array) form something which can be thought of as a static PPM model. Notably real world implementations of PPM use suffix trees as a part of their main storage data structure (e.g. PPMd). What this all means is that given a suffix tree, we can very cheaply give the probability distribution for the next byte that follows a given fixed-order sequence of bytes. This is nice, because then e.g. an order-2 predictor would be able to tell that `Th` is followed by `e` once enough data has been gathered.

   As you can probably guess, the more preceding bytes you know, the better will be your estimate for what is the most likely next byte. But the larger your context, the more expensive the searches and computations become due to pointer chasing in the suffix tree.

   So how do we remedy this? We notice that the Burrows-Wheeler transform essentially clusters similar contexts together, meaning that a low order predictor (= faster, simpler) on BWT compresses as well as a high order predictor (= slow, complicated) on the original data, at the cost of an extra transformation. This is viable, because the Burrows-Wheeler transform can be quickly computed and there have been recent advancements in running it on the GPU. So what this means is that bzip3 uses BWT + a low order predictor with an arithmetic coder to encode the bytes, meaning that it can make use of high order statistics for compression and performs comparably at a faster speed.

   Show morethread
6. mcswellMay 2024
   Dan Gusfield wrote a book in 1997 entitled "Algorithms on strings, trees and sequences: Computer Science and Computational Biology". We (what was then the Center for Advanced Study of Language at the University of Maryland) found some of the techniques described there to be useful in (natural) language analysis, particularly morphology and for comparing words in related languages.
   thread