Truong, Z. (BMEB) – Efficient distance queries and batch fuzzy search of short DNA sequences on pangenome-scale data

Efficient querying of distances between positions in a pangenome graph is important for applications such as read mapping, but larger graphs tend to have regions of high enough complexity to place them out of reach of practical distance indexing. I will talk about my work using a method called hub labeling with concepts from the road network literature in the vg toolkit’s distance index, which has made indexing whole-genome human pangenome graphs practical with it for the first time.

Efficient batch exact fuzzy search of short DNA sequences has applications to problems such as CRISPR off-target search. However, it is challenging due to the short length and small alphabet size of the queries. I will discuss the algorithm of a novel program, SowingMachine, that preliminary work indicates may perform better than existing approaches.

Event Host: Zia Truong, PhD Student, Biomolecular Engineering & Bioinformatics 

Advisor: Benedict Paten

Zoom: https://ucsc.zoom.us/j/91615897133?pwd=jw0y7UgEVDkblN4NmYEtGkGvs2C17m.1

Passcode: 14810