parasail is a SIMD C (C99) library for pairwise sequence alignment. It implements Smith-Waterman (local), Needleman-Wunsch (global), and various semi-global algorithms (where insertions before the start or after the end of sequences are optionally not penalized).

Supported algorithms include:

• Diagonal [Wozniak, 1997]
• Blocked [Rognes and Seeberg, 2000]
• Striped [Farrar, 2007]
• Prefix scan [Daily, 2015]

Implementation Variants: To maintain high performance, parasail provides three distinct implementation variants. You should choose based on your performance/data requirements:

1. Score only: Returns the alignment score and ending locations.
2. Score + Statistics: Returns score, ending locations, and alignment statistics (exact matches, similarities, and alignment length).
3. Traceback: Returns score, ending locations, and stores a traceback for later retrieval as a SAM CIGAR string.

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

For _striped or _scan vector implementations, you can create a query profile to reuse the query sequence across multiple alignments. This significantly speeds up database searches where the query remains constant.

Workflow:

1. Create a profile using parasail_profile_create_{width} (e.g., parasail_profile_create_8).
2. Use the profile with SSW-emulation functions like parasail_ssw_profile().
3. Free the profile using parasail_profile_free(profile).

Note: Profiles are opaque pointers; do not attempt to access their members directly.

// Create a profile for 8-bit striped/scan implementations
parasail_profile_t *profile = parasail_profile_create_8(s1, s1Len, matrix);

// Use the profile for subsequent alignments
parasail_result_ssw_t *result = parasail_ssw_profile(profile, s2, s2Len, 11, 1);

// Cleanup
parasail_result_ssw_free(result);
parasail_profile_free(profile);

Parasail contains over 1,000 functions. They are named using a structured pattern based on the algorithm, optimization, and data type.

1. Algorithm Base:

• sw: Smith-Waterman (local)
• nw: Needleman-Wunsch (global)
• sg: Semi-Global (no penalties at start/end of both sequences)
• sg_qb, sg_qe, sg_qx, etc.: Various semi-global modes (e.g., qb = no penalty for gaps at beginning of query).

2. Suffixes for Features:

• _stats: Returns alignment statistics.
• _table / _rowcol: Returns DP table or last row/column.
• _scan: Uses prefix scan implementation.
• _trace: Enables traceback capabilities.

3. Vectorization & Optimization:

• Non-vectorized: parasail_{algorithm}
• Vectorized: parasail_{algorithm}_{strategy}_{instruction_set}_{width}
  • Strategies: _striped, _scan, _diag.
  • Instruction Sets: _sse2_128, _sse41_128, _avx2_256, _altivec_128, _neon_128.
  • Widths: _8, _16, _32, _64, _sat (attempts 8-bit, falls back to 16-bit if overflow occurs).

4. Dispatchers: If you omit the instruction set and width, the function acts as a CPU dispatcher. It automatically selects the best available instruction set for the current CPU. This is the recommended way to call functions to ensure portability and performance.

// Example: Needleman-Wunsch, stats, striped, SSE4.1, 16-bit
parasail_nw_stats_striped_sse41_128_16

// Example: Smith-Waterman, local, AVX2, 8-bit
parasail_sw_scan_avx2_256_8

// Example: Dispatcher (best instruction set automatically chosen)
parasail_nw_stats_scan_16

You can cross-compile for ARM platforms (aarch64, gnueabi, or gnueabihf) from an x86_64 Ubuntu host using the autotools build.

1. Install Prerequisites:

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

2. Configure and Build: Use the --host and --build options. If you have zlib installed, you must use --without-zlib because the standard Ubuntu cross-compilation packages do not provide it.

3. Verify with QEMU: After building, use QEMU to run the binaries on your x86_64 host. You must specify the QEMU_LD_PREFIX using the -L flag.

# Example 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
make

# Verify
qemu-aarch64 -L /usr/aarch64-linux-gnu ./apps/parasail_aligner