Ruzzo–Tompa algorithm

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

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

The Ruzzo–Tompa algorithm has applications in bioinformatics[2], web scraping[3], and information retrieval[4].

Applications[edit]

Bioinformatics[edit]

The Ruzzo–Tompa algorithm has been used in Bioinformatics tools to study biological data. The problem of finding 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.[2]

The algorithm is used in sequence alignment which is used as a method of identifying similar DNA, RNA, or protein sequences. Accounting for the ordering of pairs of high-scoring subsequences in two sequences creates better sequence alignments. This is because the biological model suggests that separate high-scoring subsequence pairs arise from insertions or deletions within a matching region. Requiring consistent ordering of high-scoring subsequence pairs increases their statistical significance.[2]

Web scraping[edit]

The Ruzzo–Tompa algorithm is used in Web scraping to extract information from web pages. Pasternack and Roth proposed a method for extracting important blocks of text from HTML documents. The web pages are first tokenized and the score for each token is found using local, token-level classifiers. A modified version of the Ruzzo–Tompa algorithm is then used to find the k highest-valued subsequences of tokens. These subsequences are then used as predictions of important blocks of text in the article.[3]

Information retrieval[edit]

The Ruzzo–Tompa algorithm has been used in Information retrieval search algorithms. Liang et al. proposed a data fusion method to combine the search results of several microblog search algorithms. In their method, the Ruzzo–Tompa algorithm is used detect bursts of information.[4]

Problem definition[edit]

The problem of finding all maximal subsequences is defined as follows: Given a list of real numbered scores , find the list of contiguous subsequences that gives the great total score, where the score of each subsequence . The subsequences must be disjoint (non-overlapping) and have a positive score.

Other algorithms[edit]

There are several approaches to solving the all maximal scoring subsequences problem. A natural approach is to use existing, linear time algorithms to find the maximum subsequence (see maximum subarray problem) and then recursively find the maximal subsequences to the left and right of the maximum subsequence. The analysis of this algorithm is similar to that of Quicksort: The maximum subsequence could be small in comparison to the rest of sequence, leading to a running time of in the worst case.

Algorithm[edit]

This animation shows the Ruzzo–Tompa algorithm running with an input sequence of 11 integers each represented by a line segment in the graph. Segments with bold lines represent maximal segments found so far. The animation shows the state of and at each step. Below that it shows the current state the algorithm which correspond to steps 1–4 in the Algorithm section of this page. The red highlight shows the algorithm finding a value for in steps 1 and 3. If the value of satisfies the inequalities in those steps the highlight turns green. At the end of the animation the maximal subsequences will be bolded and displayed in .

The standard implementation of the Ruzzo–Tompa algorithm runs in 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 of disjoint subsequences. For each subsequence , record the cumulative total of all scores up to but not including the leftmost score of , and the total up to and including the rightmost score of .
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 of length one that is then integrated into the list by the following process.
  1. The list is searched from right to left for the maximum value of satisfying
  2. If there is no such , then add to the end of the list.
  3. If there is such a , and , then add to the end of the list.
  4. Otherwise (i.e., there is such a j, but ), extend the subsequence to the left to encompass everything up to and including the leftmost score in . Delete subsequences from the list, and append to the end of the list. Reconsider the newly extended subsequence (now renumbered ) as in step 1.
Once the end of the input is reached, all subsequences remaining on the list are maximal.[1]

The following Python code implements the Ruzzo–Tompa algorithm:

 1 def ruzzo_tompa(scores):
 2     """Ruzzo–Tompa algorithm."""
 3     k = 0
 4     total = 0
 5     # Allocating arrays of size n
 6     I, L, R, Lidx = [[0] * len(scores) for _ in range(4)]
 7     for i, s in enumerate(scores):
 8         total += s
 9         if s > 0:
10             # store I[k] by (start,end) indices of scores
11             I[k] = (i, i + 1)
12             Lidx[k] = i
13             L[k] = total - s
14             R[k] = total
15             while True:
16                 maxj = None
17                 for j in range(k - 1, -1, -1):
18                     if L[j] < L[k]:
19                         maxj = j
20                         break
21                 if maxj is not None and R[maxj] < R[k]:
22                     I[maxj] = (Lidx[maxj], i + 1)
23                     R[maxj] = total
24                     k = maxj
25                 else:
26                     k += 1
27                     break
28     # Getting maximal subsequences using stored indices
29     return [scores[I[l][0]:I[l][1]] for l in range(k)]

References[edit]

  1. ^ a b Ruzzo, Walter L.; Martin, Tompa (1999). "A Linear Time Algorithm for Finding All Maximal Scoring Subsequences". Proceedings. International Conference on Intelligent Systems for Molecular Biology: 234–241. PMID 10786306.
  2. ^ a b c Karlin, S; Altschul, SF (Jun 15, 1993). "Applications and statistics for multiple high-scoring segments in molecular sequences". Proceedings of the National Academy of Sciences of the United States of America. 90 (12): 5873–5877. doi:10.1073/pnas.90.12.5873. PMC 46825. PMID 8390686.
  3. ^ a b Pasternack, Jeff; Roth, Dan (2009). Extracting Article Text from the Web with Maximum Subsequence Segmentation. Proceedings of the 18th International Conference on World Wide Web. pp. 971–980. doi:10.1145/1526709.1526840. ISBN 9781605584874.
  4. ^ a b Liang, Shangsong; Ren, Zhaochun; Weerkamp, Wouter; Meij, Edgar; de Rijke, Maarten (2014). Time-Aware Rank Aggregation for Microblog Search. Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management. pp. 989–998. CiteSeerX 10.1.1.681.6828. doi:10.1145/2661829.2661905. ISBN 9781450325981.