Search

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 the strings in P. In this paper we present a new algorithm to construct HOG in O(||P||) time and space. Hence, the construction time and space of HOG are better than those of the overlap graph, which are O(||P|| + n^2)., Comment: 8 pages, 2 figures, submitted to CPM 2021

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 needed to compute the absence probability of a word in a random text, or the numbers of common words shared by two random texts. In all these contexts, one needs to compute or to query overlaps between pairs of words in a given set. For this sake, we designed COvI, a compressed overlap index that supports multiple queries on overlaps: like computing the correlation of two words, or listing pairs of words whose longest overlap is maximal among all possible pairs. COvI stores overlaps in a hierarchical and non-redundant manner. We propose an implementation that can handle datasets of millions of words and still answer queries efficiently. Comparison with a baseline solution - called FullAC - relying on the Aho-Corasick automaton shows that COvI provides significant advantages. For similar construction times, COvI requires half the memory FullAC, and still solves complex queries much faster.

Read mapping on De Bruijn graphs additional file. Three complementary tables are presented. Main characteristics of data sets used in this study. Assembly and mapping approach comparison. Results of BGREAT on real read sets. (PDF 40 kb)

Theobroma cacao L., native from the Amazonian basin of South America is an economically important fruit tree crop for tropical countries, source of chocolate. The first draft genome of the species, from a Criollo cultivar was published In 2011. Although a useful resource, some improvements can be made, including efforts to identify misassemblies, and reduction of the number of scaffolds, gaps, and un-anchored sequences to the ten chromosomes. In this work, we used a NGS-based approach to significantly improve the assembly of the Belizian Criollo B97-61/B2 genome. We combined 4 Illumina large insert size mate paired libraries with 52x of Pacific Biosciences long reads to correct misassembled regions, reduce the number of scaffolds to 554 (4,792 in assembly V1) with a N50 increased from 0.47 Mb to 6.5 Mb. 96.7% of the assembly was anchored to the 10 chromosomes compared to the previous 66.8%. Unknown sites (Ns) were reduced from 10.8% to 5.7%. Moreover, the NCBI Eukaryotic Genome Annotation Pipeline carried out a new RefSeq structural annotation based on RNAseq evidences and functional annotations have been updated. The release of the Theobroma cacao Criollo genome version 2 will be a valuable resource for investigating complex traits at the genomic level and is an important step for future comparative genomics and genetics studied on cocoa. New functional tools and annotations are available through the cacao genome hub (http://cocoa-genome-hub.southgreen.fr). (Texte integral)