TechFest Workshop - Theory Day - Session 4
168 views · Published 11 August 2016 · 28:14 · Indexed 12 November 2026
Channel: Microsoft Research · 2016 · Science & Technology
Miklos Racz - Sequence assembly from corrupted shotgun reads Reconstructing a sequence from its short substrings, called reads, is a central problem in DNA sequencing. I will introduce an adversarial error model for the reads, and show that a simple algorithm leads to approximate reconstruction of the original sequence, provided that the reads are long enough and there are sufficiently many of them. Many open questions remain. (Joint work with Shirshendu Ganguly and Elchanan Mossel.)