Approximate String Matching with Variable Length Don't Care Characters

Tatsuya AKUTSU  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E79-D   No.9   pp.1353-1354
Publication Date: 1996/09/25
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: LETTER
Category: Algorithm and Computational Complexity
Keyword: 
pattern matching,  approximate string matching,  algorithms,  DNA sequence analysis,  

Full Text: PDF>>
Buy this Article




Summary: 
This paper presents an O(mn log n) time algorithm for an approximate string matching problem, in which a pattern string may contain variable length don't care characters. This problem is important for searching DNA sequences or amino acid sequences.