Search papers, labs, and topics across Lattice.
This paper introduces FILTR, a domain-specific language and compiler framework designed to optimize bioinformatics algorithms expressed as recurrence equations over dynamic programming matrices. By separating core recurrence rules from pruning and scheduling strategies, FILTR enables efficient computation while simplifying implementation complexities associated with large-scale biological data. The framework achieves performance comparable to hand-tuned implementations, demonstrating speed improvements of up to 30 times across various biological benchmarks.
FILTR achieves up to 30x speed improvements in bioinformatics algorithms while simplifying the implementation of complex recurrence relations.
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.
Stanford HAI