parasail: Pairwise Sequence Alignment Library

master:

develop:

Author: Jeff Daily (jeffrey.daily@gmail.com)

Table of Contents

• Introduction
• Instruction Sets and CPU Dispatching
• Compiling and Installing
  • autotools build
  • CMake build
  • Meson build
  • Cross-Compiling for ARM
• C Interface Example
  • Standard Function Naming Convention
  • Function Dispatchers
  • Profile Function Naming Convention
  • Substitution Matrices
  • SSW Library Emulation
  • Function Lookup
  • Banded Global Alignment
  • Position-Specific Scoring Matrix Alignment
  • File Input
  • Tracebacks
• Language Bindings
  • C/C++
  • Python
  • Rust
  • Java
• Windows Build
• Example Applications
• Citing parasail
• License: Battelle BSD-style

Introduction

[back to top]

parasail is a SIMD C (C99) library containing implementations of the Smith-Waterman (local), Needleman-Wunsch (global), and various semi-global pairwise sequence alignment algorithms. Here, semi-global means insertions before the start or after the end of either the query or target sequence are optionally not penalized. parasail implements most known algorithms for vectorized pairwise sequence alignment, including diagonal [Wozniak, 1997], blocked [Rognes and Seeberg, 2000], striped [Farrar, 2007], and prefix scan [Daily, 2015]. Therefore, parasail is a reference implementation for these algorithms in addition to providing an implementation of the best-performing algorithm(s) to date on today's most advanced CPUs.

parasail implements the above algorithms currently in three variants, 1) returning the alignment score and ending locations, 2) additionally returning alignment statistics (number of exact matches, number of similarities, and alignment length), and 3) functions that store a traceback for later retrieval as a SAM CIGAR string. The three variants exist because parasail is intended to be high-performing; calculating additional statistics or the traceback will perform slower than simply calculating the alignment score. Select the appropriate implementation for your needs.

Note: When any of the algorithms open a gap, only the gap open penalty alone is applied.

Instruction Sets and CPU Dispatching

[back to top]

parasail supports the SSE2, SSE4.1, AVX2, AltiVec, and NEON instruction sets. In many cases, your compiler can compile source code for an instruction set which is not supported by your host CPU. The code is still compiled, however, parasail uses CPU dispatching at runtime to correctly select the appropriate implementation for the highest level of instruction set supported. This allows parasail to be compiled and distributed by a maintainer for the best available system while still allowing the distribution to run with a lesser CPU.

Compiling and Installing

[back to top]

The GNU autotools-based installation is the preferred method, though the CMake build works just as well. There is also a contributed Meson build. The various build files are provided because it often makes it easier to include parasail as a submodule inside other projects using one a preferred build tool. Every attempt has been made to make installation a smooth process. For example, there are no required external dependencies. However, if you still run into issues, please file an issue.

autotools build

If you are building from a git clone, the autotools files must first be generated using autoreconf -fi. The custom source distributions will already contain generated autotools files.

parasail follows the typical configure, make, make install steps of other GNU autotools-based installations. By default, this will build both a static and shared library as well as the parasail_aligner application. There is no automated test suite at this time, but running make check will build some additional test programs such as test_isa for reporting your compiler and CPU capabilities.

By default, running "make install" will install parasail into /usr/local. You will find the parasail.h header in /usr/local/include and the parasail library, e.g., libparasail.a, in /usr/local/lib. If you specify a different prefix during configure, for example configure --prefix=/some/other/path, then look within the include and lib directories there for the parasail.h header and libparasail.so library, respectively.

Don't forget to link your application to the parasail library. For example, gcc foo.c -I/where/you/installed/include -L/where/you/installed/lib -lparasail. Otherwise, you'll see errors such as undefined reference to 'parasail_sw'.

CMake build

The CMakeLists.txt file will compile and link the parasail library as well as the parasail_aligner application and the test_isa test program. It builds some of the other test programs.

If you are familiar with CMake, the build process should be familiar. For example, on Linux-based systems, create a directory for your build. It is safe to do so within the source distribution of parasail. For example:

unzip parasail-v1.0.1.zip
cd parasail-1.0.1
mkdir build
cd build
cmake ..
make

By default, CMake will build the parasail shared library. In order to compile the static library, add -DBUILD_SHARED_LIBS=OFF to your cmake invocation, or use the ccmake utility to toggle the option. The static and shared libraries must be built as separate cmake projects.

Meson build

Please follow http://mesonbuild.com/Quick-guide.html for how to use Meson. The Meson build files are maintained by @SoapZA. This build currently only supports the SSE and AVX ISAs.

Cross-Compiling for ARM

Using Ubuntu 16.04 LTS (Xenial), you can compile for an ARM-based platform using an x86_64-based build platform. First, you will need to install the necessary packages. There are a few different ARM platforms you can compile for using Ubuntu packages; the details of the platforms are not covered here.

Install Prerequisite Packages

sudo apt-get install \
gcc-arm-linux-gnueabi \
g++-arm-linux-gnueabi \
gcc-arm-linux-gnueabihf \
g++-arm-linux-gnueabihf \
gcc-aarch64-linux-gnu \
g++-aarch64-linux-gnu

Run configure for cross-compilation

Cross-compilation is possible with both the autotools and CMake builds, however the autotools build is straightforward. Set the --host and --build options and specify the cross-compilers instead of the standard compilers. If you have zlib installed, you must explicitly disable its inclusion in parasail because the default ubuntu packages from above do not provide it. You can replace the --host option in the following example with --host arm-linux-gnueabi or --host arm-linux-gnueabihf as needed.

# for aarch64
./configure CC=aarch64-linux-gnu-gcc CXX=aarch64-linux-gnu-g++ --build x86_64-pc-linux-gnu --host aarch64-linux-gnu LDFLAGS=-static --without-zlib
# for gnueabi
./configure CC=arm-linux-gnueabi-gcc CXX=arm-linux-gnueabi-g++ --build x86_64-pc-linux-gnu --host arm-linux-gnueabi LDFLAGS=-static --without-zlib
# for gnueabihf
./configure CC=arm-linux-gnueabihf-gcc CXX=arm-linux-gnueabihf-g++ --build x86_64-pc-linux-gnu --host arm-linux-gnueabihf LDFLAGS=-static --without-zlib

Note that you don't really need to specify CC and CXX above (the --host argument will be added as a prefix to gcc and g++ automatically), but being explicit will report errors early in case you forgot to install one of the packages from the prerequisites step.

Verifying Cross-Compiled ARM Executables using QEMU

Install the QEMU (https://www.qemu.org/) package. sudo apt-get install qemu. After a successful make you should have apps/parasail_aligner. QEMU will allow you to run the cross-c