4 papers
A Linear Time Algorithm for Constructing Hierarchical Overlap Graphs
Sangsoo Park, Sung Gwan Park, Bastien Cazaux +2
The hierarchical overlap graph (HOG) is a graph that encodes overlaps from a given set P of n strings, as the overlap graph does. A best known algorithm constructs HOG in O(||P|| l…
Linear Time Construction of Indexable Founder Block Graphs
Veli Mäkinen, Bastien Cazaux, Massimo Equi +2
We introduce a compact pangenome representation based on an optimal segmentation concept that aims to reconstruct founder sequences from a multiple sequence alignment (MSA). Such f…
Minimum Segmentation for Pan-genomic Founder Reconstruction in Linear Time
Tuukka Norri, Bastien Cazaux, Dmitry Kosolobov +1
Given a threshold and a set of haplotype sequences, each having length , the minimum segmentation problem for founder reconstruction…
The Compressed Overlap Index
Rodrigo Canovas, Bastien Cazaux, Eric Rivals
For analysing text algorithms, for computing superstrings, or for testing random number generators, one needs to compute all overlaps between any pairs of words in a given set. The…