Themenübersicht
Exact matching Problem
- Boyer-Moore Algorithmus:
- Knuth-Morris-Pratt Algorithmus:
- D.E. Knuth, J. Morris, and V.R.
Pratt. Fast pattern matching in strings. SIAM Journal on
Computing, 6(1):323-360, 1977.
- [Gusfield]: S. 23 -29
- [Cormen]: S. 868 ff
Exact set matching Problem:
- Aho-Corasick:
- [Gusfield]: S. 52-61
- A.V. Aho and M.J. Corasick. Efficient string matching: An aid to
bibliographic search. Comm. ACM, 18(6):333-340, 1975
Seminumerical matching
- Rabin-Karp Algorithmus:
- [Gusfield]: S. 77 - 84
- [Cormen]: S. 857 ff
- R.M. Karp and M.O. Rabin. Efficient randomized pattern-matching
algorithms. IBM Journal of Res. and Dev., pages 249--260, 1987.
- grep:
- Sun Wu and Udi Manber. Fast
Text Searching With Errors. Tech. Report TR-9111. University of
Arizona, Department of Computer Science 1991.
[Gusfield]: S. 65, 66, 70 - 73
Suche mit Automaten
- String matching mit endlichen Automaten
- [Cormen]: 34.3, S. 862 -868
Schnelle Heuristiken
- FASTA
- [Gusfield] 15.5, S. 377ff
- Lipman DJ, Pearson WR. Rapid
and sensitive protein similarity searches. Science
1985;227:1435--1441.
- D. Lipman and W. Pearson. Improved
tools for biological sequence comparison. Proceedings of the
National Academy of Science USA, 85:2444--2448, 1988.
- BLAST
- [Gusfield] 15.6, S. 379ff
- S. F. Altschul, W. Gish, W.
Miller, E. W. Myers, and D. J. Lipman. Basic Local Alignment Search
Tool. Journal of Molecular Biology, 215:403--410, 1990.
- Altschul SF, Madden TL, Schaffer AA,
Zhang J, Zhang Z, Miller W, Lipman DJ. Gapped BLAST and PSI-BLAST: a new
generation of protein database search programs. Nucleic Acids
Res. 1997 Sep 1;25(17):3389-402
Suffix Baum und seine Anwendungen
- Einfuehrung Suffixbaum
- [Gusfield]
- Kap.5: S. 89 - 93, Einfuehrung und naive Konstruktion
- Kap.6.5: S. 116ff, Praktische Implementierungsdetails
- APL 1: S. 122 Exact string matching
Anwendungen (alle aus [Gusfield]):
- APL 4: S. 125 Longest common substring
- 7.11/APL 11: S. 138ff Maximal repeat
- APL 13: S. 149- 155 Suffix Arrays
- Ziv-Lempel Kompressionsalgorithm
- [Gusfield]: APL16, S. 164ff
- http://citeseer.nj.nec.com/ziv77universal.html
Literatur:
[Gusfield]: Algorithms on Strings,
Trees, and Sequences: Computer
Science and Computational Biology, D.Gusfield, Cambridge
Press, New York, 1997
[Cormen]: Introduction to
Algorithms, T.H. Cormen, C.E. Leiserson, R.L. Rivest, MIT Press, Cambridge, MA, 1990.