An external-memory algorithm for string graph construction

DOI10.1007/s00453-016-0165-4zbMath1369.68363arXiv1405.7520OpenAlexW2963599524MaRDI QIDQ2362353

Gianluca Della Vedova, Raffaella Rizzi, Paola Bonizzoni, Yuri Pirola, Marco Previtali

Publication date: 7 July 2017

Published in: Algorithmica (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1405.7520

zbMATH Keywords

Burrows-Wheeler transformexternal memory algorithmsstring graphsgenome assembly

Mathematics Subject Classification ID

Algorithms on strings (68W32)

Related Items

Can formal languages help pangenomics to represent and analyze multiple genomes? ⋮ On the longest common prefix of suffixes in an inverse Lyndon factorization and other properties ⋮ Computing the multi-string BWT and LCP array in external memory ⋮ Unnamed Item

Uses Software

• GATK
• SPAdes
• IDBA-UD
• ABySS
• BEETL

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Lightweight algorithms for constructing and inverting the BWT of string collections
• Replacing suffix trees with enhanced suffix arrays
• Algorithms for parallel memory, I: Two-level memories
• Physical mapping of chromosomes: A combinatorial problem in molecular biology
• Computing the multi-string BWT and LCP array in external memory
• Indexing compressed text
• Linear approximation of shortest superstrings
• Scaling metagenome sequence assembly with probabilistic de Bruijn graphs
• Comparing DNA Sequence Collections by Direct Comparison of Compressed Text Indexes
• Lightweight LCP Construction for Next-Generation Sequencing Datasets
• The Burrows-Wheeler Transform between Data Compression and Combinatorics on Words
• Covering Pairs in Directed Acyclic Graphs
• Trading off space for passes in graph streaming problems