Hybrid pattern-matching algorithms on indeterminate strings
The result's identifiers
Result code in IS VaVaI
<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F07%3A03130017" target="_blank" >RIV/68407700:21230/07:03130017 - isvavai.cz</a>
Result on the web
—
DOI - Digital Object Identifier
—
Alternative languages
Result language
angličtina
Original language name
Hybrid pattern-matching algorithms on indeterminate strings
Original language description
In a string x on an alphabet, a position i is said to be indeterminate iff x[i] may be any one of a specified subset of alphabet. A string x containing indeterminate positions is therefore also said to be indeterminate (or generalized). Indeterminate strings can arise in DNA and amino acid sequences as well as in cryptological applications and the analysis of musical texts. In this paper we describe a family of fast algorithms for finding all occurrences of a pattern p = p[1..m] in a given text x, whereeither or both of p and x can be indeterminate. Our algorithms are based on a very fast exact pattern-matching algorithm recently proposed by Franek-Jennings-Smyth that combines both Boyer-Moore-Sunday and Knuth-Morris-Pratt approaches. On many of the indeterminate pattern-matching cases tested, the new algorithms execute significantly faster than well-known bit-mapping algorithms based on the Unix utility agrep, while at the same time going beyond standard agrep's functionality.
Czech name
Hybridní vyhledávací algoritmy pro neurčité řetězce
Czech description
Pozice i v řetězci je neurčitá právě tehdy může-li x[i] obsahovat libovolnou podmnožinu vstupní abecedy. Řetězec obsahující tyto pozice se nazývá neurčitý. Neurčité řetězce se objevují DNA sekvencích stejně jako v kryptografických aplikacích a analýze hudebních textů. Naše algoritmy vycházejí z velmi rychlého algoritmu pro přesné vyhledávání nedávno představeného autory Franek-Jennings-Smyth, který kombinuje BMS a KMP přístupy.
Classification
Type
D - Article in proceedings
CEP classification
IN - Informatics
OECD FORD branch
—
Result continuities
Project
<a href="/en/project/GA201%2F06%2F1039" target="_blank" >GA201/06/1039: Text processing and analysis</a><br>
Continuities
Z - Vyzkumny zamer (s odkazem do CEZ)
Others
Publication year
2007
Confidentiality
S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů
Data specific for result type
Article name in the collection
London Algorithmics and Stringology
ISBN
978-1-904987-41-3
ISSN
—
e-ISSN
—
Number of pages
19
Pages from-to
115-133
Publisher name
King's College
Place of publication
London
Event location
London
Event date
Feb 6, 2006
Type of event by nationality
WRD - Celosvětová akce
UT code for WoS article
—