Parallel Tiled Codes Implementing the Smith-Waterman Alignment Algorithm for Two and Three Sequences.

Area of Science:

• Computational biology
• Computer science
• Algorithm optimization

Background:

• The Smith-Waterman (SW) algorithm is crucial for sequence alignment but computationally expensive for large datasets.
• Its dynamic programming kernel involves affine control loops amenable to polyhedral modeling.
• Existing optimization techniques struggle with SW's complexity, especially for multiple sequences.

Purpose of the Study:

• To develop an optimized Smith-Waterman (SW) algorithm implementation using polyhedral compilation.
• To enhance SW performance for two- and three-sequence alignments.
• To enable efficient parallelization and tiling of SW code.

Main Methods:

• Applied polyhedral compilation techniques, including transitive closure of dependence graphs and loop skewing.
• Generated parallel tiled loop nests for SW implementations.
• Utilized an under-approximation of transitive closure to reduce computational complexity.

Main Results:

• Achieved significantly higher performance compared to existing compilers.
• Enabled full loop tiling, surpassing limitations of standard affine transformations.
• Successfully optimized three-sequence alignment code, which is not feasible with current compilers.
• Demonstrated high speedup and good scalability on a modern Intel multiprocessor.

Conclusions:

• The proposed polyhedral compilation approach offers efficient SW algorithm implementations.
• Under-approximated transitive closure effectively reduces computational cost while maintaining code validity.
• The method significantly enhances performance and scalability for sequence alignment tasks.