Investigating Frequented Regions (FRs) in a Yeast Pan-Genome

Traditionally, genomes have been related back to a single reference genome representing the species or even an entire evolutionary branch containing multiple species. In the current era where next generation sequencing technologies (most importantly second and third) have facilitated genome sequencing and assembly of multiple accessions per species to an unmanageable scale, the need for pan‐genomic algorithms to mine biological information from multiple genomes has become critical. A pan‐genome can be represented at the nucleotide base-pair level in the form of a de Bruijn graph. In this work we consider the problem of determining regions within a de Bruijn graph that are well-traveled in the sense that many sequences traverse the region. We term such regions and the associated subpaths as frequented regions (FRs) and investigate approaches to finding FRs in large pan-genomic data sets. We formalize the FR problem, discuss its computational complexity, and describe a heuristic algorithm for mining FRs. We demonstrate the relevance of the FR problem by applying the algorithm to a yeast pan-genome, the results of which corroborate the existing Yeast knowledge base. Additionally, we address the problem of visualizing pan-genomes - a mountainous task. By using FRs as a means of graph filtration, the complexity of the visualization can be greatly reduced and used to address specific biological questions.