Algorithmic Bioinformatics

Hannes Hauswedell

BLAST-like Local Alignments with RazerS

Academic Advisor: Knut Reinert , David Weese
Discipline: Bioinformatics
Degree: Bachelor of Science (B.Sc.)
Degree: Oct 01, 2009
Start: Jul 30, 2009
Project:
Status: finished

Abstract

The read mapping tool RazerS should be adapted to perform local alignment verification like BLAST. Furthermore the input parameters and the output format of BLAST should be incorporated into RazerS.

Contents

 

Description:

BLAST stands for Basic Local Alignment Search Tool, and is the de-facto standard for heuristic local alignments. It is often referred to as the most widely employed bioinformatics tool ever, the paper of the first version (Altschul et al., 1990) is the most highly cited paper of the 1990s. With version 2 (Altschul et al., 1997) there have been substantial improvements to performance and amongst other features, support for aligning with gaps was added. Despite its lower speed compared to read mappers, this makes BLAST an attractive choice, even in the field of metagenomics. For instance MEGAN (Huson et al., 2007) – an advanced graphical desktop-application for visualizing and analyzing metagenomic datasets – operates on BLAST output.The obvious question is, can an alternative to BLAST be devised that performs better, especially or at least for a specific use case like metagenomics? This work is to show that it is principally possible to create a local alignment search tool that is faster than BLAST and on the other hand compatible to it in many ways.
To this end, we will create a modified version of RazerS (Weese et al., 2009), called RazerBlastS that – like RazerS – builds upon the high-performance, generic C++-library SeqAn (Döring et al., 2008).

 

Literature:

[1] Altschul, S. F., Gish, W., Miller, W., Myers, E. W., and Lipman, D. J. (1990). Basic local alignmentsearch tool. J Mol Biol, 215(3):403–10.

[2] Huson, D. H., Auch, A. F., Qi, J., and Schuster, S. C. (2007). Megan analysis of metagenomicdata. Genome Res, 17(3):377–86.

[3] Weese, D., Emde, A.-K., Rausch, T., Döring, A., and Reinert, K. (2009). Razers–fast read mapping with sensitivity control. Genome Res, 19(9):1646–54.

Downloads