CHOP: haplotype-aware path indexing in population graphs

The practical use of graph-based reference genomes depends on the ability to align reads to them. Performing substring queries to paths through these graphs lies at the core of this task. The combination of increasing pattern length and encoded variations inevitably leads to a combinatorial explosio...

Full description

Saved in:
Bibliographic Details
Published in:Genome Biology 2020-03, Vol.21 (1), p.65-65, Article 65
Main Authors: Mokveld, Tom, Linthorst, Jasper, Al-Ars, Zaid, Holstege, Henne, Reinders, Marcel
Format: Article
Language:English
Subjects:
Bias
Computer Graphics
Decomposition
Genome, Human
Genomes
Genomics
Graph-based reference genomes
Haplotype-aware graph indexes
Haplotypes
Heuristic
Humans
Method
Population
Read alignment
Seeds
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The practical use of graph-based reference genomes depends on the ability to align reads to them. Performing substring queries to paths through these graphs lies at the core of this task. The combination of increasing pattern length and encoded variations inevitably leads to a combinatorial explosion of the search space. Instead of heuristic filtering or pruning steps to reduce the complexity, we propose CHOP, a method that constrains the search space by exploiting haplotype information, bounding the search space to the number of haplotypes so that a combinatorial explosion is prevented. We show that CHOP can be applied to large and complex datasets, by applying it on a graph-based representation of the human genome encoding all 80 million variants reported by the 1000 Genomes Project.
ISSN:1474-760X
1474-7596
1474-760X
DOI:10.1186/s13059-020-01963-y