Schnelle Blastsuche durch Datenbank-Clustering

Hintergrund:

Der Vergleich von Next Generation Sequencing (NGS) Daten gegen DNA- oder Proteindatenbanken gehoert mittlerweile zu den Standardaufgaben in der bioinformatischen Sequenzanalyse. Gerade fuer die Suche lokaler Aehnlichkeiten stellt die Groesse von NGS Datensaetzen und der immer umfangreicheren Datenbanken ein Problem dar. Es wird quasi unmoeglich, jede Sequenz mit jeder exakt zu vergleichen. Ein Ansatz um dies zu umgehen, ist das Vorbearbeiten und Filtern der zu untersuchenden Datenbanksequenzen. Parsons [1] und Edgar [2] benuzten hier den Ansatz des Clusterns: Nach und nach wird ein zunaechst leeres Clustering von Sequenzen anhand lokaler Aehnlichkeit zwischen den Sequenzen aufgebaut. Aehnelt eine neue Sequenz einer Referenzsequenz eines Clusters, wird dieses dem Cluster zugeordnet, sonst wird ein neues Cluster aufgemacht. Benutzt man solch ein Cluster zur Suche bzw. zum Datenbankvergleich, vergleicht man seine Seqeunzen zunaechst nur mit den Referenzsequenzen der Cluster und nur bei ausreichender Aehnlichkeit werden auch die restlichen Sequenzen im Cluster verglichen.

Aufgabe 1 - Clustering von DNA-Sequenzen anhand lokaler Matches

Ziel dieser Aufgabe ist es, eine Menge von DNA-Sequenzen anhand lokaler Aehnlichkeit zu clustern.

1. Einlesen von DNA-Datenbanksequenzen
2. Aufbau einer Clusterdatenstruktur
3. Clustern der Sequenzen anhand der Berechnung lokaler Matches (Smith-Waterman, Stellar, …)
4. Herausschreiben des Clusters in FASTA Format (Eingabe zu Aufgabe 2)

Aufgabe 2 - Lokale Suche von DNA-Sequenzen

Ziel dieser Aufgabe ist es, lokale Aehnlichkeiten von Sequenzen in einem Cluster von Referenz-Sequenzen zu suchen.

1. Einlesen eines Clusters von DNA-Datenbanksequenzen (Ausgabe aus Aufgabe 1) und Aufbau der Clusterdatenstruktur, Einlesen von DNA-Querysequenzen
2. Einschraenken des Suchraumes fuer den Sequenzvergleich mithilfe des Clusters (Filtern)
3. Suche der Querysequenzen auf den gefilterten Referenzsequenzen
4. Ausgabe der Matches

Anmerkungen:

Pro Student soll eine Aufgabe bearbeitet werden. In einem Zweierteam koennen gemeinsam Datenstrukturen und Interfaces entwickelt werden, die in den einzelnen Aufgaben (wieder)verwendet werden koennen.

References

• [1] J.D. Parsons, Improved tools for DNA comparison and clustering, Bioinformatics 1995
  
• [2] R.C. Edgar, Search and clustering orders of magnitude faster than BLAST, Bioinformatics Applications Note 2010