Zobrazeno 1 - 10
of 88
pro vyhledávání: '"Cazaux, Bastien"'
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|| log n) time and O(||P||) space, where ||P|| is the sum of lengths of th
Externí odkaz:
http://arxiv.org/abs/2102.12824
Autor:
Equi, Massimo, Norri, Tuukka, Alanko, Jarno, Cazaux, Bastien, Tomescu, Alexandru I., Mäkinen, Veli
We study the problem of matching a string in a labeled graph. Previous research has shown that unless the Orthogonal Vectors Hypothesis (OVH) is false, one cannot solve this problem in strongly sub-quadratic time, nor index the graph in polynomial ti
Externí odkaz:
http://arxiv.org/abs/2102.12822
Autor:
Cazaux, Bastien, Rivals, Eric
A superstring of a set of strings correspond to a string which contains all the other strings as substrings. The problem of finding the Shortest Linear Superstring is a well-know and well-studied problem in stringology. We present here a variant of t
Externí odkaz:
http://arxiv.org/abs/2012.08878
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 founder sequences have the feature that each row of the MSA is a recomb
Externí odkaz:
http://arxiv.org/abs/2005.09342
Akademický článek
Tento výsledek nelze pro nepřihlášené uživatele zobrazit.
K zobrazení výsledku je třeba se přihlásit.
K zobrazení výsledku je třeba se přihlásit.
Autor:
Cazaux, Bastien, Rivals, Eric
Publikováno v:
30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), Leibniz International Proceedings in Informatics (LIPIcs), vol 128, p. 24:1--24:20, 2019
The boom of genomic sequencing makes compression of set of sequences inescapable. This underlies the need for multi-string indexing data structures that helps compressing the data. The most prominent example of such data structures is the Burrows-Whe
Externí odkaz:
http://arxiv.org/abs/1805.10070
Publikováno v:
In Proc. WABI 2018
Given a threshold $L$ and a set $\mathcal{R} = \{R_1, \ldots, R_m\}$ of $m$ haplotype sequences, each having length $n$, the minimum segmentation problem for founder reconstruction is to partition the sequences into disjoint segments $\mathcal{R}[i_1
Externí odkaz:
http://arxiv.org/abs/1805.03574
Autor:
Cazaux, Bastien, Rivals, Eric
Publikováno v:
Information Processing Letters Volume 155, March 2020, 105862
Given a set of finite words, the Overlap Graph (OG) is a complete weighted digraph where each word is a node and where the weight of an arc equals the length of the longest overlap of one word onto the other (Overlap is an asymmetric notion). The OG
Externí odkaz:
http://arxiv.org/abs/1802.04632
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 positions of overlaps of a word onto itself, or of two words, are nee
Externí odkaz:
http://arxiv.org/abs/1707.05613
Background Next Generation Sequencing (NGS) has dramatically enhanced our ability to sequence genomes, but not to assemble them. In practice, many published genome sequences remain in the state of a large set of contigs. Each contig describes the seq
Externí odkaz:
http://arxiv.org/abs/1505.04911