Compiling Bioinformatics Recurrences
For bioinformatics researchers, FILTR enables rapid exploration of new heuristics without sacrificing performance, addressing the complexity of implementing efficient dynamic programming algorithms.
FILTR is a DSL and compiler for bioinformatics recurrences that separates recurrence rules from pruning and scheduling, generating optimized C++ code that matches or outperforms hand-tuned implementations (0.95x to 30x faster).
Many bioinformatics algorithms, such as sequence alignment and structure prediction, can be expressed as recurrence equations over a dynamic programming matrix. Efficient implementations of these algorithms for large-scale biological data often require changing the order in which matrix cells are calculated and pruning ineffectual regions of the matrix from consideration altogether, but these techniques typically complicate implementation. We introduce FILTR, a domain-specific language (DSL) and compiler framework for bioinformatics recurrences. FILTR keeps the core recurrence rules separate from the pruning and scheduling strategies, where pruning acts as an approximation to limit where in the DP matrix cells are computed, and scheduling determines the iteration order for how cells are explored. FILTR compiles these high-level descriptions into optimized C++ code that matches the performance of hand-tuned implementations while enabling rapid exploration of new heuristics. FILTR is competitive with hand-optimized sequence-alignment libraries, ranging from 0.95x to 30x faster across biological benchmarks.