Exploring Frequented Regions in Pan-Genomic Graphs
- Thursday, October 26, 2017 from 3:10pm to 4:00pm
- Wilson Hall, 1-144 - view map
Applied Mathematics Seminar: Brendan Mumey (Dept. of Computer Science)
We consider the problem of identifying regions within a pan-genome de Bruijn graph that are traversed by many sequence paths. We define such regions and the subpaths that traverse them as frequented regions (FRs). In this work, we formalize the FR problem and describe an efficient algorithm for finding FRs (the graphs in question may have millions of vertices and edges). Subsequently, we propose some applications of FRs based on machine-learning and pan-genome graph simplification. We demonstrate the effectiveness of these applications using data sets for the organisms Staphylococcus aureus (bacteria) and Saccharomyces cerevisiae (yeast). We corroborate the biological relevance of FRs such as identifying introgressions in yeast that aid in alcohol tolerance, and show that FRs are useful for classification of yeast strains by industrial use and visualizing pan-genomic space.