Ruzzo–Tompa algorithm
 | This article, Ruzzo–Tompa algorithm, has recently been created via the Articles for creation process. Please check to see if the reviewer has accidentally left this template after accepting the draft and take appropriate action as necessary.
Reviewer tools: Inform author |
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]. There is an existing article on the Maximum subarray problem. The Ruzzo-Tompa algorithm is an improvement over previously known quadratic time algorithms.
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[2].
References
- ^ 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.
- ^ 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. PMID 8390686.