BEGIN:VCALENDAR
VERSION:2.0
PRODID:icalendar-ruby
CALSCALE:GREGORIAN
X-WR-CALNAME:Bioinformatics Seminar
X-WR-TIMEZONE:Eastern Time (US & Canada)
BEGIN:VEVENT
DTSTAMP:20261015T171029Z
UID:tag:localist.com\,2008:EventInstance_44253193865470
DTSTART:20231018T153000Z
DTEND:20231018T170000Z
DESCRIPTION:Speaker:  William Yu (CMU)\n\nTitle:  Augmenting k-mer sketchin
 g for (meta)genomic sequence comparisons”\n\nAbstract:  Over the last de
 cade\, k-mer sketching (e.g. minimizers or MinHash) to create succinct sum
 maries of long sequences has proven effective at improving the speed of se
 quence comparisons. However\, rigorously characterizing the accuracy of th
 ese techniques has been more difficult. In this talk\, I’ll touch on thr
 ee results that showcase some of the modern theoretical developments and p
 ractical applications of theory to building faster sequence comparison too
 ls for metagenomics. We begin by rigorously providing average-case guarant
 ees for the popular seed-chainextend heuristic for pairwise sequence align
 ment under a random substitution model\, showing that it is accurate and r
 uns in close to O(n log n) time for similar sequences. Then\, we will turn
  our focus to metagenomics: our new tool skani computes average nucleotide
  identity (ANI) using sparse approximate alignments\, and is both more acc
 urate and over 20 times faster than the current state-of-the-art FastANI f
 or comparing incomplete\, fragmented MAGs (metagenome assembled genomes). 
 This was enabled by Belbasi\, et al.’s work showing that minimizers are 
 biased Jaccard estimators\, whereas other k-mer sketching does not have th
 at drawback. Finally\, we will introduce sylph (unpublished work)\, which 
 enables fast and accurate database search to find nearest neighbor genomes
  (in ANI space) of low-coverage sequenced samples by using a combination o
 f kmer sketching with a zero-inflated Poisson correction (45x faster than 
 MetaPhlAn for screening databases). All of the work in this talk is joint 
 with my brilliant PhD student Jim Shaw. Shaw J\, Yu YW. Proving sequence a
 ligners can guarantee accuracy in almost O (m log n) time through an avera
 ge-case analysis of the seed-chain-extend heuristic. Genome Research (2023
 ) 33 (7)\, 1175-1187 Shaw J\, Yu YW. Fast and robust metagenomic sequence 
 comparison through sparse chaining with skani. Nature Methods (2023). \n\n
 In person or on Zoom at https://mit.zoom.us/j/93513735220
LOCATION:MIT\, 32-G575
SUMMARY:Bioinformatics Seminar
URL;VALUE=URI:https://calendar.mit.edu/event/bioinformatics_seminar_2740
END:VEVENT
END:VCALENDAR