Title: Fragment assembly
Speakers: Baharak Rastegari and Philip Lam
Abstract In this reading group session, we are going to present the Fragment Assembly problem. This problem arise from the "shortgun method", which breaks a given piece of DNA into several smaller pieces that can be sequenced. The goal is to reconstruct the original DNA string. We can write the problem in this informal way: "Given several strings of DNA, construct the "best" superstring that contains them all". There are several models for this problem, we are going to focus on the simplest Shortest Common Superstring (SCS) problem:
Input: A collection F of strings
Output: A string S, as short as possible, such that for every f in F, S is a superstring of f.

This problem was proven to be NP-hard complete, we are going to discuss the proof of that.