SplitMEM: Graphical pan-genome analysis with suffix skips

BioRxiv : the Preprint Server for Biology
Shoshana MarcusMichael C Schatz

Abstract

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 strai...Continue Reading

Related Concepts

Bacillus anthracis
Escherichia coli
Genome
Motivation
Ozone
Trees (plant)
Tributyl phosphate
Depth
Linear
Structure

Related Feeds

Anthrax Vaccines (ASM)

Three different types of anthrax vaccines are available; a live-attenuated, an alum-precipitated cell-free filtrate and a protein recombinant vaccine. The effectiveness between the three is uncertain, but the live-attenuated have shown to reduce the risk of anthrax with low adverse events. Here is the latest research on anthrax vaccines.

Anthrax

Anthrax toxin, comprising protective antigen, lethal factor, and oedema factor, is the major virulence factor of Bacillus anthracis, an agent that causes high mortality in humans and animals. Here is the latest research on Anthrax.

Anthrax Vaccines

Three different types of anthrax vaccines are available; a live-attenuated, an alum-precipitated cell-free filtrate and a protein recombinant vaccine. The effectiveness between the three is uncertain, but the live-attenuated have shown to reduce the risk of anthrax with low adverse events. Here is the latest research on anthrax vaccines.

BioRxiv & MedRxiv Preprints

BioRxiv and MedRxiv are the preprint servers for biology and health sciences respectively, operated by Cold Spring Harbor Laboratory. Here are the latest preprint articles (which are not peer-reviewed) from BioRxiv and MedRxiv.