Nov 16, 2014

SplitMEM: a graphical algorithm for pan-genome analysis with suffix skips

Bioinformatics
Shoshana MarcusMichael C Schatz

Abstract

Genomics is expanding from a single reference per species paradigm into a more comprehensive pan-genome approach that analyzes multiple individuals together. A compressed de Bruijn graph is a sophisticated data structure for representing the genomes of entire populations. It robustly encodes shared segments, simple single-nucleotide polymorphisms and complex structural variations far beyond what can be represented in a collection of linear sequences alone. We explore deep topological relationships between suffix trees and compressed de Bruijn graphs and introduce an algorithm, splitMEM, that directly constructs the compressed de Bruijn graph in time and space linear to the total number of genomes for a given maximum genome size. We introduce suffix skips to traverse several suffix links simultaneously and use them to efficiently decompose maximal exact matches into graph nodes. We demonstrate the utility of splitMEM by analyzing the nine-strain pan-genome of Bacillus anthracis and up to 62 strains of Escherichia coli, revealing their core-genome properties.

  • References15
  • Citations20
  • References15
  • Citations20

Citations

Mentioned in this Paper

Alkalescens-Dispar Group
Genome
Genomics
Sequence Determinations, DNA
Nucleotides
Bacillus anthracis
Genetic Polymorphism
Suffix brand of benzoylprop-ethyl
Genome, Bacterial
Escherichia coli

Related Feeds

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.

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 (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.

© 2020 Meta ULC. All rights reserved