Computer Science Speaking Skills Talk

July 29, 2022 11:00am — 12:00pm

Location:
In Person and Virtual - ET - McWilliams Classroom, Gates Hillman 4303 and Zoom

Speaker:
MINH HOANG , Ph.D. Student, Computer Science Department, Carnegie Mellon University
https://scholar.google.com/citations?user=56Mb6DY0_NUC

DeepMinimizer: A Differentiable Framework for Optimizing Biological Sequence Sketch

Algorithmic complexity attacks (ACAs) are a class of denial-of-service (DoS) attacks where Minimizers are k-mer sampling schemes designed to generate sketches for large sequences that preserve sufficiently long matches between sequences. Despite its widespread application, learning an effective minimizer scheme with optimal sketch size is still an open question. Most work in this direction focuses on designing schemes that work well on expectation over random sequences, which have limited applicability to many practical tools. On the other hand, several methods have been proposed to construct minimizer schemes for a specific target sequence. These methods, however, require greedy approximations to solve an intractable discrete optimization problem on the permutation space of k-mer orderings. To address this challenge, we propose: (a) a reformulation of the combinatorial solution space using a deep neural network reparameterization; and (b) a fully differentiable approximation of the discrete objective. We demonstrate that our framework, DeepMinimizer, discovers minimizer schemes that significantly outperform state-of-the-art constructions on genomic sequences.

Presented in Partial Fulfillment of the CSD Speaking Skills Requirement.

In Person and Zoom Participation. See announcement.

For More Information:
deb@cs.cmu.edu

Add event to Google
Add event to iCal