Publications

Motifs dans les mots et les arbres by G. Kucherov — Habilitation à Diriger les Recherches, Université de Nancy 1 Henri Poincaré. (in French), 2000.

Habilitation thesis addressing motif discovery and combinatorial pattern matching problems in words and trees.

Periodic structures in words by R. Kolpakov, G. Kucherov — In J. Berstel and D. Perrin (eds.), Applied Combinatorics on Words, Encyclopedia of Mathematics and its Applications vol. 104 (Lothaire books), chapter 8, Cambridge University Press, pp. 430-477, 2005. [pdf]

A chapter of the Lothaire book series surveying periodic structures and repetitions in words within combinatorics on words.

Better space-time-robustness trade-offs for set reconciliation by D. Belazzougui, G. Kucherov, S. Walzer — Proceedings of the 51st International Colloquium on Automata, Languages, and Programming (ICALP), Tallinn, Estonia, LIPIcs vol. 297, pp. 20:1-20:19, 2024. [arxiv]

Proposes a tunable Invertible-Bloom-Lookup-Table-based sketch for reconstructing the symmetric difference of similar sets, trading space and decoding time against an exponentially decreasing failure probability.

Phase transition in count approximation by Count-Min sketch with conservative updates by E. Fusy, G. Kucherov — Proceedings of the 13th International Conference on Algorithms and Complexity (CIAC), Larnaca, Cyprus, LNCS vol. 13898, Springer, pp. 232-246, 2023. [arxiv]

Shows that, for uniformly distributed keys, the relative error of Count-Min sketch with conservative updates undergoes a sharp phase transition tied to the peelability threshold of random k-uniform hypergraphs.

Count-min sketch with variable number of hash functions: an experimental study by E. Fusy, G. Kucherov — Proceedings of the 30th International Symposium on String Processing and Information Retrieval (SPIRE), Pisa, Italy, LNCS vol. 14240, Springer, pp. 218-232, 2023. [arxiv]

Experimentally studies the error behavior of Count-Min sketch under various input distributions and proposes assigning a variable number of hash functions per element to reduce space while keeping the error small.

Set-Min sketch: a probabilistic map for power-law distributions with application to k-mer annotation by Y. Shibuya, D. Belazzougui, G. Kucherov — Journal of Computational Biology, 29(2), pp. 140-154, 2022. [biorxiv]

Introduces Set-Min sketch, a probabilistic sketch for approximately storing k-mer counts that exploits the power-law distribution of genomic k-mer frequencies to achieve lower error rates and less space than Count-Min sketch.

Efficient Reconciliation of Genomic Datasets of High Similarity by Y. Shibuya, D. Belazzougui, G. Kucherov — Proceedings of the 22nd International Workshop on Algorithms in Bioinformatics (WABI), LIPIcs vol. 242, pp. 14:1-14:14, 2022. [biorxiv]

Uses Invertible Bloom Lookup Tables combined with syncmer-based k-mer sampling to reconcile highly similar genomic k-mer sets more space-efficiently and accurately than MinHash.

Simplitigs as an efficient and scalable representation of de Bruijn graphs by K. Břinda, M. Baym, G. Kucherov — Genome Biology, 22(1), Article 96, 2021. [biorxiv]

Introduces simplitigs and the ProphAsm algorithm as a compact, efficient, and scalable alternative to unitigs for representing de Bruijn graphs, reducing sequence redundancy and indexing costs on bacterial pan-genomes.

Space-efficient representation of genomic k-mer count tables by Y. Shibuya, D. Belazzougui, G. Kucherov — Proceedings of the 21st International Workshop on Algorithms in Bioinformatics (WABI), LIPIcs vol. 201, pp. 8:1-8:19, 2021.

Combines Bloom-filter-enhanced compressed static functions with minimizer-based bucketing to represent genomic k-mer count tables in about half the space of the empirical entropy bound while supporting fast random-access queries.

Minimally overlapping words for sequence similarity search by M. C. Frith, L. Noé, G. Kucherov — Bioinformatics, 36(22-23), pp. 5344-5350, 2020. [biorxiv]

Proposes minimally-overlapping-word seeding schemes for sequence similarity search, showing such words are “anti-clumped” and often outperform minimizer-based seeding.

Rapid inference of antibiotic resistance and susceptibility by genomic neighbour typing by K. Břinda, A. Callendrello, K. C. Ma, D. R. MacFadden, T. Charalampous, R. S. Lee, L. Cowley, C. B. Wadsworth, Y. H. Grad, G. Kucherov, J. O''Grady, M. Baym, W. P. Hanage — Nature Microbiology, 5(3), pp. 455-464, 2020. [pdf] [biorxiv]

Presents genomic neighbour typing, a method that infers antibiotic resistance and susceptibility phenotypes from an isolate’s closest genomic relatives, enabling near-real-time predictions from nanopore sequencing of clinical samples.

Evolution of biosequence search algorithms: a brief survey by G. Kucherov — Bioinformatics, 35(19), pp. 3547-3552, 2019. [arxiv]

Surveys the evolution of core algorithmic techniques for comparing and searching biological sequences, from alignment-based methods to alignment-free and sketching-based approaches.

Spaced seeds improve k-mer-based metagenomic classification by K. Brinda, M. Sykulski, G. Kucherov — Bioinformatics, 31(22), pp. 3584-3592, 2015. [arxiv]

Spaced seeds, rather than contiguous k-mers, significantly improve the accuracy of k-mer-based taxonomic classification of metagenomic sequencing reads.

Improved Filters for the Approximate Suffix-Prefix Overlap Problem by G. Kucherov, D. Tsur — Proceedings of the 21st International Symposium on String Processing and Information Retrieval (SPIRE), Ouro Preto, Brazil, Springer, pp. 139-148, 2014.

Improves prior suffix-filter based methods for efficiently computing approximate suffix-prefix overlaps among large collections of next-generation sequencing reads.

Using cascading Bloom filters to improve the memory usage for de Bruijn graph by K. Salikhov, G. Sacomoto, G. Kucherov — Algorithms for Molecular Biology, 9:2, 2014. [arxiv]

Uses a cascade of Bloom filters with decreasing false-positive rates to represent the de Bruijn graph for genome assembly, substantially reducing memory usage.

Regular Expression Constrained Sequence Alignment Revisited by G. Kucherov, T. Pinhas, M. Ziv-Ukelson — Journal of Computational Biology, 18(5), pp. 771-781, 2011.

Improves the time complexity of pairwise sequence alignment constrained by a regular expression (automaton).

Back-translation for discovering distant protein homologies in the presence of frameshift mutations by M. Girdea, L. Noé, G. Kucherov — Algorithms for Molecular Biology, 5:6, 2010. [pdf]

Presents a dynamic-programming alignment method over memory-efficient graph representations of back-translated DNA to detect distant protein homologies obscured by frameshift and point mutations.

Designing efficient spaced seeds for SOLiD read mapping by L. Noé, M. Girdea, G. Kucherov — Advances in Bioinformatics, vol. 2010, Article ID 708501, 2010.

Proposes a rigorous algorithmic framework for designing spaced seeds tailored to SOLiD color-space reads to improve reference-genome mapping sensitivity.

On subset seeds for protein alignment by M. Roytberg, A. Gambin, L. Noé, S. Lasota, E. Furletova, E. Szczurek, G. Kucherov — IEEE/ACM Transactions on Computational Biology and Bioinformatics, 3(6), pp. 483-494, 2009.

Adapts the subset-seed concept to protein sequence similarity search, designing seed alphabets that match or exceed BLASTP’s sensitivity-selectivity trade-off.

Optimal neighborhood indexing for protein similarity search by P. Peterlongo, L. Noé, D. Lavenier, V. H. Nguyen, G. Kucherov, M. Giraud — BMC Bioinformatics, 9(534), 2008.

Combining alphabet reduction with extended neighborhood indexing reduces memory usage by about 35% without loss of sensitivity or speed in protein similarity search.

Diversity and structure of PIF/Harbinger-like elements in the genome of Medicago truncatula by D. Grzebelus, S. Lasota, T. Gambin, G. Kucherov, A. Gambin — BMC Genomics, 8(409), 2007.

Genome-wide analysis identified 89 PIF/Harbinger-like transposable elements in Medicago truncatula, organized into five families shaped mainly by internal deletions.

A unifying framework for seed sensitivity and its application to subset seeds by G. Kucherov, L. Noé, M. Roytberg — Journal of Bioinformatics and Computational Biology, 4(2), pp. 553-569, 2006.

Presents a unified automaton-based framework for computing the sensitivity of alignment seeds and applies it to introduce subset seeds, a flexible alternative to spaced seeds.

Multi-seed lossless filtration by G. Kucherov, L. Noé, M. Roytberg — IEEE/ACM Transactions on Computational Biology and Bioinformatics, 2(1), pp. 51-61, 2005.

Presents algorithms for combining multiple spaced seeds to achieve efficient lossless filtration in approximate string matching, with application to oligonucleotide selection.

YASS: enhancing the sensitivity of DNA similarity search by L. Noé, G. Kucherov — Nucleic Acids Research, 33, pp. W540-W543, 2005. [website]

YASS is a web-based DNA similarity search tool using transition-constrained seeds and a flexible hit criterion to improve sensitivity in detecting homologous genomic regions.

Estimating seed sensitivity on homogeneous alignments by G. Kucherov, L. Noé, Y. Ponty — Proceedings of the IEEE 4th Symposium on Bioinformatics and Bioengineering (BIBE), pp. 387-394, 2004. [pdf]

Introduces a method for estimating alignment seed sensitivity based on homogeneous alignments rather than Markov-chain models of alignment generation.

Improved hit criteria for DNA local alignment by L. Noé, G. Kucherov — BMC Bioinformatics, 5(149), 2004.

Proposes a flexible group criterion combining single- and multi-seed strategies plus transition-constrained seeds to improve sensitivity of heuristic DNA local alignment methods.

mreps: efficient and flexible detection of tandem repeats in DNA by R. Kolpakov, G. Bana, G. Kucherov — Nucleic Acids Research, 31(13), pp. 3672-3678, 2003. [website]

mreps is a software tool that detects all tandem repeats in a DNA sequence in a single run, using a resolution parameter to control tolerance for fuzzy repeats.

Reconsidering the significance of genomic word frequencies by M. Csűrös, L. Noé, G. Kucherov — Trends in Genetics, vol. 23, no. 11, pp. 543-546, 2007. [website]

Reconsiders the statistical methods used to assess the significance of genomic word (oligonucleotide) frequency counts.

Structural pattern matching of nonribosomal peptides by S. Caboche, M. Pupin, V. Leclère, P. Jacques, G. Kucherov — BMC Structural Biology, vol. 9, article 15, 2009.

Presents a graph-based method that models structural pattern matching between nonribosomal peptides as a variant of the maximum common subgraph problem.

NORINE: a database of nonribosomal peptides by S. Caboche, M. Pupin, V. Leclère, A. Fontaine, Ph. Jacques, G. Kucherov — Nucleic Acids Research, Database Issue, vol. 36, pp. D326-D331, 2007. [website]

NORINE is a database cataloguing several hundred nonribosomal peptides synthesized by bacteria and fungi, together with tools for their systematic study.

Online computation of normalized substring complexity by G. Kucherov, Y. Nekrich — Proceedings of the 17th Latin American Theoretical Informatics Symposium (LATIN), April 13-17 2026, Florianópolis, Brazil, 2025. [arxiv]

Online maintenance of the normalized substring complexity with logarithmic amortized and worst-case time bounds.

Full-fledged Real-Time Indexing for Constant Size Alphabets by G. Kucherov, Y. Nekrich — Algorithmica, vol. 79, no. 2, pp. 387-400, 2017. [arxiv]

Presents a real-time indexing data structure for constant-size-alphabet strings supporting O(1) worst-case time symbol insertion and O(|P|+k)-time pattern matching queries.

Optimal Bounds for Computing alpha-gapped Repeats by M. Crochemore, R. Kolpakov, G. Kucherov — Proceedings of the 10th International Conference on Language and Automata Theory and Applications (LATA), Prague, Czech Republic, Springer, pp. 245-255, 2016. [arxiv]

Proves an optimal O(alpha n) bound on the number of maximal alpha-gapped repeats in a string of length n and gives a matching time algorithm to compute them.

Computing the longest unbordered substring by P. Gawrychowski, G. Kucherov, B. Sach, T. Starikovskaya — Proceedings of the 22nd International Symposium on String Processing and Information Retrieval (SPIRE), London, UK, Springer, pp. 246-257, 2015.

Gives improved algorithms for computing the longest unbordered substring of a string, running in O(n log n) expected time and O(n^1.5) worst-case time.

Approximate String Matching using a Bidirectional Index by G. Kucherov, K. Salikhov, D. Tsur — Proceedings of the 25th Annual Symposium on Combinatorial Pattern Matching (CPM), Moscow, Russia, Springer, pp. 230-242, 2014. [arxiv]

Introduces “search schemes” for approximate pattern matching over bidirectional FM-indexes, with a probabilistic model to design and evaluate optimal schemes.

On the combinatorics of suffix arrays by G. Kucherov, L. Tóthmérész, S. Vialette — Information Processing Letters, vol. 113, issues 22-24, pp. 915-920, 2013. [arxiv]

Establishes a bijective characterization of suffix array permutations via Burrows-Wheeler arrays, unifying and simplifying prior enumeration results for suffix arrays over bounded alphabets.

On-line construction of position heaps by G. Kucherov — Proceedings of the 18th International Symposium on String Processing and Information Retrieval (SPIRE), Pisa, Italy, Springer, pp. 326-337, 2011. [arxiv]

Gives a simple linear-time on-line algorithm, resembling Ukkonen’s suffix-tree construction, for building the position heap indexing structure of a string.

Searching for gapped palindromes by R. Kolpakov, G. Kucherov — Theoretical Computer Science, vol. 410, no. 51, pp. 5365-5373, 2009. [pdf]

Gives an O(n log n)-time algorithm for finding all maximal gapped palindromes in a string.

Linear-time computation of local periods by J.-P. Duval, R. Kolpakov, G. Kucherov, T. Lecroq, A. Lefebvre — Theoretical Computer Science, vol. 326 (1-3), pp. 229-240, 2004. [pdf]

A linear-time algorithm computes all local periods (maximal periodicities occurring around each position) of a word.

Finding approximate repetitions under Hamming distance by R. Kolpakov, G. Kucherov — Theoretical Computer Science, vol. 303 (1), pp. 135-156, 2003. [pdf]

An efficient algorithm finds all maximal approximate tandem repeats in a word, where approximation between repeat copies is measured under the Hamming distance.

Finding Repeats with Fixed Gap by R. Kolpakov, G. Kucherov — Proceedings of the 7th International Symposium on String Processing and Information Retrieval (SPIRE), Coruña, Spain, IEEE Computer Society, pp. 162-168, 2000. [pdf]

An efficient algorithm finds all pairs of identical factors in a word that are separated by a gap of fixed length.

Finding maximal repetitions in a word in linear time by R. Kolpakov, G. Kucherov — Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), New York, NY, USA, IEEE Computer Society, pp. 596-604, 1999. [pdf]

The sum of exponents of all maximal repetitions in a word of length n is linear in n, which yields a linear-time algorithm for finding all maximal repetitions (runs) in a word.

Matching a Set of Strings with Variable Length Don’t Cares by G. Kucherov, M. Rusinowitch — Theoretical Computer Science, vol. 178 (1), pp. 129-154, 1997. [pdf]

Efficient algorithms are given for matching a fixed set of strings containing variable-length don’t-care symbols against a text, based on ground word-rewriting techniques.

Optimal Linear Arrangement of Interval Graphs by J. Cohen, F. Fomin, P. Heggernes, D. Kratsch, G. Kucherov — Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS), High Tatras, Slovakia, LNCS vol. 4162, pp. 267-279, 2006. [pdf]

Optimal linear arrangement (OLA) of interval graphs is NP-hard.

Combinatorial Search on Graphs Motivated by Bioinformatics Applications: a Brief Survey by M. Bouvel, V. Grebinski, G. Kucherov — Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Metz, France, LNCS vol. 3787, pp. 16-27, 2005. [pdf]

A brief survey of a collection of methods and results from the area of combinatorial search, focusing on graph reconstruction using queries of different types.

Reconstructing Set Partitions by V. Grebinski, G. Kucherov — Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms (SODA), Baltimore, ACM/SIAM, pp. 915-916, 1999. [pdf]

How to reconstruct set partitions from queries about the number of parts represented in subsets.

Optimal Query Bounds for Reconstructing a Hamiltonian Cycle in Complete Graphs by V. Grebinski, G. Kucherov — Proceedings of the 5th Israel Symposium on the Theory of Computing Systems (ISTCS), Ramat-Gan, Israel, IEEE Press, pp. 166-173, 1997. [pdf]

Early paper on graph reconstruction focusing on Hamiltonian cycles and different query models. Motivated by a biological problem of genome physical mapping.

On maximal repetitions of arbitrary exponent by R. Kolpakov, G. Kucherov, P. Ochem — Information Processing Letters, 110(7), pp. 252-256, 2010.

Generalizes the earlier linear bound on the number of maximal repetitions (runs) of exponent at least 2 in a word to maximal repetitions of exponent strictly greater than 1.

How many square occurrences must a binary sequence contain? by G. Kucherov, P. Ochem, M. Rao — The Electronic Journal of Combinatorics, 10(1), #R12, 2003. [pdf]

Shows that the number of square occurrences in an infinite binary word is at least a constant fraction, approximately 0.55080, of the word’s length.

On repetition-free binary words of minimal density by R. Kolpakov, G. Kucherov, Yu. Tarannikov — Theoretical Computer Science, 218(1), pp. 143-160, 1999. [pdf]

Introduces a general notion of minimal letter density for infinite words avoiding prohibited subwords, computed exactly for n-th power-free binary words.

Patterns in words versus patterns in trees: a brief survey and new results by G. Kucherov, M. Rusinowitch — Proceedings of the 3rd Andrei Ershov International Conference "Perspectives of System Informatics" (PSI'99), Novosibirsk, Russia, Springer, pp. 280-293, 1999. [pdf]

Surveys and compares combinatorial pattern-matching and unification problems on words versus on trees, and presents new complexity results linking the two settings.

On maximal repetitions in words by R. Kolpakov, G. Kucherov — Proceedings of the 12th International Symposium on Fundamentals of Computation Theory (FCT'99), Iasi, Romania, Springer, pp. 374-385, 1999. [pdf]

Gives an algorithm computing all maximal repetitions (runs) in a word and bounds on the maximum possible number of such repetitions as a function of word length.

Undecidability of Ground Reducibility for Word Rewriting Systems with Variables by G. Kucherov, M. Rusinowitch — Information Processing Letters, 53, pp. 209-215, 1995. [pdf]

Proves that ground reducibility is undecidable for word (string) rewriting systems with variables, in contrast to the decidable case for term rewriting systems.

Complexity of Testing Ground Reducibility for Linear Word Rewriting Systems With Variables by G. Kucherov, M. Rusinowitch — Proceedings of the 4th International Workshop on Conditional and Typed Rewriting Systems (CTRS-94), Jerusalem, Israel, Springer, pp. 262-275, 1994. [pdf]

Establishes the computational complexity of deciding ground reducibility for linear word (string) rewriting systems with variables.

The complexity of some complementation problems by G. Kucherov, D. Plaisted — Information Processing Letters, vol. 71, pp. 159-165, 1999. [pdf]

Analyzes the computational complexity of several complementation problems arising in term rewriting and pattern/tree-automaton languages.

How to get rid of projection rules in context-free tree grammars by D. Hofbauer, M. Huber, G. Kucherov — Studies in Logic, Language and Information, Chapter 15, pp. 235-247, Center for the Study of Language and Information (CSLI), Stanford, and The European Association for Logic, Language and Information (FoLLI), 1998.

Shows how projection (identity) rules can be eliminated from context-free tree grammars without loss of generative power.

Decidability of regularity and related properties of ground normal form languages by G. Kucherov, M. Tajine — Information and Computation, vol. 118, pp. 91-100, 1995. [pdf]

Proves that regularity of the ground normal form language of a term rewriting system is decidable, along with related properties.

Some Results on Top-context-free Tree Languages by D. Hofbauer, M. Huber, G. Kucherov — Proceedings of the 19th International Colloquium on Trees in Algebra and Programming (CAAP), Lecture Notes in Computer Science, vol. 787, Springer-Verlag, pp. 157-171, 1994. [pdf]

Presents structural and decidability results for top-context-free tree languages, a subclass of context-free tree languages.