F2.large.jpg

ION Torrent chip

Personalized-medicine

https://english.tau.ac.il/sites/default/files/media_server/marina/English/logo580.jpg

sequencing5.jpg

Illumina's HiSeq

https://media.licdn.com/mpr/mpr/p/1/005/08a/125/171fed4.jpg

 

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

           

 

 

 

 

 

 

 

 

 

 

http://hitwebcounter.com/counter/counter.php?page=4814763&style=0005&nbdigits=5&type=page&initCount=0