Generalized and Weighted Strings: Repetitions and Pattern Matching

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F68407700%3A21230%2F04%3A00109860" target="_blank" >RIV/68407700:21230/04:00109860 - isvavai.cz</a>

Výsledek na webu

—

DOI - Digital Object Identifier

—

Jazyk výsledku

angličtina

Název v původním jazyce

Generalized and Weighted Strings: Repetitions and Pattern Matching

Popis výsledku v původním jazyce

Generalized and weighted strings are special strings capable of expressing variability and uncertainity of appearance of a symbol in a given position. These types of strings are mainly used in molecular biology. In this paper we present a finite state automata approach for solving various pattern matching problems. We present the Generalized Factor Automaton (GFA), a novel structure for indexing generalized strings. We show how to use GFA for substring searching and searching maximum repeating factors in generalized strings. Finally, we show how to transform the finite automaton for a given pattern matching problem on strings to an automaton for the pattern matching problem on generalized strings.

Název v anglickém jazyce

Generalized and Weighted Strings: Repetitions and Pattern Matching

Popis výsledku anglicky

Generalized and weighted strings are special strings capable of expressing variability and uncertainity of appearance of a symbol in a given position. These types of strings are mainly used in molecular biology. In this paper we present a finite state automata approach for solving various pattern matching problems. We present the Generalized Factor Automaton (GFA), a novel structure for indexing generalized strings. We show how to use GFA for substring searching and searching maximum repeating factors in generalized strings. Finally, we show how to transform the finite automaton for a given pattern matching problem on strings to an automaton for the pattern matching problem on generalized strings.

Druh

C - Kapitola v odborné knize

CEP obor

IN - Informatika

OECD FORD obor

—

Projekt

—

Návaznosti

Z - Vyzkumny zamer (s odkazem do CEZ)

Rok uplatnění

2004

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 knihy nebo sborníku

Texts in Algorithmics, Volume 2 - String Algorithmics

ISBN

1-904987-02-8

Počet stran výsledku

24

Strana od-do

225-248

Počet stran knihy

251

Název nakladatele

King's College

Místo vydání

London

Kód UT WoS kapitoly

—