Ph.D. Student Jamshed Khan Wins Outstanding Student Paper Award

Jamshed Khan, a third-year computer science doctoral student, recently received the Ian Lawson Van Toch Memorial Award for Outstanding Student Paper at the 2021 Conference on Intelligent Systems for Molecular Biology (ISMB) and European Conference on Computational Biology (ECCB).

ISMB is the flagship meeting of the International Society for Computational Biology (ISCB). The event is co-located with ECCB and has grown to become the world’s largest bioinformatics and computational biology conference. The conference was held virtually July 25–30 due to the ongoing COVID-19 pandemic.

The award went to “Cuttlefish: Fast, parallel, and low-memory compaction of de Bruijn graphs from large-scale genome collections,” authored by Khan and his adviser Rob Patro, an associate professor of computer science with an appointment in the University of Maryland Institute for Advanced Computer Studies (UMIACS). The paper introduces a new algorithm for efficiently building a compacted de Bruijn graph from collections of input genome or transcriptome sequences. 

The de Bruijn graph and its colored compacted variant has become an increasingly useful data structure in genomic analysis. The structure is used to assemble new genomes, compare the genomes of related organisms, and build efficient indexes for mapping or aligning the data from sequencing experiments, among other tasks.  

However, the process of building the compacted de Bruijn graph is a computational challenge, with many existing solutions requiring a lot of time and memory as the input becomes larger.

In the paper, Khan and Patro—who are both members of the Center for Bioinformatics and Computational Biology (CBCB)—present a highly scalable and very low-memory algorithm called Cuttlefish, to construct the compacted de Bruijn graph for collections of whole genome references.

The researchers say Cuttlefish considerably outperforms existing state-of-the-art approaches. It can build the compacted de Bruijn graph for 100 human genomes two and half times as fast and using less than a quarter of the memory compared to the next best tool performing the same task.

“By providing a faster and more memory-frugal algorithm for constructing this widely-used structure of the compacted de Bruijn graph, we anticipate that Cuttlefish will aid in some of the many downstream applications in which this graph is used, like comparative genomics, pangenome analysis, and the indexing of large collections of related genomes for sequence analysis,” Patro says.

The Ian Lawson Van Toch Memorial Award for Outstanding Student Paper is given to the student who presents the most thought-provoking or original paper at ISMB/ECCB, as judged by a panel of experts. The award, which is sponsored by the Princess Margaret Hospital Foundation, is given in memory of Ian Lawson Van Toch, a 23-year-old medical biophysics graduate student at the University of Toronto who passed away in August 2007.

Khan says he is honored to receive such a prestigious award.

“We are ecstatic for this recognition of our work,” he says. “I'm very grateful to Rob for his support and guidance along the way, and for being such a remarkable adviser and mentor. I'm also thankful to my talented and dedicated lab-mates for their critiques and feedback. We look forward to Cuttlefish paving the way toward more exciting results in high-throughput genomics research.”

—Story by Melissa Brachfeld