Tel Aviv University -- Blavatnik School of Computer Science

Seminar 0368-4198-01

Algorithms for Deep Sequencing Data

סמינר: אלגוריתמים לנתוני ריצוף עמוק

http://www.cs.tau.ac.il/~rshamir/seminar/18/NGS18.html

Prof. Ron Shamir

Fall 2018

Thursday 5-7 pm, Schreiber 007

"Next Generation Sequencing" (NGS) techniques for determining the precise sequence of DNA molecules have revolutionized modern biology and medicine. They reduced sequencing costs by a factor of 10,000 within a decade. A typical experiment produces 10 - 100 million DNA sequences (in a four letter alphabet), each 100-200 letters long, which are all segments of the target genome with errors. High volume, high efficiency and low cost have made NGS a "mega-tool" used in hundreds of types of biological and medical measurements. In order to deal with the massive data sets, strong and fast algorithms are required, and the international bioinformatics community is actively occupied with the subject.

In the seminar we will study some of the key algorithms developed in recent years to analyze NGS data. The main methods and concepts that we will cover are de Bruijn graphs, minimizers, universal hitting sets, Bloom filters and Minhash. Both the theoretical properties and applications of these methods will be discussed.

The techniques in the papers that we will discuss come from the areas of algorithms, "stringology", probability and data structures.

Registration: The seminar is open for BSc AND MSc students. Among master students, those in the bioinformatics track will have priority in registration. Other interested students should inquire with the instructor.

Prerequisites: Passing successfully the course Algorithms. The seminar does not require prior knowledge in biology. The basic background in biology will be given in the first meetings.

Course material:

· Syllabus (tentative)

· Guideline for speakers

Plan

Note: dates are tentative and may slightly shift

No.	Date	Speaker	Topic	Paper	Method	Presentation
1	18/10	Ron Shamir	Introduction		Biology background, sequencing	Lecture 1
2	25/10	Ron Shamir	Introduction (2)		Alignment, Suffix trees, Suffix arrays, Burrows-Wheeler Transform	Lecture 2
3	1/11	Lior Wainstein, Eliran Shabat	Winnowing	Scheimer et al., 2003	Winnowing	Lecture 3
4	8/11	Avia Efrat, Ronen Tomer	Minimizers	Roberts et al., 2004	Minimizers	Lecture 4
5	15/11	Dor Alon, Zohar Barak	De Bruijn assembly	Pevzner et al., 2001	EULER	Lecture 5
6	22/11	Ofir Cohen, Yonatan vernik	Compaction	Chikhi et al., 2016	BCALM	Lecture 6
7	29/11	Adar Zaitek, Eyal Golumbic	Compression for assembly	Li et al. 2013	MSP	Lecture 7
8	13/12	Tom Verbin, Dan Lahav	Universal hitting sets	Orenstein et al.	DOCKS	Lecture 8
10	20/12	Veronica Latcinik, Ori Peres	Webpage comparison	Broder 1997	Minhash	Lecture 9
11	3/1/19	Dvir Ginzburg, Yuri Kleiman	Metagenomic distances	Ondov et al., 2016	Mash	Lecture 10
12	10/1	Itay Shamir, Iftach Ginger	k-mer counting	Melsted et al., 2011	BFCounter	Lecture 11

Contact info: email: rshamir AT tau dot ac dot il; phone: 640-5383; office: Schreiber 014; office hours – by appointment

picture credits:

· http://bioinformaticsreview.com/20151005/biominer-intro/

· Time magazine

· https://www.wired.com

· https://www.linkedin.com/pulse/20140923215637-5241481-artificial-intelligence-to-deliver-personalised-medicine

· https://www.whitehouse.gov/blog/2015/01/30/precision-medicine-initiative-data-driven-treatments-unique-your-own-body

· http://www.pathogenomix.com/

· https://jcm.asm.org/content/50/3/857

· http://www.lsuhscshreveport.edu/Research/researchcorefacility/Genomics/Next-Generation-Sequencing/index

·