TetRex

TetRex accelerates regex search of highly conserved motifs in biological sequences by leveraging a hierarchical interleaved bloom filter to reduce search space and improve runtime.

Key Features:

• Index-accelerated regex search: Enables efficient identification of regular expression matches in large biological sequence databases.
• Hierarchical interleaved bloom filter: Utilizes this compact data structure for set membership to reduce the search space prior to traditional regex search.
• Runtime optimization: Combined approach of bloom filter pre-filtering with traditional search outperforms state-of-the-art regex tools.

Scientific Applications:

• Conserved motif identification: Detects highly conserved sequences in genomes and proteomes across unrelated species that are critical to life.
• Large-scale sequence database scanning: Addresses the challenge of searching enormous biological sequence datasets where traditional regex tools fall short.

Methodology:

TetRex employs a hierarchical interleaved bloom filter for set membership queries to reduce the search space, followed by a traditional regex search on the filtered subset.