Simplified pangenome graph traversals with PSSM scoring : search for motifs differentials

Overview & Synopsis

A pangenome Variation Graph (VG) is a data structure that integrates complete information about genetic variations in a species or group of species. Computational pan-genomic is beginning to be discussed as a viable alternative to many standard approaches previously based on sequences. Although in itself a compression of genome sequences, a fundamental problem is the size of this graph (tens to hundreds of millions of nodes): the application of numerous algorithms based on traversals is not possible and heuristics and indexing techniques are necessary to be able to manipulate and query it. We are interested in developing an approach to search for functional differentials in a VG via the detection of sequence pattern changes between the genomes included in the graph. To do so, we search for probabilistic pattern described via a PSSM (Position Specific Scoring Matrix). Our approach aims to output all significant PSSM score differentials that can be extracted from a VG. Note we detect motifs on node boundaries only (the score difference is either null or undefined for motifs inside nodes).