Sommersemester 2011: Formale Methoden zur Rekonstruktion und Analyse von Netzwerken

Vorbesprechung: erster Montag im Semester, Montag, 04.04.2011, 17:00 Uhr in OH14, R202.
Details und ein genauer Zeitplan werden bei der Vorbesprechung festgelegt; dort stelle ich auch die einzelnen Artikel kurz vor.

Wichtig: Vorkenntnisse in der Bioinformatik (z.B. Prüfung/Leistungsnachweis "Rekonstruktion biologischer Netzwerke", "Algorithmische Bioinformatik", oder "Algorithmen auf Sequenzen") sind unbedingt notwendig.
Bei Interesse schicken Sie bitte vor Semesterbeginn eine e-mail.

Inhalt: Im Sommersemester 2011 befasst sich das Seminar mit aktuellen Originalarbeiten zum Thema Netzwerke in der Biologie und schließt sich damit auch an die Spezialvorlesung des letzten Wintersemesters an. Ein voriger Besuch der Spezialvorlesung ist erwünscht, aber nicht unbedingt notwendig.

Termin: Blockseminar am Samstag 25.06. ab 09:00 Uhr in OH14, R202.

Zeitplan:
04.04. Vorbesprechung, Verteilung der Arbeiten
April    immer  montags 14-16 bzw. ab 17 Uhr: Möglichkeit zur Diskussion der Artikel, bitte vorab per e-mail melden.
18.04. Abgabe einer groben Vortragsplanung (dazu müssen Sie den Artikel mehrfach gelesen und ermittelt haben, welche Grundlagen noch aufgearbeitet werden müssen).
Mai     immer  montags 14-16 bzw. ab 17 Uhr: Möglichkeit zur Diskussion der Artikel, bitte vorab per e-mail melden.
30.05. (bzw. spätestens eine Woche vor den Vorträgen) Abgabe der Folien als pdf
25.06. ab 9 Uhr: Vorträge in OH14/R202
15.07. (spätestens) Abgabe der ersten Version der Ausarbeitung
26.08. (spätestens) Abgabe der finalen Version der Ausarbeitung
Kurz darauf werden bei erfolgreicher Teilnahme die Seminarscheine ausgestellt.

---

Wintersemester 2010/11: Next Generation Sequencing

Termin: Im WS2010/11 jeweils Montags 14-16 in OH14, R202.
Vorbesprechung: erster Montag im Semester, Montag, 11.10.2010, 14 Uhr in OH14, R202
Danach stehe ich an jedem Montag für die Betreuung zur Verfügung und gebe weiter Hintergrundinformationen.
Die Vorträge beginnen dann einige Wochen nach Semesterbeginn, ggf. wird es einen Block gegen Semesterende geben.
Details und ein genauer Zeitplan werden bei der Vorbesprechung festgelegt; dort stelle ich auch die einzelnen Artikel kurz vor.
Wichtig: Vorkenntnisse in der Sequenzanalyse (z.B. Prüfung/Leistungsnachweis "Algorithmen auf Sequenzen") sind unbedingt notwendig.
Bei Interesse schicken Sie bitte vor Semesterbeginn eine e-mail.

Wir diskutieren aktuelle Entwicklungen im Bereich der DNA-Sequenziertechnologien und neuer Anwendungen. Dabei legen wir vor allem Wert auf die Herausarbeitung der algorithmischen Fragestellungen, die sich hierbei ergeben, und ihrer Lösungsansätze. Vorgestellt werden verschiedene Kombinationen aus Technologie, Anwendung und Algorithmen an Hand verschiedener aktueller Artikel aus einer Sonderausgabe der Zeitschrift Bioinformatics, nämlich der Sonderausgabe "Next Generation Sequencing 2010". Es gibt eine online-Liste dieser und älterer Artikel. Ggf. soll es je einen Übersichtsvortrag zu Technologien, Grundlegenden Fragestellungen und Anwendungen geben.

Sequenziertechnologien sind beispielsweise:

• 454 von Roche
• Illumina
• SOLiD von ABI
• Helicos
• Pacific Biosciences
  
• IonTorrent
  

Grundlegende Fragestellungen sind beispielsweise:

• Base Calling und Quality Control
• Standardisierung von Dateiformaten für Sequenzen und Alignments
• Read Mapping und Alignment
• Assembly von Reads
• Konstruktion von Analyse-Pipelines
• Visualisierung
  

Anwendungen sind beispielsweise:

• De novo Sequencing von Genomen
• Resequencing von Genomen (oder Teilen), Entdeckung von Variationen
• RNA-seq: Messung von Genexpression
• ChIP-seq
• Darauf jeweils aufbauend: Diagnose von Krankheiten
  

Im Einzelnen sollen folgende Arbeiten besprochen werden:

(Base calling)
Correction of sequencing errors in a mixed set of reads
Leena Salmela
Bioinformatics (2010) 26: 1284-1290 Full Text

(Read Mapping and Alignment, Vortrag von Fabian Bienek)
Fast and Accurate Short Read Alignment with Burrows-Wheeler Transform
Li Heng and Richard Durbin
Advanced Access publication: 18 May 2009 Full Text

(Read Mapping and Alignment)
MicroRazerS: Rapid alignment of small RNA reads
Anne-Katrin Emde et al.
Bioinformatics (2010) 26: 123-124 Full Text

(Nucleotide-level Variation)
SNVMix: predicting single nucleotide variants from next generation sequencing of tumors
Rodrigo Goya et al
Advanced Access publication: 3 February 2010 Full Text

(Nucleotide-level Variation)
Fast and SNP-tolerant detection of complex variants and splicing in short reads
Thomas Wu and Serban Nacu
Advanced Access publication: 10 February 2010 Full text

(Structural Variation, Vortrag von Henning Timm)
Detection and characterization of novel sequence insertions using paired-end next-generation sequencing
Iman Hajirasouliha et al.
Bioinformatics (2010) 26: 1277–1283 Full Text

(Structural Variation)
Structural Variation Analysis with Strobe Reads
Anna Ritz et al.
Bioinformatics (2010) 26: 1291-1298 Full Text

Zeitplan WS 2010/11

Mo 11.10.2010	Vorbesprechung, Themenvergabe. DNA-Sequenziertechnologien.
Mo 18.10.	Erarbeitung der Kurzzusammenfassungen (1 Seite)
Mo 25.10.	Abgabe und der Kurzzusammenfassungen. Hinweise zu Seminarausarbeitungen. Besprechung der Kurzzusammenfassungen.
Mo 01.11.	--- (Allerheiligen)
Mo 08.11.	Technologie-Übersicht (siehe Technologien oben und Material)
Mo 15.11.	Sven Rahmann: Deep microRNA sequencing reveals differential expression in favorable versus unfavorable neuroblastoma tumors
Mo 22.11.	Diskussion der Artikel
Mo 29.11.	Abgabe 1. Version der Folien, Diskussion der Artikel
Mo 06.12.	Diskussion der Artikel
Mo 13.12.	Fabian Bienek: Fast and Accurate Short Read Alignment with Burrows-Wheeler Transform
Mo 03.01.2011	Henning Timm: Detection and characterization of novel sequence insertions using paired-end next-generation sequencing
Mo 10.01.	Hinweise zu LaTeX-Ausarbeitungen
Mo 17.01.	Fragen zu Ausarbeitungen
Mo 24.01.	Fragen zu Ausarbeitungen
Mo 31.01.	Abschlussbesprechung

---

Wintersemester 2009/10: Compressed Full Text Self Indexes

Wir wollen den aktuellen Stand der Forschung und Implementierung im Bereich der sogenannten compressed full text self indexes erarbeiten. Hierbei geht es um folgende Problemstellung: Man hat einen sehr langen (mehrere GB bis TB) Text (z.B. 1000 Genome zu je 3 GB) und möchte diese einerseits platzsparen abspeichern (Kompression) und bei Bedarf jeden Teilstring (oder den kompletten Text) wieder extrahieren (extraction), andererseits effizient Suchanfragen beantworten wie: Wie oft kommt die Sequenz AGGTCCAAT insgesamt vor (counting)? Wo überall (locating)?

Hierzu gibt es seit ca. 10 Jahren hochinteressante Entwicklungen: Mit geeigneten Datenstrukturen ist es z.B. möglich, das menschliche Genom (ca. 3 GB) in ca. 1 GB Hauptspeicher zu speichern und zu indizieren. Komprimierter Text und Index benötigen also weniger Platz als der (nicht komprimierte) Text selbst.

Im Seminar werden sowohl die methodischen Grundlagen erarbeitet als auch aktuelle Implementierungen vorgestellt.
Das Material ist relativ anspruchsvoll. Solide Kenntnisse in Algorithmen und Datenstrukturen sind unbedingt erforderlich.

Grundlage sind die folgenden Übersichtsartikel, aus denen einzelne Abschnitte als Themen vergeben werden.
Dabei muss i.d.R. weiterführende im Abschnitt genannte Literatur zusätzlich erarbeitet werden.

1. [NM07] Navarro, G. and Mäkinen, V. 2007. Compressed full-text indexes. ACM Comput. Surv. 39, 1 (Apr. 2007), 2. [http://doi.acm.org/10.1145/1216370.1216372]
2. [FGNV09] Ferragina, P., González, R., Navarro, G., and Venturini, R. 2009. Compressed text indexes: From theory to practice. J. Exp. Algorithmics 13 (Feb. 2009), 1.12-1.31. [http://doi.acm.org/10.1145/1412228.1455268]

Anmeldungen bitte vorab per email an den Veranstalter.

• Ort und Zeit: Mo 14-16 in OH14, R202
• Vorbesprechung: am ersten Termin, 12.10.2009

Ablauf: Wir werden die Artikel gemeinsam erarbeiten. Für jedes Treffen wird ein zu lesender Abschnitt und ein/e Verantwortliche/r festgelegt. Der Abschnitt soll als Kurzvortrag präsentiert werden. Im Anschluss sollen dazu Detailfragen von allen (auch vom / von der Vortragenden) gestellt und von allen gemeinsam beantwortet werden, sowie Beispiele konstruiert und verstanden werden. Zu den Themen des Verantwortungsbereichs soll eine Ausarbeitung angefertigt werden. Dabei gelten die Hinweise zu Seminarausarbeitungen. Die Ausarbeitungen sind spätestens 2 Wochen nach dem entsprechenden Seminardartum abzugeben.

Termine

Mo 12.10.	Übersicht, Vorbesprechung.	Prof. Rahmann
Mo 19.10.	[NM07] 1-3 und [FGNV] bis 2.1 einschließlich	Prof. Rahmann
Mo 26.10.	-- fällt aus --
Mo 02.11.	[NM07] 4	Daniel Richter
Mo 09.11.	[NM07] 5	Christian Wiener
Mo 30.11.	[NM07] 6	Daniel Richter
Mo 07.12.	[NM07] 7	Christian Wiener
Mo 14.12.	[NM07] 8	Prof. Rahmann

---

Sommersemester 2009

Nach Absprache sind einzelne individuelle Bioinformatik-bezogene Themen aus der aktuellen Forschungsliteratur zu vergeben.
Es ist sinnvoll und hilfreich, im letzten Semester die "Algorithmische Bioinformatik" (oder im vorletzten die "Algorithmen auf Sequenzen") gehört zu haben.

• Ort und Zeit: Mo 14-16 in OH14, R202
• Vorbesprechung: am ersten Termin, 20.04.2009

Folgende Themen stehen zur Verfügung:

Thema	Arbeitsgebiet
Accelerating Boyer-Moore searches on binary texts	Stringalgorithmen
Burrows-Wheeler transform and palindromic richness	Stringalgorithmen
Compressing DNA sequence databases with coil	Stringalgorithmen, Informationstheorie
Lossless filter for multiple repeats with bounded edit distance	Stringalgorithmen, Sequenzanalyse
ProbeMatch: a tool for aligning oligonucleotide sequences und weitere(!)	Sequenzanalyse
Visualisation of genomic data with the Hilbert curve	Visualisierung
The simultaneous consecutive ones problem	Kombinatorische Optimierung
Evolving DNA motifs to predict GeneChip probe performance	Evolutionäre Algorithmen, Microarrays
Markov clustering versus affinity propagation for the partitioning of protein interaction graphs	Protein-Interaktionen, Clustering

Zeitplan:

Datum (Mo.)	Thema	Vortragende/r
20.04.2009	Vorbesprechung	Sven Rahmann
25.05.2009	Predicting the subcellular location of proteins	Nils Hammerla
01.06.2009	(Pfingstmontag)	-
08.06.2009	ProbeMatch: a tool for aligning oligonucleotide sequences (und weitere)	David Schichowski
15.06.2009	Evolving DNA motifs to predict GeneChip probe performance	Martin Sawatzki
22.06.2009	Efficient Algorithms for the Computational Design of Optimal Tiling Arrays	Timo Stöcker
29.06.2009	(ISMB, Stockholm)	-
06.07.2009	BWT and palindromic richness	Sebastian Jerosch
13.07.2009	Accelerating Boyer-Moore on binary texts	Finn Siebert
20.07.2009	Simultaneous Consecutive-Ones Problems	Julianna-Katalin Sipos

---

Wintersemester 2008/09

Zeit und Ort: Montags 14-16 in OH14, R203.
Termine:
Mo 13.10. Vorbesprechung
Mo 03.11. Sven Rahmann: Support Vector Machines (01)
Mo 10.11. Tobias Marschall: ENCODE (02)
Mo 17.11. Marcel Martin: The Fragment Assembly String Graph (03)
Mo 24.11. Markus Chimani: Exact Crossing Minimization (Disputationsvortrag, in E04, 13:00)
Mo 08.12. Stefan Pöter: Struktur regulatorischer Netze (07)
Mo 15.12. Tian Zhang: MapReduce (04)
Mo 05.01. Sven Rahmann: Brainbow (08) + Wie schreibe ich eine Ausarbeitung?
Mo 12.01. Ruxandra Cernat: Alignment-Statistik (06)
Mo 19.01. Simona-Claudia Florescu: MotifCut (09)
Mo 26.01. Dominic Storz: Cache-Oblivious Dynamic Programming for Bioinformatics (05)
Mo 02.02. Schlussbesprechung

---

Sommersemester 2008: Analyse großer Datenmengen

Zeit und Ort: Montags 14-16 in OH14, R203.
Termine:
Mo 14.04. Vorbesprechung
Mo 28.04. (1) Sven Rahmann: "Genes" von Prohaska & Stadler (2008)
Mo 05.05. (2) Marcel Martin: "Shotgun bisulphite sequencing of the Arabidopsis genome reveals DNA methylation patterning" von Cokus & al (2008)
Mo 19.05. (3) Karl Becker: "Predicting Molecular Formulas of Fragment Ions with Isotope Patterns in Tandem Mass Spectra" von Zhang & al (2005)
Mo 02.06. (4) N.N.: "Phylogenetic classification of short environmental DNA fragments" von Krause & al (2008)
Mo 09.06. (5) Tobias Marschall: "Probabilistic arithmetic automata and their applications to pattern matching statistics" von Marschall & al (2008).
Mo 16.06. (6) Hüseyin Kagba: "Abstract shapes of RNA" von Giegerich & al (2004)
Mo 23.06. (7) Nico Piatkowski: "Asymptotics of RNA shapes" von Lorenz & al (2008)
Mo 14.07. Schlussbesprechung