Content deleted Content added
No edit summary |
No edit summary |
||
Line 4:
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]]<ref>{{cite journal|last1=Karlin|first1=S|last2=Altschul|first2=SF|title=Applications and statistics for multiple high-scoring segments in molecular sequences|journal=Proceedings of the National Academy of Sciences of the United States of America|date=Jun 15, 1993|volume=90|issue=12|pages=5873-5877|pmid=8390686}}</ref>.
==Problem Definition==
==Algorithm==
There are several approaches to solving the all maximal scoring subsequences problem. A natural approach is to use existing, linear time algorithms (see [[maximum subarray problem]]) to find the maximum subsequence and then recursively find the maximal subsequences to the left and right of the maximum subsequence. This algorithm <math>O(n^2)</math> in the worst case. The analysis of this algorithm is similar to that of [[Quicksort]]: The maximum subsequence could be small in comparison to the rest of sequence. It is simple to build an example where this algorithm would be slow
The standard implementation of the Ruzzo-Tompa algorithm runs in <math>O(n)</math> time and uses <math>O(n)</math> space, where <math>n</math> 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:
| |||