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]):
  1. Sei A die Menge aller Q-gramme eines Patterns der Länge m
  2. Wähle eine Fehlerposition i, 1<=i<=m, die von maximal vielen Q-gramme aus A überdeckt wird und entferne letztere aus A.
  3. Wiederhole Schritt 2 k-mal.
  4. t ist die höchstens so groß wie |A|.

Schreiben Sie ein Modul, das:
  1. Q-gramme aus einer Datei einliest (siehe Shapes.txt in den Attachments).
  2. 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.
  3. 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:
  1. Reads aus einem Fasta-File einliest.
  2. 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:
  1. Reads aus einem Fasta-File einliest.
  2. zu einer wählbaren max. Fehlerzahl k mittels Modul 1 ein geeignetes Q mit zug. t auswählt.
  3. 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:
  1. alle von Modul 2 bzw 3 gefundenen Matches verifiziert.
  2. tatsächliche Matches mit Anfangs-, Endposition und Id der Genomsequenz sammelt.
  3. 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

Comments

 
Topic attachments
I Attachment Action Size Date Who Comment
Shapes.txttxt Shapes.txt manage 0.6 K 31 Mar 2010 - 12:04 DavidWeese Menge von q-gram shapes, nach absteigendem q geordnet
Topic revision: r9 - 23 Mar 2011, DavidWeese
 
  • Printable version of this topic (p) Printable version of this topic (p)