TriStrand
Three DNA strands, one aligned story: 3D dynamic programming at near-C speed with Python ergonomics.
Implement full three-way sequence alignment with complete traceback support for all three strands.
Reduce memory pressure from O(n³) to O(n²) through Hirschberg-style divide-and-conquer recursion.
Stay in the Python ecosystem while achieving near-C speed via Numba JIT kernel compilation.
The Project Brief
A high-performance implementation of three-way Multiple Sequence Alignment (MSA) for DNA sequences, combining classical dynamic programming with modern JIT compilation for practical scalability.
Technical highlights:
- Full 3D Needleman-Wunsch dynamic programming with sum-of-pairs scoring (+5 match / −4 gap).
- Divide-and-conquer recursion (Hirschberg-style) reduces memory complexity from O(n³) to O(n²), enabling alignment of large sequences that would otherwise exhaust memory.
- Core DP kernels JIT-compiled with Numba for near-C speed without leaving the Python ecosystem.
- Built-in memory monitoring and automatic FASTA I/O.
Additional algorithms included:
- Branch-and-bound techniques for combinatorial sequence optimization.
- Hirschberg’s algorithm demonstrating space-efficient dynamic programming.
Stack: Python · Numba · NumPy · BioPython
Key Components
Project Highlights
README documents 3D dynamic programming for three-sequence alignment with customizable scoring parameters.
Numba acceleration is used for core kernels to improve runtime without dropping out of Python tooling.
Input/output supports simple direct sequence edits and FASTA-based workflows.
Quickstart
"Three strands, one truth — alignment is just the universe's way of finding what belongs together."