Sequence Alignment Optimization: From $O(n^2)$ to Linear Space

Overview

This project addresses the classic Sequence Alignment problem (finding the similarity between two DNA strands) by comparing two algorithmic approaches. It demonstrates the trade-off between standard Dynamic Programming and a memory-optimized Divide and Conquer strategy (Hirschberg's Algorithm).

The goal was to process large-scale genomic datasets where $O(mn)$ memory consumption is prohibitive, optimizing the space complexity to linear $O(\min(m, n))$ while maintaining alignment accuracy.

The Challenge

Given two DNA sequences $X$ and $Y$ generated via string expansion, finding the optimal alignment requires minimizing penalties:

• Gap Penalty: $\delta = 30$
• Mismatch Penalty: Defined by a specific affinity matrix (e.g., A-C = 110, A-T = 94).

Algorithms Implemented

1. Basic Dynamic Programming (src/basic_solver.py)

• Method: Standard Needleman-Wunsch implementation.
• Space Complexity: $O(mn)$ - Requires storing the full DP table.
• Limitations: Memory usage grows quadratically. Failed to process sequence lengths > 3,000 on standard hardware due to RAM exhaustion (~150MB for M+N=4000).

2. Memory Efficient / Hirschberg's (src/efficient_solver.py)

• Method: A hybrid Divide & Conquer approach combined with DP. It recursively splits the problem space, only storing two rows of the DP table at any given time.
• Space Complexity: $O(\min(m, n))$ - Linear space growth.
• Performance: Successfully processed large sequences with < 1 MB of memory usage, where the basic version required > 150 MB.

Performance Analysis

I benchmarked both solutions on datasets ranging from size 16 to ~4000 (M+N).

Time Complexity

Theoretically, the efficient algorithm performs roughly twice the number of operations due to re-computation. However, in our Python implementation, the efficient version actually performed faster (44s vs 67s for N=4000).

This counter-intuitive result is likely due to memory management overhead in the Basic version. Allocating and accessing a massive $O(N^2)$ matrix (150MB+) causes frequent cache misses and garbage collection pressure, whereas the linear-space version maintains better CPU cache locality.

Space Complexity

The optimization is clearly visible here. The basic algorithm's memory usage explodes quadratically, while the efficient algorithm remains flat (linear).

How to Run

Prerequisites

• Python 3.x
• Linux/Mac environment (recommended for shell scripts) or Windows PowerShell.

Execution

Run the solver using the provided Python scripts. The input file must follow the generation format specified in input/sample_input.txt.

Basic Version:

python src/basic_solver.py input/sample_input.txt output/basic_output.txt

Memory Efficient Version:

python src/efficient_solver.py input/sample_input.txt output/efficient_output.txt

Credits

• Instructor: Prof. Shahriar Shamsian
• Course: CSCI-570 Analysis of Algorithms, University of Southern California