Discovering Motifs in Biological Sequences Using the Micron Automata Processor.

Area of Science:

• Computational Biology
• Bioinformatics
• Algorithm Design

Background:

• Identifying conserved sequences (motifs) across DNA/protein sequences is crucial.
• The (l, d) motif search problem is computationally challenging (NP-complete).
• Previous largest solved instance was (26,11).

Purpose of the Study:

• To propose a novel algorithm for the (l, d) motif search problem.
• To utilize non-deterministic finite automata (NFA) and a new micron automata processor.
• To demonstrate solving larger problem instances.

Main Methods:

• Developed a streaming execution algorithm over a large set of NFAs.
• Designed the solution for parallel execution on a micron automata processor.
• Estimated run-times for significantly larger problem instances.

Main Results:

• The novel algorithm demonstrates capability for solving larger (l, d) motif search instances.
• Estimated run-times for instances (39,18) and (40,17) are feasible on the new hardware.
• The approach effectively utilizes the parallel processing power of the automata processor.

Conclusions:

• The proposed algorithm and hardware acceleration enable solving previously intractable (l, d) motif search problems.
• This work provides a guide for utilizing automata processor technology for motif discovery.
• Significant advancements in computational biology motif analysis are anticipated.