Like this:

Chapter 7 explores divide-and-conquer algorithms, which are exactly what they sound like: breaking a problem into smaller problems, then finding a solution to the original problem using the solutions to the smaller problems.

Secion 7.1 revisits the Sorting problem from chapter 2, when we looked at an algorithm requiring quadratic time.  With the new divide-and-conquer approach, we will be able to find an algorithm requiring  time.  It looks like there are two keys to this divide-and-conquer sorting algorithm: first, if we’re given two sorted lists of integers it is relatively easy () to combine the two into one sorted list; second, a single-element list is, by definition, already sorted. Therefore it makes sense to construct a recursive algorithm which breaks down a list of integers into single-element lists, then take these sorted lists and repeatedly combine them to form the desired sorted list.

The algorithms themselves are fairly straightforward, and I can follow the first explanation of the  running time, but given the recurrence relation on page 230 I don’t think I could have come up with  on my own.  The second explanation is more intuitive, but the semantics in the last paragraph of section 7.1 seemed inconsistent.  He uses the term “recursion tree” to refer to the entire graph (which is not a mathematical tree, based on my understanding) in Figure 7.1, but goes on to state that it has 3 levels, which would indicate that either the Divide or the Conquer portion is the actual recursion tree.   Also, it looks like he uses “top level” (line 4) to refer to the level that is, strictly speaking, the second level from the bottom.  For those more familiar with computer science, is this typical?

In 7.2, the goal is to reduce the space complexity of the sequence alignment algorithm.  It is important to note that the algorithm presented will only compute the score of an alignment, not the alignment itself.  The implication seems to be that if we need the actual alignment, the space complexity remains .

Previously, in order to find the longest path in an edit graph, we needed the entire backtracking matrix, which again requires  space.  In order to do this, we need to come up with a way to find the longest path in the edit graph without using a backtracking matrix.  The new technique depends on the fact that we can find the middle vertex of the longest path without actually knowing the longest path – all we need to do is find the length of the longest path from the source to each vertex in the middle column (prefix(i), where i indexes each vertex in the middle column), and the length of the longest path from each vertex in the middle column to the sink (suffix(i)).  Then, since the length of the longest path from source to sink passing through vertex i in the middle column is length(i) = prefix(i) + suffix(i), maximizing length(i) over all i gives the length of the longest path from source to sink and, more importantly, determines the middle vertex in this path.

It took me a while to understand why this reduces the space requirement – i.e., why no backtracking matrix is required – but I think the key is that in finding this middle vertex, all we need are the lengths of two longest paths.  Since we don’t need the actual paths, we don’t need a backtracking matrix.

It’s easy to see that continuing this process – repeatedly finding middle vertices – will eventually give us each vertex in the longest path, hence the path itself.  Since this process must terminate, and each stage requires time equal to the rectangles to the left and right of the current middle column, the time required to compute the longest path is a partial sum of the geometric series with common ration 1/2 and first term equal to the area of the edit graph, nm, hence is less than 2nm.  So this algorithm requires  time.  We’re also told that it requires  space, since to compute the alignment scores in a column we only use the scores from the preceding column, so we only need 2n values.

Section 7.3 revisits the Longest Common Subsequence problem and develops an algorithm with running time, using block alignment and the Four-Russians technique.  As a side note, I looked up an article on the Four-Russians technique to find out why it’s called that – it turns out that the technique comes from a paper by four authors, but only one is Russian…

Block alignment of two DNA sequences – in our case, both are assumed to have length n – is simply dividing the grid formed by the sequences into subgrids of size t x t, where t divides n.  A block path is one which enters and leaves each square at the corners.  The block alignment problem is to find the longest block path through the graph.  To do this, we must find the alignment score for each of the squares, which means solving alignment problems, then piecing together the alignment scores to find the longest path.  Correct me if I’m wrong, but I think this ends up requiring time. However, we’re looking for an algorithm with subquadratic time.

This is where the Four-Russians technique comes in, and in order to apply it we must have .  The key lies in constructing minialignments and storing each alignment score in a lookup table – if we assume  (which, since it’s a scalar multiple I think that for running time this counts as ), this lookup table will have only n entries.  The running time calculations make use of :

Computing the score for each t x t minialignment takes time, so with n entries it takes running time.  Apparently, though, the overall running time is dominated by the accesses (could someone explain why there’s that number of accesses?), and each access takes time, so the overall running time is .

Advertisement