Ruzzo–Tompa algorithm: Difference between revisions

Revision as of 23:21, 16 February 2023

Revision as of 15:23, 17 February 2023

Line 1:

The '''Ruzzo–Tompa algorithm''' or the '''RT algorithm'''<ref name=":0">{{Cite journal |last=Spouge |first=John L. |last2=Ramírez |first2=Leonardo Mariño |last3=Sheetlin |first3=Sergey L. |date=2014 |title=Searching for repeats, as an example of using the generalised Ruzzo-Tompa algorithm to find optimal subsequences with gaps |url=http://www.inderscience.com/link.php?id=62991 |journal=International Journal of Bioinformatics Research and Applications |language=en |volume=10 |issue=4/5 |pages=384 |doi=10.1504/IJBRA.2014.062991 |issn=1744-5485 |pmc=PMC41355184135518 |pmid=24989859}}</ref> is a [[Time complexity#Linear time|linear-time]] [[algorithm]] for finding all non-overlapping, contiguous, maximal scoring subsequences in a sequence of real numbers.<ref name="ruzzo_tompa">{{cite journal|last1=Ruzzo|first1=Walter L.|last2=Martin|first2=Tompa|title=A Linear Time Algorithm for Finding All Maximal Scoring Subsequences|journal=Proceedings. International Conference on Intelligent Systems for Molecular Biology|date=1999|pages=234–241|pmid=10786306|isbn=9781577350835|url=https://dl.acm.org/citation.cfm?id=660812|ref=ruzzo-tompa}}</ref> The Ruzzo–Tompa algorithm was proposed by Walter L. Ruzzo and Martin Tompa.<ref>{{Cite web |title=A Linear Time Algorithm for Finding All Maximal Scoring Subsequences |url=https://homes.cs.washington.edu/~ruzzo/papers/maxseq.pdf}}</ref> This algorithm is an improvement over previously known quadratic time algorithms.<ref name=":0" /> 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]],<ref name="karlin" /> [[web scraping]],<ref name="pasternack">{{cite book|last1=Pasternack|first1=Jeff|last2=Roth|first2=Dan|title=Extracting Article Text from the Web with Maximum Subsequence Segmentation|journal=Proceedings of the 18th International Conference on World Wide Web|date=2009|pages=971–980|doi=10.1145/1526709.1526840|isbn=9781605584874|s2cid=346124}}</ref> and [[information retrieval]].<ref name="liang">{{cite book|last1=Liang|first1=Shangsong|last2=Ren|first2=Zhaochun|last3=Weerkamp|first3=Wouter|last4=Meij|first4=Edgar|last5=de Rijke|first5=Maarten|title=Time-Aware Rank Aggregation for Microblog Search|journal=Proceedings of the 23rd ACM International Conference on Conference on Information and Knowledge Management|date=2014|pages=989–998|doi=10.1145/2661829.2661905|isbn=9781450325981|citeseerx=10.1.1.681.6828|s2cid=14287901}}</ref>