Linear-time superbubble identification algorithm for genome assembly

Ljiljana Brankovic; Costas S. Iliopoulos; Ritu Kundu; Manal Mohamed; Solon P. Pissis; Fatima Vayani

doi:10.1016/j.tcs.2015.10.021

Linear-time superbubble identification algorithm for genome assembly

Ljiljana Brankovic, Costas S. Iliopoulos, Ritu Kundu, Manal Mohamed, Solon P. Pissis, Fatima Vayani

Research output: Contribution to journal › Article › peer-review

18 Citations (Scopus)

211 Downloads (Pure)

Abstract

DNA sequencing is the process of determining the exact order of the nucleotide bases of an individual's genome in order to catalogue sequence variation and understand its biological implications. Whole-genome sequencing techniques produce masses of data in the form of short sequences known as reads. Assembling these reads into a whole genome constitutes a major algorithmic challenge. Most assembly algorithms utilise de Bruijn graphs constructed from reads for this purpose. A critical step of these algorithms is to detect typical motif structures in the graph caused by sequencing errors and genome repeats, and filter them out; one such complex subgraph class is a so-called superbubble . In this paper, we propose an O(n+m)O(n+m)-time algorithm to detect all superbubbles in a directed acyclic graph with n vertices and m (directed) edges, improving the best-known O(mlog⁡m)O(mlog⁡m)-time algorithm by Sung et al.

Original language	English
Pages (from-to)	374-383
Number of pages	10
Journal	Theoretical Computer Science
Volume	609, Part 2
Early online date	23 Oct 2015
DOIs	https://doi.org/10.1016/j.tcs.2015.10.021
Publication status	Published - 4 Jan 2016

Access to Document

10.1016/j.tcs.2015.10.021Licence: CC BY

Linear-time superbubble identification_BRANKOVIC_Acc16Oct2015_GOLD VoR(CC BY)Final published version, 352 KBLicence: CC BY

Cite this

@article{8555eec3a29f4abb8e607a0e4d7e6afd,

title = "Linear-time superbubble identification algorithm for genome assembly",

abstract = "DNA sequencing is the process of determining the exact order of the nucleotide bases of an individual's genome in order to catalogue sequence variation and understand its biological implications. Whole-genome sequencing techniques produce masses of data in the form of short sequences known as reads. Assembling these reads into a whole genome constitutes a major algorithmic challenge. Most assembly algorithms utilise de Bruijn graphs constructed from reads for this purpose. A critical step of these algorithms is to detect typical motif structures in the graph caused by sequencing errors and genome repeats, and filter them out; one such complex subgraph class is a so-called superbubble . In this paper, we propose an O(n+m)O(n+m)-time algorithm to detect all superbubbles in a directed acyclic graph with n vertices and m (directed) edges, improving the best-known O(mlog⁡m)O(mlog⁡m)-time algorithm by Sung et al.",

author = "Ljiljana Brankovic and Iliopoulos, {Costas S.} and Ritu Kundu and Manal Mohamed and Pissis, {Solon P.} and Fatima Vayani",

year = "2016",

month = jan,

day = "4",

doi = "10.1016/j.tcs.2015.10.021",

language = "English",

volume = "609, Part 2",

pages = "374--383",

journal = "Theoretical Computer Science",

issn = "0304-3975",

publisher = "Elsevier",

}

TY - JOUR

T1 - Linear-time superbubble identification algorithm for genome assembly

AU - Brankovic, Ljiljana

AU - Iliopoulos, Costas S.

AU - Kundu, Ritu

AU - Mohamed, Manal

AU - Pissis, Solon P.

AU - Vayani, Fatima

PY - 2016/1/4

Y1 - 2016/1/4

N2 - DNA sequencing is the process of determining the exact order of the nucleotide bases of an individual's genome in order to catalogue sequence variation and understand its biological implications. Whole-genome sequencing techniques produce masses of data in the form of short sequences known as reads. Assembling these reads into a whole genome constitutes a major algorithmic challenge. Most assembly algorithms utilise de Bruijn graphs constructed from reads for this purpose. A critical step of these algorithms is to detect typical motif structures in the graph caused by sequencing errors and genome repeats, and filter them out; one such complex subgraph class is a so-called superbubble . In this paper, we propose an O(n+m)O(n+m)-time algorithm to detect all superbubbles in a directed acyclic graph with n vertices and m (directed) edges, improving the best-known O(mlog⁡m)O(mlog⁡m)-time algorithm by Sung et al.

AB - DNA sequencing is the process of determining the exact order of the nucleotide bases of an individual's genome in order to catalogue sequence variation and understand its biological implications. Whole-genome sequencing techniques produce masses of data in the form of short sequences known as reads. Assembling these reads into a whole genome constitutes a major algorithmic challenge. Most assembly algorithms utilise de Bruijn graphs constructed from reads for this purpose. A critical step of these algorithms is to detect typical motif structures in the graph caused by sequencing errors and genome repeats, and filter them out; one such complex subgraph class is a so-called superbubble . In this paper, we propose an O(n+m)O(n+m)-time algorithm to detect all superbubbles in a directed acyclic graph with n vertices and m (directed) edges, improving the best-known O(mlog⁡m)O(mlog⁡m)-time algorithm by Sung et al.

U2 - 10.1016/j.tcs.2015.10.021

DO - 10.1016/j.tcs.2015.10.021

M3 - Article

SN - 0304-3975

VL - 609, Part 2

SP - 374

EP - 383

JO - Theoretical Computer Science

JF - Theoretical Computer Science

ER -

Linear-time superbubble identification algorithm for genome assembly

Abstract

Access to Document

Fingerprint

Cite this