CHOP: Haplotype-aware path indexing in population graphs

MotivationAlthough the characterization of within species genomic diversity continues to increase, this information is usually not incorporated in the sequencing analysis process. Existing reference genomes can easily be converted to graph-based reference genomes by extending them with known sequence variations. However, the practical use of these 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. We present a solution that uses haplotype information to prevent this from happening.\n\nResultsWe present CHOP, a method that uses haplotype information to retrieve the constrained sequence search space of a graph-based reference genome. Our approach enables typical sequence aligners to perform read alignments to graphs that store any type of variation. CHOP performs similarly to another graph alignment method that unnecessarily indexes all combinations of sequence, while aligning reads to a population reference graph of Mycobacterium tuberculosis genomes. CHOP can achieve increased sensitivity for variation detection by iteratively integrating variation into a graph. Finally, we show that CHOP can be applied to large and complex datasets, by applying it on a graph-based representation of chromosome 6 of the human genome encoding the variants reported by the 1000 Genomes project.