INESC-ID   Instituto de Engenharia de Sistemas e Computadores Investigação e Desenvolvimento em Lisboa
technology from seed


Knowledge Discovery and Bioinformatics
Inesc-ID Lisboa

Parallel efficient alignment of reads for re-sequencing applications

09/26/2013 - 14:30
09/26/2013 - 15:30

In bioinformatics, in the context of resequencing projects,
the e cient and accurate mapping of reads to a reference
genome is a critical problem. One instance of this problem
is the local alignment of pyrosequencing reads produced
by the 454 GS FLX system against a reference sequence,
an instance for which the software tool TAPyR (Tool for
the Alignment of Pyrosequencing Reads) was developed.
TAPyR implements a methodology to e ciently solve this
problem, which proved to yield results of a quality (both in
terms of content and execution speed) higher than those of
mainstream applications. With the goal of further improving
this platform's results, we produced a parallel implementation
of the query and reference sequence access procedures
of the original version. Through the use of multithreading,
this new version, P-TAPyR, produces considerable
reductions in the processing time of queries, scaling with
the amount of hardware-supported threads (not accounting
for hyper-threading) available. For larger data sets, we
were able to observe running times roughly 26 times faster
than serial execution with 30 executing threads, showing
an experimental (progressively-decreasing) execution serial
fraction of 0.8% (determined by the Karp-Rabin Metric described
in a posterior section). Herein we present the modi
cations made to this software tool to allow for parallel
querying of reads against an indexed reference which, scales
proportionally to the amount of available physical cores.