Paper Info
Title
Finding common motifs with gaps using finite automata
Abstract
We present an algorithm that uses finite automata to find the common motifs with gaps occurring in all strings belonging to a finite set S = {S1,S2,...,Sr}. In order to find these common motifs we must first identify the factors that exist in each string. Therefore the algorithm begins by constructing a factor automaton for each string Si. To find the common factors of all the strings, the algorithm needs to gather all the factors from the strings together in one data structure and this is achieved by computing an automaton that accepts the union of the above-mentioned automata. Using this automaton we are able to create a new factor alphabet. Based on this factor alphabet a finite automaton is created for each string Si that accepts sequences of all non overlapping factors residing in each string. The intersection of the latter automata produces the finite automaton which accepts all the common subsequences with gaps over the factor alphabet that are present in all the strings of the set S = {S1,S2,...,Sr}. These common subsequences are the common motifs of the strings.
Year
DOI
Venue
2006
10.1007/11812128_8
CIAA
Keywords
Field
DocType
finite automaton,above-mentioned automaton,factor alphabet,common factor,finite set,common motif,common subsequence,factor automaton,string si,latter automaton,finite automata,data structure
Discrete mathematics,Two-way deterministic finite automaton,Combinatorics,Nondeterministic finite automaton,Deterministic automaton,Deterministic finite automaton,Levenshtein automaton,Directed acyclic word graph,Mathematics,Büchi automaton,ω-automaton
Conference
Volume
ISSN
ISBN
4094
0302-9743
3-540-37213-X
Citations 
PageRank 
References 
223
7.85
5
Authors
5
Search Limit
100223
Name
Order
Citations
PageRank
Pavlos Antoniou135317.04
Jan Holub232719.17
Costas S. Iliopoulos31534167.43
Bořivoj Melichar427617.21
Pierre Peterlongo539020.28