Displaying similar documents to “Efficient validation and construction of border arrays and validation of string matching automata”

Forbidden factors and fragment assembly

F. Mignosi, A. Restivo, M. Sciortino (2001)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

In this paper methods and results related to the notion of minimal forbidden words are applied to the fragment assembly problem. The fragment assembly problem can be formulated, in its simplest form, as follows: reconstruct a word w from a given set I of substrings (fragments) of a word w . We introduce an hypothesis involving the set of fragments I and the maximal length m ( w ) of the minimal forbidden factors of w . Such hypothesis allows us to reconstruct uniquely the word w from the set...

A sparse dynamic programming algorithm for alignment with non-overlapping inversions

Alair Pereira Do Lago, Ilya Muchnik, Casimir Kulikowski (2005)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity:

Alignment of sequences is widely used for biological sequence comparisons, and only biological events like mutations, insertions and deletions are considered. Other biological events like inversions are not automatically detected by the usual alignment algorithms, thus some alternative approaches have been tried in order to include inversions or other kinds of rearrangements. Despite many important results in the last decade, the complexity of the problem of alignment with inversions...

A new practical linear space algorithm for the longest common subsequence problem

Heiko Goeman, Michael Clausen (2002)

Kybernetika

Similarity:

This paper deals with a new practical method for solving the longest common subsequence (LCS) problem. Given two strings of lengths m and n , n ≥ m , on an alphabet of size s , we first present an algorithm which determines the length p of an LCS in O ( n s + min { m p , p ( n - p ) } ) time and O ( n s ) space. This result has been achieved before [ric94,ric95], but our algorithm is significantly faster than previous methods. We also provide a second algorithm which generates an LCS in O ( n s + min { m p , m log m + p ( n - p ) } ) time while preserving the linear space bound,...

Computing the prefix of an automaton

Marie-Pierre Béal, Olivier Carton (2000)

RAIRO - Theoretical Informatics and Applications - Informatique Théorique et Applications

Similarity: