Search

Your search keyword '"Élise, Prieur-Gaston"' showing total 7 results
Start Over Author "Élise, Prieur-Gaston" Publisher hal ccsd
7 results on '"Élise, Prieur-Gaston"'

1. Efficient pattern matching in degenerate strings with the Burrows–Wheeler transform

Author

Thierry Lecroq, Yannick Guesnet, Jacqueline W. Daykin, Arnaud Lefebvre, Martine Léonard, Laurent Mouchard, Bruce W. Watson, Élise Prieur-Gaston, Richard Groult, Modélisation, Information et Systèmes - UR UPJV 4290 (MIS), Université de Picardie Jules Verne (UPJV), Equipe Traitement de l'information en Biologie Santé (TIBS - LITIS), Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Université Le Havre Normandie (ULH), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), and Normandie Université (NU)

Subjects
Burrows–Wheeler transform, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], 0102 computer and information sciences, 02 engineering and technology, 01 natural sciences, Theoretical Computer Science, Combinatorics, 0202 electrical engineering, electronic engineering, information engineering, Pattern matching, Time complexity, Mathematics, Discrete mathematics, Sequence, String (computer science), Degenerate energy levels, String, Computer Science Applications, Algorithm, 010201 computation theory & mathematics, Signal Processing, 020201 artificial intelligence & image processing, Degenerate, Alphabet, Constant (mathematics), Information Systems
Abstract

A degenerate or indeterminate string on an alphabet Σ is a sequence of non-empty subsets of Σ. Given a degenerate string t of length n and its Burrows–Wheeler transform we present a new method for searching for a degenerate pattern of length m in t running in O ( m n ) time on a constant size alphabet Σ. Furthermore, it is a hybrid pattern matching technique that works on both regular and degenerate strings. A degenerate string is said to be conservative if its number of non-solid letters is upper-bounded by a fixed positive constant q; in this case we show that the search time complexity is O ( q m 2 ) for counting the number of occurrences and O ( q m 2 + occ ) for reporting the found occurrences where occ is the number of occurrences of the pattern in t. Experimental results show that our method performs well in practice.

Published
2019
Full Text
View/download PDF

2. Abelian Powers and Repetitions in Sturmian Words

Author

Alessio Langiu, Élise Prieur-Gaston, Gabriele Fici, Filippo Mignosi, Thierry Lecroq, Jarkko Peltomäki, Arnaud Lefebvre, Università degli studi di Palermo - University of Palermo, Department of Informatics [King's College London], King‘s College London, Equipe Traitement de l'information en Biologie Santé (TIBS - LITIS), Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Université Le Havre Normandie (ULH), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Normandie Université (NU), Dipartimento di Informatica [Italy] (DI), Università degli Studi dell'Aquila (UNIVAQ), Fici, G., Langiu, A., Lecroq, T., Lefebvre, A., Mignosi, F., Peltomäki, J., Prieur-Gaston, É., Dipartimento di Energia, ingegneria dell'Informazione e modelli Matematici [Palermo] (DEIM), Université Le Havre Normandie (ULH), Normandie Université (NU)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Université Le Havre Normandie (ULH), and Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)

Subjects
FOS: Computer and information sciences, Fibonacci number, General Computer Science, Discrete Mathematics (cs.DM), Formal Languages and Automata Theory (cs.FL), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Computer Science - Formal Languages and Automata Theory, 0102 computer and information sciences, 01 natural sciences, Theoretical Computer Science, Combinatorics, FOS: Mathematics, Mathematics - Combinatorics, [INFO]Computer Science [cs], Number Theory (math.NT), 0101 mathematics, Abelian group, Continued fraction, Fibonacci word, ComputingMilieux_MISCELLANEOUS, Quotient, Mathematics, Mathematics - Number Theory, ta111, 010102 general mathematics, Computer Science (all), Sturmian word, Abelian period, Abelian power, Critical exponent, Lagrange constant, 010201 computation theory & mathematics, Bounded function, Exponent, Combinatorics (math.CO), Computer Science::Formal Languages and Automata Theory, Computer Science - Discrete Mathematics
Abstract

Richomme, Saari and Zamboni (J. Lond. Math. Soc. 83: 79-95, 2011) proved that at every position of a Sturmian word starts an abelian power of exponent $k$ for every $k > 0$. We improve on this result by studying the maximum exponents of abelian powers and abelian repetitions (an abelian repetition is an analogue of a fractional power) in Sturmian words. We give a formula for computing the maximum exponent of an abelian power of abelian period $m$ starting at a given position in any Sturmian word of rotation angle $\alpha$. vAs an analogue of the critical exponent, we introduce the abelian critical exponent $A(s_\alpha)$ of a Sturmian word $s_\alpha$ of angle $\alpha$ as the quantity $A(s_\alpha) = limsup\ k_{m}/m=limsup\ k'_{m}/m$, where $k_{m}$ (resp. $k'_{m}$) denotes the maximum exponent of an abelian power (resp.~of an abelian repetition) of abelian period $m$ (the superior limits coincide for Sturmian words). We show that $A(s_\alpha)$ equals the Lagrange constant of the number $\alpha$. This yields a formula for computing $A(s_\alpha)$ in terms of the partial quotients of the continued fraction expansion of $\alpha$. Using this formula, we prove that $A(s_\alpha) \geq \sqrt{5}$ and that the equality holds for the Fibonacci word. We further prove that $A(s_\alpha)$ is finite if and only if $\alpha$ has bounded partial quotients, that is, if and only if $s_{\alpha}$ is $\beta$-power-free for some real number $\beta$. Concerning the infinite Fibonacci word, we prove that: i) The longest prefix that is an abelian repetition of period $F_j$, $j>1$, has length $F_j( F_{j+1}+F_{j-1} +1)-2$ if $j$ is even or $F_j( F_{j+1}+F_{j-1} )-2$ if $j$ is odd, where $F_{j}$ is the $j$th Fibonacci number; ii) The minimum abelian period of any factor is a Fibonacci number. Further, we derive a formula for the minimum abelian periods of the finite Fibonacci words, Comment: To appear in Theoretical Computer Science

Published
2018
Full Text
View/download PDF

3. Practical fast on-line exact pattern matching algorithms for highly similar sequences

Author

Élise Prieur-Gaston, Nadia Ben Nsira, Thierry Lecroq, Equipe Traitement de l'information en Biologie Santé (TIBS - LITIS), Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Université Le Havre Normandie (ULH), Normandie Université (NU)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Université Le Havre Normandie (ULH), and Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)

Subjects
0301 basic medicine, Set (abstract data type), 03 medical and health sciences, 030104 developmental biology, Efficient algorithm, Computer science, Line (geometry), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Window (computing), Pattern matching, Variation (game tree), Algorithm, ComputingMilieux_MISCELLANEOUS
Abstract

With the advent of high-throughput sequencing technologies there are more and more genomic sequences of individuals of the same species available. These sequences only differ by a very small amount of variations. There is thus a strong need for efficient algorithms for performing fast pattern matching in such specific sets of sequences. In this paper we propose efficient practical algorithms that solve on-line exact pattern matching problem in a set of highly similar DNA sequences. We first present a method for exact single pattern matching when $k$ variations are allowed in a window which size is equal to the pattern length. We then propose an algorithm for exact multiple pattern matching when only one variation is allowed in a window which size is equal to the length of the longest pattern. Experimental results show that our algorithms, though not optimal in the worst case, have good performances in practice.

Published
2018

4. A survey of string orderings and their application to the Burrows–Wheeler transform

Author

Jacqueline W. Daykin, Arnaud Lefebvre, Richard Groult, Thierry Lecroq, Yannick Guesnet, Élise Prieur-Gaston, M. Léonard, Modélisation, Information et Systèmes - UR UPJV 4290 (MIS), Université de Picardie Jules Verne (UPJV), Equipe Traitement de l'information en Biologie Santé (TIBS - LITIS), Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Université Le Havre Normandie (ULH), Normandie Université (NU)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Université Le Havre Normandie (ULH), and Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)

Subjects
General Computer Science, Burrows–Wheeler transform, String (computer science), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], Suffix array, Binary number, 0102 computer and information sciences, 02 engineering and technology, Lexicographical order, 01 natural sciences, Theoretical Computer Science, law.invention, Combinatorics, Transformation (function), 010201 computation theory & mathematics, law, 0202 electrical engineering, electronic engineering, information engineering, Bijection, 020201 artificial intelligence & image processing, Word (computer architecture), ComputingMilieux_MISCELLANEOUS, Mathematics
Abstract

For over 20 years the data clustering properties and applications of the efficient Burrows–Wheeler transform have been researched. Lexicographic suffix-sorting is induced during the transformation, and more recently a new direction has considered alternative ordering strategies for suffix arrays and thus the transforms. In this survey we look at these distinctly ordered bijective and linear transforms. For arbitrary alphabets we discuss the V-BWT derived from V-order and the D-BWT based on lex-extension order. The binary case yields a pair of transforms, the binary Rouen B-BWT, defined using binary block order. Lyndon words are relevant to implementing the original transform; the new transforms are defined for analogous structures: V-words, indeterminate Lyndon words, and B-words, respectively. There is plenty of scope for further non-lexicographic transforms as indicated in the conclusion.

Published
2018
Full Text
View/download PDF

5. Three Strategies for the Dead-Zone String Matching Algorithm

Author

Jacqueline Daykin, Richard Groult, Yannick Guesnet, Thierry Lecroq, Arnaud Lefebvre, Martine Léonard, Laurent Mouchard, Élise Prieur-Gaston, Bruce Watson, Modélisation, Information et Systèmes - UR UPJV 4290 (MIS), Université de Picardie Jules Verne (UPJV), Equipe Traitement de l'information en Biologie Santé (TIBS - LITIS), Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Université Le Havre Normandie (ULH), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Normandie Université (NU), Jan Holub and Jan Ž\vdárek, and Lecroq, Thierry

Subjects
[INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], ComputingMilieux_MISCELLANEOUS
Abstract

International audience

Published
2017

6. A note on easy and efficient computation of full abelian periods of a word

Author

Arnaud Lefebvre, William F. Smyth, Thierry Lecroq, Gabriele Fici, Élise Prieur-Gaston, Equipe Traitement de l'information en Biologie Santé (TIBS - LITIS), Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Université Le Havre Normandie (ULH), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Normandie Université (NU), McMaster University [Hamilton, Ontario], Università degli studi di Palermo - University of Palermo, Department of Computing and Software (McMaster University), Fici, G., Lecroq, T., Lefebvre, A., Prieur-Gaston, É., Smyth, W., and Lecroq, Thierry

Subjects
FOS: Computer and information sciences, Discrete Mathematics (cs.DM), Formal Languages and Automata Theory (cs.FL), [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Elementary abelian group, Computer Science - Formal Languages and Automata Theory, 0102 computer and information sciences, 02 engineering and technology, [INFO] Computer Science [cs], 01 natural sciences, Rank of an abelian group, Combinatorics, Simple (abstract algebra), Computer Science - Data Structures and Algorithms, 0202 electrical engineering, electronic engineering, information engineering, Discrete Mathematics and Combinatorics, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], Abelian group, Hidden subgroup problem, Discrete Mathematics and Combinatoric, ComputingMilieux_MISCELLANEOUS, Mathematics, Combinatorics on word, Discrete mathematics, Applied Mathematics, 020206 networking & telecommunications, Abelian period, Text algorithm, Weak repetition, Free abelian group, Abelian power, Combinatorics on words, Design of algorithm, 010201 computation theory & mathematics, Word (computer architecture), Computer Science::Formal Languages and Automata Theory, Computer Science - Discrete Mathematics
Abstract

Constantinescu and Ilie (Bulletin of the EATCS 89, 167-170, 2006) introduced the idea of an Abelian period with head and tail of a finite word. An Abelian period is called full if both the head and the tail are empty. We present a simple and easy-to-implement $O(n\log\log n)$-time algorithm for computing all the full Abelian periods of a word of length $n$ over a constant-size alphabet. Experiments show that our algorithm significantly outperforms the $O(n)$ algorithm proposed by Kociumaka et al. (Proc. of STACS, 245-256, 2013) for the same problem., Accepted for publication in Discrete Applied Mathematics

Published
2016
Full Text
View/download PDF

7. Online Computation of Abelian Runs

Author

Arnaud Lefebvre, Thierry Lecroq, Gabriele Fici, Élise Prieur-Gaston, Università degli studi di Palermo - University of Palermo, Equipe Traitement de l'information en Biologie Santé (TIBS - LITIS), Laboratoire d'Informatique, de Traitement de l'Information et des Systèmes (LITIS), Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Institut National des Sciences Appliquées (INSA)-Normandie Université (NU)-Université de Rouen Normandie (UNIROUEN), Normandie Université (NU)-Université Le Havre Normandie (ULH), Normandie Université (NU)-Institut national des sciences appliquées Rouen Normandie (INSA Rouen Normandie), Normandie Université (NU), Adrian-Horia Dediu, AH, Formenti, E, Vide, CM, Truthe, B, Fici, G., Lecroq, T., Lefebvre, A., Prieur-Gaston, É., and Lecroq, Thierry

Subjects
FOS: Computer and information sciences, Formal Languages and Automata Theory (cs.FL), Abelian run, [INFO.INFO-DS]Computer Science [cs]/Data Structures and Algorithms [cs.DS], [INFO.INFO-DS] Computer Science [cs]/Data Structures and Algorithms [cs.DS], Computer Science - Formal Languages and Automata Theory, 0102 computer and information sciences, 02 engineering and technology, [INFO] Computer Science [cs], 01 natural sciences, Online computation, Theoretical Computer Science, Combinatorics, Computer Science - Data Structures and Algorithms, 0202 electrical engineering, electronic engineering, information engineering, Data Structures and Algorithms (cs.DS), [INFO]Computer Science [cs], Abelian group, ComputingMilieux_MISCELLANEOUS, Mathematics, Combinatorics on word, Discrete mathematics, Computer Science (all), 020206 networking & telecommunications, Abelian period, Text algorithm, 16. Peace & justice, Substring, Combinatorics on words, 010201 computation theory & mathematics, Word (group theory), Computer Science::Formal Languages and Automata Theory
Abstract

Given a word $w$ and a Parikh vector $\mathcal{P}$, an abelian run of period $\mathcal{P}$ in $w$ is a maximal occurrence of a substring of $w$ having abelian period $\mathcal{P}$. We give an algorithm that finds all the abelian runs of period $\mathcal{P}$ in a word of length $n$ in time $O(n\times |\mathcal{P}|)$ and space $O(\sigma+|\mathcal{P}|)$., Comment: To appear in the Proceedings of LATA 2015

Published
2015

Catalog

Books, media, physical & digital resources
See catalog results