Haplotype-aware graph indexes

DOI10.4230/LIPICS.WABI.2018.4zbMATH Open1494.92090arXiv1805.03834OpenAlexW3022795813MaRDI QIDQ5090328FDOQ5090328

Authors: Jouni Sirén, Erik Garrison, Adam M. Novak, Benedict Paten, Richard Durbin 

Publication date: 18 July 2022

Abstract: The variation graph toolkit (VG) represents genetic variation as a graph. Each path in the graph is a potential haplotype, though most paths are unlikely recombinations of true haplotypes. We augment the VG model with haplotype information to identify which paths are more likely to be correct. For this purpose, we develop a scalable implementation of the graph extension of the positional Burrows--Wheeler transform. We demonstrate the scalability of the new implementation by indexing the 1000 Genomes Project haplotypes. We also develop an algorithm for simplifying variation graphs for k-mer indexing without losing any k-mers in the haplotypes.

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

Recommendations

• Indexing variation graphs
• Read mapping on genome variation graphs
• Describing the local structure of sequence graphs
• From indexing data structures to de Bruijn graphs
• Bidirectional variable-order de Bruijn graphs

zbMATH Keywords

haplotypesFM-indexesvariation graphs

Mathematics Subject Classification ID

Protein sequences, DNA sequences (92D20) Computational methods for problems pertaining to biology (92-08)

Cites Work

• Title not available (Why is that?)
• Compressed indexes for dynamic text collections
• Indexing compressed text
• Practical entropy-compressed rank/select dictionary
• FM-index of alignment: a compressed index for similar strings
• Indexing similar DNA sequences
• Lightweight algorithms for constructing and inverting the BWT of string collections
• A space and time efficient algorithm for constructing compressed suffix arrays
• Wheeler graphs: a framework for BWT-based data structures
• Indexing variation graphs
• FM-index of alignment with gaps

Cited In (4)

• A simple algorithm for computing the document array
• Describing the local structure of sequence graphs
• Indexing variation graphs
• Vaquita: fast and accurate identification of structural variation using combined evidence

This page was built for publication: Haplotype-aware graph indexes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5090328)