engleski

An SIMD dynamic programming C/C++ library

Deterministic sequence alignment algorithms like Smith-Waterman and NeedlemanWunsch are slow but give optimal result. They are used in many bioinformatic tools as core components and very often they consume significant amount of CPU time. In order to make them faster, different fast implementations have been implemented, many of them performing parallelization using Single Instruction Multiple Data (SIMD) support on CPU or GPU. However, most of these fast implementations are either standalone tool or part of larger tool and were not made to be reusable, which is limiting their usage. In order to make some of this implementations reusable, we implemented two C/C++ libraries for sequence alignment, both based on fast SIMD implementations. SWIMD is library for database search and is based on Rognes’s Faster Smith-Waterman database searches(SWIPE). In our implementation we added one global and two semiglobal alignment methods. We also added support for AVX2 instruction set. We compared SWIMD with currently best implementations like SSW, SSEARCH and SWIPE and showed that SWIMD implementation using AVX2 is the fastest. SWIMD is available from http://github.com/Martinsos/swimd. EDLIB is library for pairwise sequence alignment using edit distance and is based on Myers’s Fast Bit-Vector Algorithm. We added one global and one semi-global alignment method. For global method we have shown how to calculate the band. We also added finding of alignment path. EDLIB is available from https://github.com/Martinsos/edlib. By implementing this two libraries we provided reusable components important for many bioinformatic tools, but also usable for other purposes. We believe this will enable wider usage of fast SIMD algorithms and that many tools could benefit from using them.

bioinformatics; sequence; alignment; SIMD; SSE; AVX2; library; parallelization

nije evidentirano