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

ABSTRACT:

Motivation

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.

Results

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 t

SUBMITTER: Marcus S 

PROVIDER: S-EPMC4253837 | biostudies-literature | 2014 Dec

REPOSITORIES: biostudies-literature