Ruzzo–Tompa algorithm

The Ruzzo-Tompa algorithm is a linear time algorithm for finding all non-overlapping, contiguous, maximal scoring subsequences in a sequence of real numbers. This algorithm is an improvement over previously known quadratic time algorithms. The maximum scoring subsequence from the set produced by the algorithm is a solution to the Maximum subarray problem.

The problem of find disjoint maximal subsequences is of practical importance in the analysis of DNA. Maximal subsequences algorithms have been used in the identification of transmembrane segments and the evaluation of sequence homology.

Algorithm

The standard implementation of the Ruzzo-Tompa algorithm runs in $O(n)$ time and uses $O(n)$ space, where $n$ is the length of the list of scores. The algorithm uses dynamic programming to progressively build the final solution by incrementally solving progressively larger subsets of the problem. The description of the algorithm provided by Ruzzo and Tompa is as follows:

Read the scores left to right and maintain the cumulative sum of the scores read. Maintain an ordered list $I_{1},I_{2},...,I_{j}$ of disjoint subsequences. For each subsequence $I_{j}$, record the cumulative total $L_{j}$ of all scores up to but not including the leftmost score of $I_{j}$, and the total $R_{j}$ up to and including the rightmost score of $I_{j}$.

The lists are initially empty. Scores are read from left to right and are processed as follows. Nonpositive scores are require no special processing, so the next score is read. A positive score is incorporated into a new sub-sequence $I_{k}$ of length one that is then integrated into the list by the following process.

1. The list $I$ is searched from right to left for the maximum value of $j$ satisfying $L_{j}<L_{k}$
2. If there is no such $j$, then add $I_{k}$ to the end of the list.
3. If there is such a $j$, and $R_{j}\geq R_{k}$, then add $I_{k}$ to the end of the list.
4. Otherwise (i.e., there is such a j, but $R_{j}<R_{k}$), extend the subsequence $I_{k}$ to the left to encompass everything up to and including the leftmost score in $I_{j}$. Delete subsequences $I_{j},I_{j}+1,...,I_{k}-1$ from the list, and append $I_{k}$ to the end of the list. Reconsider the newly extended subsequence $I_{k}$ (now renumbered $I_{j}$) as in step 1.

Once the end of the input is reached, all subsequences remaining on the list $I$ are maximal.

The following Python code implements the Ruzzo-Tompa algorithm:

def RuzzoTompa(scores):
	k=0
	total = 0;
	# Allocating arrays of size n
	I,L,R,Lidx = [[0]*len(scores) for _ in range(4)]
	for i,s in enumerate(scores):
		total += s
		if s > 0:
			# store I[k] by (start,end) indices of scores
			I[k] = (i,i+1)
			Lidx[k] = i
			L[k] = total-s
			R[k] = total
			while(True):
				maxj = None
				for j in range(k-1,-1,-1):
					if L[j] < L[k]:
						maxj = j
						break;
				if maxj != None and R[maxj] < R[k]:
					I[maxj] = (Lidx[maxj],i+1)
					R[maxj] = total
					k = maxj
				else:
					k+=1
					break;
	# Getting maximal subsequences using stored indices
	return [scores[I[l][0]:I[l][1]] for l in range(k)]