Data structure for representation of maximal repeats in strings

Diploma thesis home page

Author: Michal Linhard

Thesis advisor: Tibor Hegedus

Last changed: May 01 2007

Abstract

In this diploma thesis we present data structure for representation of maximal repeats in strings
- R3 tree, based on well known data structure - suffix tree. It requires O(n) space and it can be
constructed in O(n) time and space for string of length n over constant-sized alphabet. We formalize repeat in
string S as triple (p1, p2, l), where p1, p2 are two distinct positions in S and l is the length of the repeat.
We formulate query for maximal repeats in S in the form of the function findPairs(p1, k, S)
that returns all pairs (p2, l) such that (p1, p2, l) is maximal repeat with l >= k. R3 tree allows
computation of findPairs queries in optimal time O(z), where z is the number of found pairs. We
also describe design and functionality of R3lib - library written in C, for finding maximal repeats
in arbitrary binary data, that works with proposed structure.

Documents

References

1. Brenda S. Baker, On finding duplication in strings and software, technical report, AT&T Bell Laboratories, February, 1993 [source] [.ps.gz]
2. Manber, U., & Myers, G. (1993). Suffix arrays: A new method for on-line string searches. SIAM Journal on Computing, 22(5), 935--948 [source] [.ps]
3. E. Ukkonen: On-line construction of suffix-trees. Algorithmica 14 (1995), 249-260 [source] [.pdf]
4. M. Crochemore, W. Rytter: Text Algorithms. Oxford University Press, New York, 1994 [source]
5. P. Ko and S. Aluru, "Space-efficient linear time construction of suffix arrays," Combinatorial Pattern Matching, pp. 200-210, 2003. [source] [.pdf]
6. Juha Kärkkäinen and Peter Sanders: Simple linear work suffix array construction, in Proc. 30th International Colloquium on Automata, Languages and Programming (ICALP '03). LNCS 2719, Springer, 2003, pp. 943-955 [source] [.pdf]
7. S. Kurtz and C. Schleiermacher: REPuter: Fast Computation of Maximal Repeats in Complete Genomes, Bioinformatics, 15(5):426-427, 1999. [source][.pdf]
8. S. Kurtz, and E. Ohlebusch: Replacing Suffix Trees with Enhanced Suffix Arrays, M.I. Abouelhoda, Journal of Discrete Algorithms, 2:53-86, 2004. [source][.pdf]
9. M.I. Abouelhoda, S. Kurtz, and E. Ohlebusch: The Enhanced Suffix Array and its Applications to Genome Analysis, In Proceedings of the Second Workshop on Algorithms in Bioinformatics, pages 449-463. Lecture Notes in Computer Science 2452, Springer-Verlag, 2002. [source][.pdf]
10. R. Dementiev, J. Mehnert, and J. Kärkkäinen: Better External Memory Suffix Array Construction. In Workshop on Algorithm Engineering & Experiments, Vancouver, 2005. [source][.pdf]
11. Jens Mehnert: External Memory Suffix Array Construction, Diploma Thesis [source][.pdf]
12. R. Dementiev, L. Kettner, P. Sanders: Stxxl: Standard Template Library for XXL Data Sets. Technical Report 2005/18, Fakultät für Informatik, University of Karlsruhe [source][.pdf]
13. Stefan Burkhardt, Juha Kärkkäinen: Fast Lightweight Suffix Array Construction and Checking, CPM 2003, LNCS 2676, pp. 55–69, 2003 [.pdf]
14. Klaus-Bernd Schurmann, Jens Stoye: An Incomplex Algorithm for Fast Suffix Array Construction, Proceedings of the 7th Workshop on Algorithm Engineering and Experiments, 2005 [.pdf]
15. S. Lee, K. Park, Efficient Implementations of Suffix Array Construction Algorithms, Proceedings of the 15th Australasian Workshop on Combinatorial Algorithms, pp. 64-72, 2004 [.ps]
16. D. K. Kim, J. S. Sim, H. Park, K. Park, Linear-time construction of suffix arrays, Proceedings of the 14th Annual Symposium on Combinatorial Pattern Matching, pp. 186-199, 2003 [.ps]
17. Juha Kärkkäinen, Peter Sanders and Stefan Burkhardt, Linear work suffix array construction, Journal of ACM, 2005. [.pdf]
18. Giovanni Manzini, Two space saving tricks for linear time LCP computation, Technical Report TR-INF-2004-02-03-UNIPMN, [.pdf]
19. Moritz G. Maaß. Linear Bidirectional On-line Construction of Affix Trees. In Proceedings of the 11th Annual Symposium on Combinatorial Pattern Matching (CPM), volume 1848 of LNCS, pages 320-334. Springer, jun 2000 [source][.ps.gz]
20. J. Stoye. Affixbäume. Diploma thesis, 1995. [source][.ps]
21. J. Stoye. Affix trees. Diploma thesis, 1995. [source][.ps]
22. Shunsuke Inenaga, Hiromasa Hoshino, Ayumi Shinohara, Masayuki Takeda, Setsuo Arikawa: On-Line Construction of Symmetric Compact Directed Acyclic Word Graphs, Proc. 8th Symposium on String Processing and Information Retrieval (SPIRE2001), IEEE-CS Press, pp. 96-110, November 2001 [source][.pdf]

Relevant software

• http://stxxl.sourceforge.net/ - STXXL library for manipulation with huge data
• http://i10www.ira.uka.de/dementiev/esuffix/docu/index.html - external memory suffix array construction
• http://www.vmatch.de/ - The Vmatch large scale sequence analysis software
• http://mummer.sourceforge.net/ - MUMmer - "Ultra-fast alignment of large-scale DNA and protein sequences"

Links

• http://homepage3.nifty.com/wpage/links/suffix_arrays.html -list of publications about suffix array
• http://www.bio.ifi.lmu.de/lehre/WS2006/VLG_Sequ/ - some lecture
• http://theory.snu.ac.kr/research.html - list of some works
• http://www.brics.dk/DS/00/4/ - some thesis about Computational Biology
• http://www.cs.ucr.edu/~stelo/pattern.html - Pattern Matching Pointers
• http://www2.toki.or.id/book/AlgDesignManual/BOOK/BOOK5/NODE208.HTM#longestcommonsubstring - LCS problem
• http://nist.gov/dads/HTML/longestCommonSubstring.html - LCS problem
• http://www.cs.helsinki.fi/u/ukkonen/Erice2005.ppt - lecture about suffix trees and arrays
• http://www.stringology.org/ - research group working on the stringology
• http://www.cse.msu.edu/~torng/Classes/Archives/cse960.01/Lectures/SuffixTreeApplications.ppt - suffix tree applications
• http://wwwmayr.informatik.tu-muenchen.de/personen/maass/at_slides.pdf - lecture about affix trees
• http://www.techfak.uni-bielefeld.de/~stoye/talks/20060517birkenfeld.pdf - lecture: Suffix trees, Affix trees, and some of their applications

Changelog

May 01 2007 - Final version of diploma thesis added.

April 30 2007 - Pre-Final version of diploma thesis added.

April 25 2007 - Link added.

April 24 2007 - New working version of thesis.

April 23 2007 - New working version of thesis.

April 10 2007 - R3lib project page link added, new working version of diploma thesis.

March 22 2007 - New version of diploma thesis home page in english. Old version can be found here : Old version of page.