Fast Pattern-Matching on Indeterminate Strings

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F08%3A03130018" target="_blank" >RIV/68407700:21230/08:03130018 - isvavai.cz</a>

Result on the web

—

DOI - Digital Object Identifier

—

Result language

angličtina

Original language name

Fast Pattern-Matching 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. Indeterminate strings can arise inDNA and amino acid sequences as well as in cryptological applications and the analysis of musical texts. In this paper we describe fast algorithms for finding all occurrences of a pattern p in a given text x, where either or both of p and x can be indeterminate. Our algorithms are based on the Sunday variant of the Boyer-Moore pattern-matching algorithm, one of the fastest exact pattern-matching algorithms known. The methodology we describe applies more generally to all variants of Boyer-Moore (such asHorspool's, for example) that depend only on calculation of the ``rightmost shift'' array: our method therefore assumes that the alphabet is indexed (essentially, an integer alphabet), a requirement normally satisfied in practice.

Czech name

Rychlé vyhledávání v neurčitých řetězcích

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ů. V tomto článku popisujeme rychlé algoritmy hledající všechny výskyty vzorků p v daném textu x, kde x a/nebo p mohou být neurčité.

Type

J_x - Unclassified - Peer-reviewed scientific article (Jimp, Jsc and Jost)

CEP classification

IN - Informatics

OECD FORD branch

—

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)

Publication year

2008

Confidentiality

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

Name of the periodical

Journal of Discrete Algorithms

ISSN

1570-8667

e-ISSN

—

Volume of the periodical

6

Issue of the periodical within the volume

1

Country of publishing house

DE - GERMANY

Number of pages

14

Pages from-to

—

UT code for WoS article

—

EID of the result in the Scopus database

—