Sitemap
A list of all the posts and pages found on the site. For you robots out there, there is an XML version available for digesting as well.
Pages
Posts
publications
Complexity of Testing Ground Reducibility for Linear Word Rewriting Systems With Variables
Proceedings of the 4th International Workshop on Conditional and Typed Rewriting Systems (CTRS-94), Jerusalem, Israel, Springer, pp. 262-275, 1994
Establishes the computational complexity of deciding ground reducibility for linear word (string) rewriting systems with variables.
Some Results on Top-context-free Tree Languages
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
Presents structural and decidability results for top-context-free tree languages, a subclass of context-free tree languages.
Undecidability of Ground Reducibility for Word Rewriting Systems with Variables
Information Processing Letters, 53, pp. 209-215, 1995
Proves that ground reducibility is undecidable for word (string) rewriting systems with variables, in contrast to the decidable case for term rewriting systems.
Decidability of regularity and related properties of ground normal form languages
Information and Computation, vol. 118, pp. 91-100, 1995
Proves that regularity of the ground normal form language of a term rewriting system is decidable, along with related properties.
Matching a Set of Strings with Variable Length Don’t Cares
Theoretical Computer Science, vol. 178 (1), pp. 129-154, 1997
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 Query Bounds for Reconstructing a Hamiltonian Cycle in Complete Graphs
Proceedings of the 5th Israel Symposium on the Theory of Computing Systems (ISTCS), Ramat-Gan, Israel, IEEE Press, pp. 166-173, 1997
Early paper on graph reconstruction focusing on Hamiltonian cycles and different query models. Motivated by a biological problem of genome physical mapping.
How to get rid of projection rules in context-free tree grammars
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.
Reconstructing Set Partitions
Proceedings of the 10th ACM-SIAM Symposium on Discrete Algorithms (SODA), Baltimore, ACM/SIAM, pp. 915-916, 1999
How to reconstruct set partitions from queries about the number of parts represented in subsets.
Finding maximal repetitions in a word in linear time
Proceedings of the 40th Annual Symposium on Foundations of Computer Science (FOCS), New York, NY, USA, IEEE Computer Society, pp. 596-604, 1999
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.
On maximal repetitions in words
Proceedings of the 12th International Symposium on Fundamentals of Computation Theory (FCT'99), Iasi, Romania, Springer, pp. 374-385, 1999
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.
Patterns in words versus patterns in trees: a brief survey and new results
Proceedings of the 3rd Andrei Ershov International Conference "Perspectives of System Informatics" (PSI'99), Novosibirsk, Russia, Springer, pp. 280-293, 1999
Surveys and compares combinatorial pattern-matching and unification problems on words versus on trees, and presents new complexity results linking the two settings.
On repetition-free binary words of minimal density
Theoretical Computer Science, 218(1), pp. 143-160, 1999
Introduces a general notion of minimal letter density for infinite words avoiding prohibited subwords, computed exactly for n-th power-free binary words.
The complexity of some complementation problems
Information Processing Letters, vol. 71, pp. 159-165, 1999
Analyzes the computational complexity of several complementation problems arising in term rewriting and pattern/tree-automaton languages.
Finding Repeats with Fixed Gap
Proceedings of the 7th International Symposium on String Processing and Information Retrieval (SPIRE), Coruña, Spain, IEEE Computer Society, pp. 162-168, 2000
An efficient algorithm finds all pairs of identical factors in a word that are separated by a gap of fixed length.
Motifs dans les mots et les arbres
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.
mreps: efficient and flexible detection of tandem repeats in DNA
Nucleic Acids Research, 31(13), pp. 3672-3678, 2003
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.
Finding approximate repetitions under Hamming distance
Theoretical Computer Science, vol. 303 (1), pp. 135-156, 2003
An efficient algorithm finds all maximal approximate tandem repeats in a word, where approximation between repeat copies is measured under the Hamming distance.
How many square occurrences must a binary sequence contain?
The Electronic Journal of Combinatorics, 10(1), #R12, 2003
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.
Improved hit criteria for DNA local alignment
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.
Estimating seed sensitivity on homogeneous alignments
Proceedings of the IEEE 4th Symposium on Bioinformatics and Bioengineering (BIBE), pp. 387-394, 2004
Introduces a method for estimating alignment seed sensitivity based on homogeneous alignments rather than Markov-chain models of alignment generation.
Linear-time computation of local periods
Theoretical Computer Science, vol. 326 (1-3), pp. 229-240, 2004
A linear-time algorithm computes all local periods (maximal periodicities occurring around each position) of a word.
Periodic structures in words
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
A chapter of the Lothaire book series surveying periodic structures and repetitions in words within combinatorics on words.
YASS: enhancing the sensitivity of DNA similarity search
Nucleic Acids Research, 33, pp. W540-W543, 2005
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.
Multi-seed lossless filtration
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.
Combinatorial Search on Graphs Motivated by Bioinformatics Applications: a Brief Survey
Proceedings of the 31st International Workshop on Graph-Theoretic Concepts in Computer Science (WG), Metz, France, LNCS vol. 3787, pp. 16-27, 2005
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.
A unifying framework for seed sensitivity and its application to subset seeds
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.
Optimal Linear Arrangement of Interval Graphs
Proceedings of the 31st International Symposium on Mathematical Foundations of Computer Science (MFCS), High Tatras, Slovakia, LNCS vol. 4162, pp. 267-279, 2006
Optimal linear arrangement (OLA) of interval graphs is NP-hard.
Diversity and structure of PIF/Harbinger-like elements in the genome of Medicago truncatula
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.
NORINE: a database of nonribosomal peptides
Nucleic Acids Research, Database Issue, vol. 36, pp. D326-D331, 2007
NORINE is a database cataloguing several hundred nonribosomal peptides synthesized by bacteria and fungi, together with tools for their systematic study.
Reconsidering the significance of genomic word frequencies
Trends in Genetics, vol. 23, no. 11, pp. 543-546, 2007
Reconsiders the statistical methods used to assess the significance of genomic word (oligonucleotide) frequency counts.
Optimal neighborhood indexing for protein similarity search
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.
Structural pattern matching of nonribosomal peptides
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.
Searching for gapped palindromes
Theoretical Computer Science, vol. 410, no. 51, pp. 5365-5373, 2009
Gives an O(n log n)-time algorithm for finding all maximal gapped palindromes in a string.
On subset seeds for protein alignment
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.
Paper Title Number 1
Journal 1, 2009
This paper is about the number 1. The number 2 is left for future work.
Recommended citation: Your Name, You. (2009). "Paper Title Number 1." Journal 1. 1(1).
Download Paper | Download Slides | Download Bibtex
Designing efficient spaced seeds for SOLiD read mapping
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.
Back-translation for discovering distant protein homologies in the presence of frameshift mutations
Algorithms for Molecular Biology, 5:6, 2010
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.
On maximal repetitions of arbitrary exponent
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.
Paper Title Number 2
Journal 1, 2010
This paper is about the number 2. The number 3 is left for future work.
Recommended citation: Your Name, You. (2010). "Paper Title Number 2." Journal 1. 1(2).
Download Paper | Download Slides
Regular Expression Constrained Sequence Alignment Revisited
Journal of Computational Biology, 18(5), pp. 771-781, 2011
Improves the time complexity of pairwise sequence alignment constrained by a regular expression (automaton).
On-line construction of position heaps
Proceedings of the 18th International Symposium on String Processing and Information Retrieval (SPIRE), Pisa, Italy, Springer, pp. 326-337, 2011
Gives a simple linear-time on-line algorithm, resembling Ukkonen’s suffix-tree construction, for building the position heap indexing structure of a string.
On the combinatorics of suffix arrays
Information Processing Letters, vol. 113, issues 22-24, pp. 915-920, 2013
Establishes a bijective characterization of suffix array permutations via Burrows-Wheeler arrays, unifying and simplifying prior enumeration results for suffix arrays over bounded alphabets.
Using cascading Bloom filters to improve the memory usage for de Bruijn graph
Algorithms for Molecular Biology, 9:2, 2014
Uses a cascade of Bloom filters with decreasing false-positive rates to represent the de Bruijn graph for genome assembly, substantially reducing memory usage.
Approximate String Matching using a Bidirectional Index
Proceedings of the 25th Annual Symposium on Combinatorial Pattern Matching (CPM), Moscow, Russia, Springer, pp. 230-242, 2014
Introduces “search schemes” for approximate pattern matching over bidirectional FM-indexes, with a probabilistic model to design and evaluate optimal schemes.
Improved Filters for the Approximate Suffix-Prefix Overlap Problem
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.
Spaced seeds improve k-mer-based metagenomic classification
Bioinformatics, 31(22), pp. 3584-3592, 2015
Spaced seeds, rather than contiguous k-mers, significantly improve the accuracy of k-mer-based taxonomic classification of metagenomic sequencing reads.
Computing the longest unbordered substring
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.
Paper Title Number 3
Journal 1, 2015
This paper is about the number 3. The number 4 is left for future work.
Recommended citation: Your Name, You. (2015). "Paper Title Number 3." Journal 1. 1(3).
Download Paper | Download Slides
Optimal Bounds for Computing alpha-gapped Repeats
Proceedings of the 10th International Conference on Language and Automata Theory and Applications (LATA), Prague, Czech Republic, Springer, pp. 245-255, 2016
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.
Full-fledged Real-Time Indexing for Constant Size Alphabets
Algorithmica, vol. 79, no. 2, pp. 387-400, 2017
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.
Evolution of biosequence search algorithms: a brief survey
Bioinformatics, 35(19), pp. 3547-3552, 2019
Surveys the evolution of core algorithmic techniques for comparing and searching biological sequences, from alignment-based methods to alignment-free and sketching-based approaches.
Rapid inference of antibiotic resistance and susceptibility by genomic neighbour typing
Nature Microbiology, 5(3), pp. 455-464, 2020
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.
Minimally overlapping words for sequence similarity search
Bioinformatics, 36(22-23), pp. 5344-5350, 2020
Proposes minimally-overlapping-word seeding schemes for sequence similarity search, showing such words are “anti-clumped” and often outperform minimizer-based seeding.
Space-efficient representation of genomic k-mer count tables
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.
Simplitigs as an efficient and scalable representation of de Bruijn graphs
Genome Biology, 22(1), Article 96, 2021
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.
Efficient Reconciliation of Genomic Datasets of High Similarity
Proceedings of the 22nd International Workshop on Algorithms in Bioinformatics (WABI), LIPIcs vol. 242, pp. 14:1-14:14, 2022
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.
Set-Min sketch: a probabilistic map for power-law distributions with application to k-mer annotation
Journal of Computational Biology, 29(2), pp. 140-154, 2022
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.
Count-min sketch with variable number of hash functions: an experimental study
Proceedings of the 30th International Symposium on String Processing and Information Retrieval (SPIRE), Pisa, Italy, LNCS vol. 14240, Springer, pp. 218-232, 2023
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.
Phase transition in count approximation by Count-Min sketch with conservative updates
Proceedings of the 13th International Conference on Algorithms and Complexity (CIAC), Larnaca, Cyprus, LNCS vol. 13898, Springer, pp. 232-246, 2023
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.
Better space-time-robustness trade-offs for set reconciliation
Proceedings of the 51st International Colloquium on Automata, Languages, and Programming (ICALP), Tallinn, Estonia, LIPIcs vol. 297, pp. 20:1-20:19, 2024
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.
Paper Title Number 4
GitHub Journal of Bugs, 2024
This paper is about fixing template issue #693.
Recommended citation: Your Name, You. (2024). "Paper Title Number 3." GitHub Journal of Bugs. 1(3).
Download Paper
Paper Title Number 5, with math \(E=mc^2\)
GitHub Journal of Bugs, 2024
This paper is about a famous math equation, \(E=mc^2\)
Recommended citation: Your Name, You. (2024). "Paper Title Number 3." GitHub Journal of Bugs. 1(3).
Download Paper
Online computation of normalized substring complexity
Proceedings of the 17th Latin American Theoretical Informatics Symposium (LATIN), April 13-17 2026, Florianópolis, Brazil, 2025
Online maintenance of the normalized substring complexity with logarithmic amortized and worst-case time bounds.