Eine vergleichende Studie von BLAST-Algorithmen

Aufgabenstellung

BLAST (Basic Local Alignment Tool) ist das bekannteste Programm zur Identifizierung von lokalen Alignments zwischen Sequenenzen. Die Implementierung von NCBI (National Center for Biotechnology Information) ist sehr komplex und schwer zu verstehen. Für die SeqAn Bibliothek wird im Rahmen einer Bachelorarbeit vom zehn Wochen eine einfachere Variante implementiert und mit dem NCBI Programm verglichen. Die Algorithmischen Komponenten orientieren sich an der ersten BLAST Version (Altschul et al., 1990).

Softwarekomponenten

Das SeqAn BLAST Tool soll aus folgenden Teilprogrammen bestehen.

Teilprogramm	Datensätze
Blastn	Nukleotid-Datenbank : Nukleotid-Query
Blastp	Protein-Datenbank : Protein-Query
Blastx	Protein-Datenbank : Nukleotid-Query

In jedem Teilprogramm kommte es zur:

• Identifizierung von High Scoring Words (HSW)
• Treffer Suche mit Aho-Corasick-Automat
• und zur Erweiterung der Treffer zu High Scoring Segement Pairs (HSP)

Zeitplan

	Zeitraum
Recherche	17.06.13 - 01.07.13
Internet Recherche, Paper lesen	17.06.13 - 21.06.13
Algorithmus erfassen	19.06.13 - 21.06.13
Programmplanung	24.06.13 - 01.07.13
Implementierung und Testen	02.07.13 - 22.07.13
Blastp	02.06.13 - 08.06.13
Blastn	09.06.13 - 15.07.13
Blastx	16.06.13 - 22.07.13
vergleichende Tests und Laufzeitanalysen	23.07.13 - 05.08.13
Laufzeitanalysen	23.07.13 - 25.07.13
Analyse Sensitivität und Spezifität	26.07.13 - 30.07.13
Vergleich mit NCBI BLAST	26.07.13 - 05.08.13
Schreibphase	06.08.13 - 26.08.13

Comments