Apr 6, 2014

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

  • References
  • Citations

References

  • We're still populating references for this paper, please check back later.
  • References
  • Citations

Citations

  • This paper may not have been cited yet.

Mentioned in this Paper

Matching Test
Genome
Trees (plant)
Nucleic Acid Sequencing
Genomics
Sequencing
OSR1 gene
Comparative Genomic Analysis
Tributyl phosphate
Bacillus anthracis

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.

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.

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.