Sidenote - For those of you asking questions on Contrail, we asked M. Schatz in twitter.
Michael Schatz posted a new preprint in arxiv. We have not read it yet, but the abstract appears promising. We will get back to it later, but for readers’ benefit here is what it is all about.
Motivation: With the rise of improved sequencing technologies, genomics is expanding from a single reference per species paradigm into a more comprehensive pan-genome approach with multiple individuals represented and analyzed together. One of the most sophisticated data structures for representing an entire population of genomes is a compressed de Bruijn graph. The graph structure can robustly represent simple SNPs to complex structural variations far beyond what can be done from linear sequences alone. As such there is a strong need to develop algorithms that can efficiently construct and analyze these graphs.
Results: In this paper we explore the deep topological relationships between the suffix tree and the compressed de Bruijn graph. We introduce a novel O(n log n) time and space algorithm called splitMEM, that directly constructs the compressed de Bruijn graph for a pan-genome of total length n. To achieve this time complexity, we augment the suffix tree with suffix skips, a new construct that allows us to traverse several suffix links in constant time, and use them to efficiently decompose maximal exact matches (MEMs) into the graph nodes. We demonstrate the utility of splitMEM by analyzing the pan- genomes of 9 strains of Bacillus anthracis and 9 strains of Escherichia coli to reveal the properties of their core genomes. Availability: The source code and documentation are available open- source at http://splitmem.sourceforge.net
For other related methods, readers are encouraged to check -
Thanks to Ilia Minkin, the first author of Sibelia, for pointing out his relevant paper. The readers may find following comments useful in comparing Sibelia with splitMEM. Edit. He also wrote a blog-post on this topic and it is available here.