Discovering Motifs in Biological Sequences Using the Micron Automata Processor
Authors:
- 6 May 2015
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Computational Biology and Bioinformatics
- Vol. 13 (1) , 99-111
Abstract
Finding approximately conserved sequences, called motifs, across multiple DNA or protein sequences is an important problem in computational biology. In this paper, we consider the (l; d) motif search problem of identifying one or more motifs of length l present in at least q of the n given sequences, with each occurrence differing from the motif in at most d substitutions. The problem is known to be NP-complete, and the largest solved instance reported to date is (26;11). We propose a novel algorithm for the (l; d) motif search problem using streaming execution over a large set of non-deterministic finite automata (NFA). This solution is designed to take advantage of the micron automata processor, a new technology close to deployment that can simultaneously execute multiple NFA in parallel. We demonstrate the capability for solving much larger instances of the (l; d) motif search problem using the resources available within a single automata processor board, by estimating run-times for problem instances (39; 18) and (40; 17). The paper serves as a useful guide to solving problems using this new accelerator technology.Keywords
Funding Information
- National Science Foundation (CCF-1448333)
This publication has 23 references indexed in Scilit:
- Finding Motifs in Biological Sequences Using the Micron Automata Processor2014
- qPMS7: A Fast Algorithm for Finding (ℓ, d)-Motifs in DNA and Protein SequencesPLOS ONE, 2012
- PMS5: an efficient exact algorithm for the (ℓ, d)-motif finding problemBMC Bioinformatics, 2011
- Fast and Practical Algorithms for Planted (l, d) Motif SearchIEEE/ACM Transactions on Computational Biology and Bioinformatics, 2007
- RISOTTO: Fast Extraction of Motifs with Mismatches2006
- A HIGHLY SCALABLE ALGORITHM FOR THE EXTRACTION OF CIS-REGULATORY REGIONS2005
- VOTING ALGORITHMS FOR DISCOVERING LONG MOTIFS2005
- Toward Optimal Motif Enumeration2003
- Finding composite regulatory patterns in DNA sequencesBioinformatics, 2002
- Extracting structured motifs using a suffix tree—algorithms and application to promoter consensus identification2000