About

SWIFT is an algorithm for fast local alignment searching. Contrary to popular alignment heuristics such as BLAST, SWIFT guarantees that alignments matching its query parameters will be found. More specifically, it is guaranteed to find ε-matches, where an ε-match is a local alignment over a given length, with an error ratio of at most ε.

The SWIFT algorithm is based on the use of q-grams and a sliding window to quickly and efficiently identify parallelograms in the implied dynamic programming matrix with which ε-matches may overlap.

Downloads

• Source code
• Supplemental information:
  • Efficient q-Gram Filters for Finding All ε-Matches over a Given Length
    K. R. Rasmussen, J. Stoye and E. W. Myers. In Proc. of the 9th Conf. on Computational Molecular Biology (RECOMB'05), pp189-203, Cambridge, MA, 2005.
    [ PDF ] [ Preprint PDF ] [ Presentation Slides ]

Install

• CMake, the cross-platform, open-source make system.
• Boost, the free peer-reviewed portable C++ source libraries.

1. Unpack the archive,

   • tar zxvf swift-r489.tar.gz

2. Create and enter a new build directory for the out-of-source build,

   • mkdir build && cd build

3. Setup the build directory,

   • cmake ../swift-r489

4. Configure the build,

   • ccmake .

   • Change CMAKE_BUILD_TYPE to 'Release'
   • Enter advanced mode (press 't')
   • Change CMAKE_CXX_FLAGS_RELEASE to

     • -O3 -DNDEBUG -fomit-frame-pointer -pipe -fpermissive

   • Press 'c' to configure and then 'q' to quit.
5. Build the executable,

   • make

6. The SWIFT executable now resides in the 'swift' subdirectory. Invoke the 'help' command to get information on usage.

   • cd swift && ./swift help