Projektmanagement im Softwarebereich - Seqan 2010
Das ist die vorläufige Wiki-Seite zum Praktikum
Projektmanagement im Softwarebereich - Seqan.
Aufteilung auf die Teilprojekte
Name |
Teilprojekt |
Anne-Marie Tumescheit |
Modul 1 |
Swantje Tielemann |
Modul 2 |
Anke Penzlin |
Modul 3 |
Michal Krivan |
Modul 4 |
Grundlagen
Lesen Sie die Kapitel 1-3 aus [1]. Empfehlenswert ist außerdem das VL-Skript [7] (4.4-4.6 kann übersprungen werden).
Reads
0.1-50 Mio. kurze DNA-Sequenzen der Länge 36-150bps.
Read Match
Ein Teilstück g eines Referenzgenoms (bspw. NCBI Human Genome), das zu einem Read r höchstens Hamming- bzw. edit-Distanz k.
k ist eine vorgegebene maximale Fehlerzahl.
Q-gram threshold
Gegeben sei ein shape Q (bspw. 110010110111100111) und ein Read r der Länge m.
Wenn g ein Match von r ist, wieviele Q-gramme haben g und r mindestens gemeinsam? Siehe Kapitel 3 in [1].
Diese Mindestanzahl nennen wir die Q-gram treshold t.
Das Projekt
Ziel dieses Praktikums ist, einen Seed und einen q-gram basierten Read Mapper zu implementieren.
- Input
- Eine Menge von DNA-Reads als Fasta-Datei, Referenzsequenzen als Fasta-Datei und eine maximale Fehlerzahl k.
- Output
- Alle Read Matches im SAM-Format [5].
Die gefundenen Matches können mit den samtools [5] visualisiert werden.
Zum Testen der Read Mapper können Sie Reads und Genom mit dem
ReadSimulator [6] erzeugen und überprüfen, ob diese an den Herkunftsstellen wiedergefunden werden.
Teilprojekte
Modul 1 - Berechnung der Threshold von beliebigen Q-gram shapes
Exakte Berechnung
Der Algorithmus aus Kapitel 4 in [1] berechnet die exakte Q-gram Threshold t zu gegebenen Q, m und k.
Heuristische Berechnung
Dieser einfache heuristische Algorithmus gibt eine obere Abschätzung von t (vgl. mit [2]):
- Sei A die Menge aller Q-gramme eines Patterns der Länge m
- Wähle eine Fehlerposition i, 1<=i<=m, die von maximal vielen Q-gramme aus A überdeckt wird und entferne letztere aus A.
- Wiederhole Schritt 2 k-mal.
- t ist die höchstens so groß wie |A|.
Schreiben Sie ein Modul, das:
- Q-gramme aus einer Datei einliest (siehe Shapes.txt in den Attachments).
- eine Funktion bereitstellt, die zu geg. m und k mit dem DP-Algorithmus ein Q-gram mit möglichst vielen Einsen und t>0 auswählt.
- Vergleichen Sie die Ergebnisse beider Algorithmen für alle Q aus Shapes.txt (siehe Attachments), m=36,50,75,100 und k=1,..,10.
Modul 2 - Filter basierend auf dem Schubfachprinzip
Nach Schubfachprinzip gilt: Teilt man einen Read in k+l Teile, muss jeder Match mit höchstens k Fehlern mindestens l Teile mit dem Read gemein haben. Es soll ein Filter für l=2 implementiert werden, der nach Reads mit bis zu k Mismatches in den Dna-Sequenzen sucht. Siehe [3].
Wie lässt sich dieser Filter auf edit-Distanz erweitern?
Schreiben Sie ein Program, das:
- Reads aus einem Fasta-File einliest.
- zu einer wählbaren max. Fehlerzahl k alle potential matches nach Schubfachprinzip findet.
Modul 3 - Filter basierend auf dem Zählen von Q-grammen
Quasar [4],[7] ist ein Q-gram basierter Filter der genomische Regionen herausfiltert die garantiert keine Read Matches enthalten.
Die übrigen Region können evtl. matches enthalten und heißen potential matches.
Quasar sucht nach genomischen Regionen die mind. t Q-gramme mit einem Read gemeinsam haben.
Schreiben Sie ein Program, das:
- Reads aus einem Fasta-File einliest.
- zu einer wählbaren max. Fehlerzahl k mittels Modul 1 ein geeignetes Q mit zug. t auswählt.
- alle potential matches mit t gemeinsamen Q-grammen findet.
Modul 4 - Match Verifikation und Ausgabe
Die potential matches aus Schritt 3 müssen auf tatsächliche matches verifiziert werden.
Unterstützt werden soll Hamming- und edit-Distanz.
Schreiben Sie ein Modul, das:
- alle von Modul 2 bzw 3 gefundenen Matches verifiziert.
- tatsächliche Matches mit Anfangs-, Endposition und Id der Genomsequenz sammelt.
- alle Matches im SAM-Format in eine Datei ausgibt.
Referenzen
Achtung: Die Paper-Links gehen nur von der FU (bzw. VPN) aus.
[1] Stefan Burkhardt, Juha Kärkkäinen,
Better Filtering with Gapped q-Grams,
Fundamenta Informaticae, 2003
[2]
http://en.wikipedia.org/wiki/Maximum_coverage_problem
[3] Anthony Cox, ELAND, unpublished,
http://www.fejes.ca/2008/01/aligning-dna-eland.html
[4] Stefan Burkhardt, Andreas Crauser, Paolo Ferragina, Hans-Peter Lenhof, Eric Rivals, Martin Vingron,
q-gram Based Database Searching Using a Suffix Array (QUASAR),
RECOMB, 1999
[5] SAM tools and format,
http://samtools.sourceforge.net/
[6] Read Simulator,
http://svn.mi.fu-berlin.de/seqan/trunk/seqan/projects/library/apps/seqcons/read_simulator.R
[7] Vorlesung
Fast Filtering Algorithms, P4 SS09