Hybridní vyhledávací algoritmy pro neurčité řetězce

Kód výsledku v 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>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Hybrid pattern-matching algorithms on indeterminate strings

Popis výsledku v původním jazyce

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.

Název v anglickém jazyce

Hybrid pattern-matching algorithms on indeterminate strings

Popis výsledku anglicky

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.

Druh

D - Stať ve sborníku

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

<a href="/cs/project/GA201%2F06%2F1039" target="_blank" >GA201/06/1039: Analýza a zpracování textu</a><br>

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2007

Kód důvěrnosti údajů

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Název statě ve sborníku

London Algorithmics and Stringology

ISBN

978-1-904987-41-3

ISSN

—

e-ISSN

—

Počet stran výsledku

19

Strana od-do

115-133

Název nakladatele

King's College

Místo vydání

London

Místo konání akce

London

Datum konání akce

6. 2. 2006

Typ akce podle státní příslušnosti

WRD - Celosvětová akce

Kód UT WoS článku

—