| 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.
|