Export Citations
Publications
Save this search
Please login to be able to save your searches and receive alerts for new content matching your search criteria.
- research-article
Computing Phylo-
$k$ IEEE/ACM Transactions on Computational Biology and Bioinformatics, Volume 20, Issue 5•Sept.-Oct. 2023, pp 2889-2897 • https://doi.org/10.1109/TCBB.2023.3278049Finding the correct position of new sequences within an established phylogenetic tree is an increasingly relevant problem in evolutionary bioinformatics and metagenomics. Recently, alignment-free approaches for this task have been proposed. One such ...
- Article
Efficient Construction of Hierarchical Overlap Graphs
String Processing and Information Retrieval•October 2020, pp 277-290• https://doi.org/10.1007/978-3-030-59212-7_20AbstractThe hierarchical overlap graph (HOG for short) is an overlap encoding graph that efficiently represents overlaps from a given set P of n strings. A previously known algorithm constructs the HOG in time and space, where is the sum of lengths of ...
- research-article
Linking indexing data structures to de Bruijn graphs: Construction and update
Journal of Computer and System Sciences, Volume 104, Issue C•Sep 2019, pp 165-183 • https://doi.org/10.1016/j.jcss.2016.06.008AbstractDNA sequencing technologies have tremendously increased their throughput, and hence complicated DNA assembly. Numerous assembly programs use de Bruijn graphs (dBG) built from short reads to merge these into contigs, which represent ...
- research-article
Relationship between superstring and compression measures: New insights on the greedy conjecture
Discrete Applied Mathematics, Volume 245, Issue C•Aug 2018, pp 59-64 • https://doi.org/10.1016/j.dam.2017.04.017AbstractA superstring of a set of words is a string that contains each input word as a substring. Given such a set, the Shortest Superstring Problem (SSP) asks for a superstring of minimum length. SSP is an important theoretical problem ...
- research-article
The power of greedy algorithms for approximating Max-ATSP, Cyclic Cover, and superstrings
Discrete Applied Mathematics, Volume 212, Issue C•October 2016, pp 48-60 • https://doi.org/10.1016/j.dam.2015.06.003The Maximum Asymmetric Travelling Salesman Problem (Max-ATSP), which asks for a Hamiltonian path of maximum weight covering a digraph, and the Maximum Compression(Max-Comp), which, for a finite language P ź { s 1 , ź , s p } , asks for w , a superstring ...
- research-article
A linear time algorithm for Shortest Cyclic Cover of Strings
Journal of Discrete Algorithms, Volume 37, Issue C•March 2016, pp 56-67 • https://doi.org/10.1016/j.jda.2016.05.001Merging words according to their overlap yields a superstring. This basic operation allows to infer long strings from a collection of short pieces, as in genome assembly. To capture a maximum of overlaps, the goal is to infer the shortest superstring of ...
- research-article
Reverse engineering of compact suffix trees and links
Journal of Discrete Algorithms, Volume 28, Issue C•September 2014, pp 9-22 • https://doi.org/10.1016/j.jda.2014.07.002Invented in the 1970s, the Suffix Tree (ST) is a data structure that indexes all substrings of a text in linear space. Although more space demanding than other indexes, the ST remains likely an inspiring index because it represents substrings in a ...
- Article
Approximate Common Intervals in Multiple Genome Comparison
BIBM '11: Proceedings of the 2011 IEEE International Conference on Bioinformatics and Biomedicine•November 2011, pp 131-134• https://doi.org/10.1109/BIBM.2011.96We consider the problem of inferring approximate common intervals of multiple genomes. Genomes are modelled as sequences of homologous genes families identifiers, and approximate common intervals represent conserved regions possibly showing ...
- Article
Novel definition and algorithm for chaining fragments with proportional overlaps
RECOMB-CG'10: Proceedings of the 2010 international conference on Comparative genomics•October 2010, pp 161-172Chaining fragments is a crucial step in genome alignment. Existing chaining algorithms compute a maximum weighted chain with no overlaps allowed between adjacent fragments. In practice, using local alignments as fragments, instead of MEMs, generates ...
- Article
MPSCAN: fast localisation of multiple reads in genomes
WABI'09: Proceedings of the 9th international conference on Algorithms in bioinformatics•September 2009, pp 246-260With Next Generation Sequencers, sequence based transcriptomic or epigenomic assays yield millions of short sequence reads that need to be mapped back on a reference genome. The upcoming versions of these sequencers promise even higher sequencing ...
- article
Hardness of optimal spaced seed design
Journal of Computer and System Sciences, Volume 74, Issue 5•August, 2008, pp 831-849 • https://doi.org/10.1016/j.jcss.2007.10.001Speeding up approximate pattern matching is a line of research in stringology since the 80s. Practically fast approaches belong to the class of filtration algorithms, in which text regions dissimilar to the pattern are first excluded, and the remaining ...
- article
Longest common subsequence problem for unoriented and cyclic strings
Theoretical Computer Science, Volume 370, Issue 1-3•February, 2007, pp 1-18 • https://doi.org/10.1016/j.tcs.2006.10.002Given a finite set of strings X, the Longest Common Subsequence problem (LCS) consists in finding a subsequence common to all strings in X that is of maximal length. LCS is a central problem in stringology and finds broad applications in text ...
- Article
Tiling an interval of the discrete line
CPM'06: Proceedings of the 17th Annual conference on Combinatorial Pattern Matching•July 2006, pp 117-128• https://doi.org/10.1007/11780441_12We consider the problem of tiling a segment {0, ..., n} of the discrete line. More precisely, we ought to characterize the structure of the patterns that tile a segment and their number. A pattern is a subset of ℕ. A tiling pattern or tile for {0, ..., ...
- Article
Hardness of optimal spaced seed design
CPM'05: Proceedings of the 16th annual conference on Combinatorial Pattern Matching•June 2005, pp 144-155• https://doi.org/10.1007/11496656_13Speeding up approximate pattern matching is a line of research in stringology since the 80's. Practically fast approaches belong to the class of filtration algorithms, in which text regions dissimilar to the pattern are excluded (filtered out) in a ...
- article
STAR: an algorithm to Search for Tandem Approximate Repeats
Bioinformatics, Volume 20, Issue 16•November 2004, pp 2812-2820 • https://doi.org/10.1093/bioinformatics/bth335Motivation: Tandem repeats consist in approximate and adjacent repetitions of a DNA motif. Such repeats account for large portions of eukaryotic genomes and have also been found in other life kingdoms. Owing to their polymorphism, tandem repeats have ...
- article
Combinatorics of periods in strings
Journal of Combinatorial Theory Series A, Volume 104, Issue 1•October 2003, pp 95-113 • https://doi.org/10.1016/S0097-3165(03)00123-7We consider the set Γn of all period sets of strings of length n over a finite alphabet. We show that there is redundancy in period sets and introduce the notion of an irreducible period set. We prove that Γn is a lattice under set inclusion and does ...
- Article
Complexities of the centre and median string problems
CPM'03: Proceedings of the 14th annual conference on Combinatorial pattern matching•June 2003, pp 315-327Given a finite set of strings, the MEDIAN STRING problem consists in finding a string that minimizes the sum of the distances to the strings in the set. Approximations of the median string are used in a very broad range of applications where one needs a ...
- article
On the Distribution of the Number of Missing Words in Random Texts
Combinatorics, Probability and Computing, Volume 12, Issue 1•January 2003, pp 73-87 • https://doi.org/10.1017/S0963548302005473Determining the distribution of the number of empty urns after a number of balls have been thrown randomly into the urns is a classical and well understood problem. We study a generalization: Given a finite alphabet of size σ and a word length q, what ...
- Article
Comparison of minisatellites
RECOMB '02: Proceedings of the sixth annual international conference on Computational biology•April 2002, pp 67-76• https://doi.org/10.1145/565196.565205In the class of repeated sequences that occur in DNA, minisatellites have been found polymorphic and became useful tools in genetic mapping and forensic studies. They consist of a heterogeneous tandem array of a short repeat unit. The slightly different ...
- Article
Combinatorics of Periods in Strings
ICALP '01: Proceedings of the 28th International Colloquium on Automata, Languages and Programming,•July 2001, pp 615-626We consider the set Γ(n) of all period sets of strings of length n over a finite alphabet. We show that there is redundancy in period sets and introduce the notion of an irreducible period set. We prove that Γ(n) is a lattice under set inclusion and ...